Two pointer and deque

From two LeetCode questions. From those problems, we can learn:

1. Two pointer
2. Deque
3. Binary search

209. Minimum Size Subarray Sum

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0, j = 0;
        const int n = nums.size();
        int ret = n + 1;
        for (int j = 0; j < n; ++j) {
            // update the nums to prefix_sum
            if ( j > 0) nums[j] += nums[j-1];
            // if the prefix sum sofar qualify, update the result
            if (nums[j] >= target) ret = min(ret, j + 1);
            // when qualify, we reduce the window size if the result after reducing the size is still qualify and update the result
            // example can be support target is 10
            // 1 1 1 1 not qualify
            // [1 1 1 1 10000] qualify
            // 1 [1 1 1 10000] qualify
            // 1 1 [1 1 10000] qualify
            // 1 1 1 [1 10000] qualify
            // 1 1 1 1 [10000] qualify
            while (i < j && nums[j] - nums[i] >= target ) {
                ret = min(ret, j - i);
                i++;
            }
        }
        return ret == n + 1? 0: ret;   
    }
};

This problem can also be solved by using binary search. The solution will not be introduced here. The basic idea is to guess the length, and check whether it qualifies.

if sum(nums) not qualify, it is impossible to be qualified.

If qualify, high will be the guess

if not qualify, guess + 1 will be the low

862. Shortest Subarray with Sum at Least K

The difference of 862 to 209 is in 862, we can have negative values. The introduction of negative value making the logic much harder as:

1. the O(n log n) binary search approach is not working as we can don’t have this property, if the length is n qualify, then the length of n + 1 also be qualified.

An example is, suppose target is 100, in the following case, length 1 qualifies, however, length is 2 does not.

100, -10000, -10000, 100, -10000

However, if no negative values, the property of if the length is n qualify, then the length of n + 1 also be qualified can always hold.

2. The sliding window or two-pointer approach is much harder to be understood.

Lee215[1] gave an awesome solution by using deque. It took me about half a year to fully understand his brilliant solution after creating the following two visualizations by going over one example.

In order to understand the problem better, I only provide the prefix sum results. The original nums can be easily inferred through this prefix sum.

Picture explanation about the whole process part 1

Picture explanation about the whole process part 2

Thanks for reading. For the whole article list of my posts in different categories, please visit my blog.

Reference

[1]https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C++JavaPython-O(N)-Using-Deque