209. Minimum Size Subarray Sum


Reference: LeetCode
Difficulty: Medium

Problem

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example: 

1
2
3
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up: If you have figured out the $O(N)$ solution, try coding another solution of which the time complexity is $O(N\log{N})$.

Analysis

Brute-Force

Note: Be careful of the initialization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minSubArrayLen(int s, int[] nums) {
  // assume nums is not null
  int n = nums.length;
  int minLen = Integer.MAX_VALUE;
  
  for (int i = 0; i < n; ++i) {
    int sum = 0;
    for (int j = i; j < n; ++j) {
      sum += nums[j];
      if (sum >= s) {
        minLen = Math.min(minLen, j - i + 1);
      }
    }
  }
  
  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Time: $O(N^2)$
Space: $O(1)$

TreeMap

My TreeMap Post: TreeSet/TreeMap Usage & binarySearch()

Based on the idea in 325. Maximum Size Subarray Sum Equals K, we can use a tree map for solving this problem.

Modification:

When we have duplicate prefix sums, we update the index. It is because in this problem we want the minimum size. However, since the problem statement says there are all positive integers, there won’t be duplicate prefix sums.

1
2
3
4
  x      s
-----> ------>
------------->
     sum

Also, in this problem we want the sum greater than or equal to s, so we cannot use hash map. Instead, we use a tree map. In the example above, when we have a prefix sum sum, we check if there is an x such that sum - x >= s. In other words, we want x <= sum - s. It is to find the greatest x that satisfies the equation. This can be achieved by using floorKey(K) in TreeMap.

Try it by hand with an example!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minSubArrayLen(int s, int[] nums) {
  // assume nums is not null
  int n = nums.length;
  TreeMap<Integer, Integer> map = new TreeMap<>(); // <prefixSum, index>
  map.put(0, -1);
  
  int minLen = Integer.MAX_VALUE;
  
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += nums[i];
    
    if (map.floorKey(sum - s) != null) {
      int size = i - map.get(map.floorKey(sum - s)); // or floorEntry(K).getValue()
      minLen = Math.min(minLen, size);
    }
    
    map.put(sum, i); // update to the latest index
  }
  
  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Time: $O(N\log{N})$
Space: $O(N)$

Based on the same idea, we can implement the binary search by ourselves. We don’t need a tree map here because we have positive elements such that prefix sums are always increasing; in other words, as we build the array, it is always sorted in ascending order.

In this solution, we apply upper-bound binary search (FYI: Binary Search Template Notes).

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int minSubArrayLen(int s, int[] nums) {
  // assume nums is not null
  int n = nums.length;
  int[] prefix = new int[n + 1];
  prefix[0] = 0; // corresponding to map.put(0, -1), but index starts from 0
  // prefix[0] = 0, prefix[1] = nums[0], prefix[2] = nums[0] + nums[1], ...
  
  int minLen = Integer.MAX_VALUE;
  
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += nums[i];
    
    int result = binarySearch(prefix, 0, i, sum - s);
    if (result != -1) { // <= sum - s
      int size = i - result + 1;
      minLen = Math.min(minLen, size);
    }

    prefix[i + 1] = sum;
  }
  
  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

// To find the one (<= key)
// we use upper-bound BS to find (> key)
// exists:     lo - 1 --> existing item
// not exists: lo - 1 --> greatest item < key
private int binarySearch(int[] nums, int lo, int hi, int key) {
  int oldLo = lo;
  int oldHi = hi;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] > key) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  lo -= 1;
  if (lo >= oldLo && lo <= oldHi) return lo;
  else return -1;
}

Time: $O(N\log{N})$
Space: $O(N)$

Two Pointers

1
s = 0, nums = [0] // this is an invalid input

Instead of having the starting index fixed, we update it when it no longer contributes to a solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
s = 7, nums = [2, 3, 1, 2, 4, 3]  // output: 2
              i/j (2)             // i = start, j = end
               i  j (5)
               i     j (6)
               i        j (8) // increasing j does not give us a better solution
                  i     j (6)
                  i        j (10)
                     i     j (7)
                        i  j (6)
                        i     j (9)
                           i  j (7)
                             i/j (3)

My Version: (initialize sum as nums[0])

Note: The subarray is [start, end].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int minSubArrayLen(int s, int[] nums) {
  // assume nums is not null
  int n = nums.length;
  if (n == 0) {
    return 0;
  }
  int sum = nums[0];
  int minLen = Integer.MAX_VALUE;
  int start = 0, end = 0; // [start, end]

  while (end < n) {
    if (sum < s) {
      ++end;
      if (end == n) break;
      sum += nums[end];
    } else { // sum >= s
      minLen = Math.min(minLen, end - start + 1);
      sum -= nums[start];
      ++start;
    }
  }

  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

We can also use while to update start until it satisfies the condition:

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
public int minSubArrayLen(int s, int[] nums) {
  // assume nums is not null
  int n = nums.length;
  if (n == 0) {
    return 0;
  }
  int sum = nums[0];
  int minLen = Integer.MAX_VALUE;
  int start = 0, end = 0; // [start, end]

  while (end < n) {
    if (sum < s) {
      ++end;
      if (end == n) break;
      sum += nums[end];
    }
    while (sum >= s) { // nums[] can't be 0
      minLen = Math.min(minLen, end - start + 1);
      sum -= nums[start];
      ++start;
    }
  }

  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Other:

Note: The subarray is [start, end).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int minSubArrayLen(int s, int[] nums) {
  // assume nums is not null
  int n = nums.length;
  int sum = 0;
  int minLen = Integer.MAX_VALUE;
  int start = 0, end = 0;

  while (end < n) {
    sum += nums[end];
    ++end;
    if (sum >= s) {
      minLen = Math.min(minLen, end - start);
      --end;
      sum -= nums[end]; // restore
      sum -= nums[start]; ++start;
    } // sum < s
  }
  
  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Use while:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int minSubArrayLen(int s, int[] nums) {
  // assume nums is not null
  int n = nums.length;
  int sum = 0;
  int minLen = Integer.MAX_VALUE;
  int start = 0, end = 0;

  while (end < n) {
    sum += nums[end];
    ++end;
    while (sum >= s) {
      minLen = Math.min(minLen, end - start);
      sum -= nums[start];
      ++start;
    }
  }
  
  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Time: $O(N)$
Space: $O(1)$

Comment
avatar
Junhao Wang
a software engineering cat
Articles
50
Tags
115
Categories
10
Newest Comments
loading...
Categories
Info
Article :
50
Total Count :
82.4k
UV :
PV :
Last Push :