Skip to content

2875. Minimum Size Subarray in Infinite Array 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int minSizeSubarray(vector<int>& nums, int target) {
    const long sum = accumulate(nums.begin(), nums.end(), 0L);
    const int n = nums.size();
    const int remainingTarget = target % sum;
    const int repeatLength = (target / sum) * n;
    if (remainingTarget == 0)
      return repeatLength;

    int suffixPlusPrefixLength = n;
    long prefix = 0;
    unordered_map<long, int> prefixToIndex{{0, -1}};

    for (int i = 0; i < 2 * n; ++i) {
      prefix += nums[i % n];
      if (const auto it = prefixToIndex.find(prefix - remainingTarget);
          it != prefixToIndex.cend())
        suffixPlusPrefixLength = min(suffixPlusPrefixLength, i - it->second);
      prefixToIndex[prefix] = i;
    }

    return suffixPlusPrefixLength == n ? -1
                                       : suffixPlusPrefixLength + repeatLength;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int minSizeSubarray(int[] nums, int target) {
    final long sum = Arrays.stream(nums).asLongStream().sum();
    final int n = nums.length;
    final int remainingTarget = (int) (target % sum);
    final int repeatLength = (int) (target / sum) * n;
    if (remainingTarget == 0)
      return repeatLength;

    int suffixPlusPrefixLength = n;
    long prefix = 0;
    HashMap<Long, Integer> prefixToIndex = new HashMap<>();
    prefixToIndex.put(0L, -1);

    for (int i = 0; i < 2 * n; ++i) {
      prefix += nums[i % n];
      if (prefixToIndex.containsKey(prefix - remainingTarget))
        suffixPlusPrefixLength =
            Math.min(suffixPlusPrefixLength, i - prefixToIndex.get(prefix - remainingTarget));
      prefixToIndex.put(prefix, i);
    }

    return suffixPlusPrefixLength == n ? -1 : repeatLength + suffixPlusPrefixLength;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def minSizeSubarray(self, nums: List[int], target: int) -> int:
    summ = sum(nums)
    n = len(nums)
    remainingTarget = target % summ
    repeatLength = (target // summ) * n
    if remainingTarget == 0:
      return repeatLength

    suffixPlusPrefixLength = n
    prefix = 0
    prefixToIndex = {0: -1}

    for i in range(2 * n):
      prefix += nums[i % n]
      if prefix - remainingTarget in prefixToIndex:
        suffixPlusPrefixLength = min(
            suffixPlusPrefixLength,
            i - prefixToIndex[prefix - remainingTarget])
      prefixToIndex[prefix] = i

    return -1 if suffixPlusPrefixLength == n else suffixPlusPrefixLength + repeatLength