leetcode Question: Minimum Size Subarray Sum

Minimum Size Subarray Sum

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

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Analysis:

Here in this post we just implement O(n log n) solution using binary search.

At first it took me so much time to design the binary search on the original data array, however it is neither a neat binary search algorithm nor pass the OJ time limits.

Then from the problem description I found that "sum >= s" and word "subarray". In other words, this means we don't have to know each number, we just need to know the sum, and start/end positions (end-start leads to length).

OK, so first step is to get the sum array "ss[ ]" , where ss[0] = 0, ss[1] = sum(nums[0..1]), ss[i] = sum(nums[0,i-1]).

Then next step is to design the binary search. We know that for binary search, each time we split "some" array into two parts (remember mid = st + (ed-st)/2 ?),  check some conditions (e.g., key ? > mid element), then decide keep searching one part until meet terminating conditions.

In this problem, my solution is slight different but essentially it is the same to binary search, the key idea is:
(1) We fix starting point "st".
(2) Two pointers, p,q
(3) Binary search between p and q
(4) According to the problem, find min length starting from st.

The above steps takes O(log n) complexity. Iterate every element as the starting point will result in the final result. Therefore the time complexity n log n.


For example, let's say the number array is :
[10, 5, 13, 4, 18, 4, 5, 11, 14, 9, 16, 10, 20, 18]
We calculate the sum array:
[0, 10, 15, 28, 32 40, 44, 49, 60, 74, 83, 99, 109, 129, 137]
Set the starting points, set two pointers, and starting search:

Note that, when we get mid element between p and q, the subarray sum is ss[mid] - ss[st], but not ss[mid] - ss[p], since we fix the starting point st, only using binary search to find the other position, which has min length and sum from st is larger than s.

     [0, 10, 15, 28, 32 40, 44, 49, 60, 74, 83, 99, 109, 129, 137]
1. st,p                                                                              q
2. st,p                                mid                                        q       ss[mid]-ss[st] < s, search right half
3.  st                                    p'                                          q'
4.  st                                    p'               mid'                    q'      ss[mid]-ss[st] >= s, search left half
*(Because the length from st to any element in left half is smaller than any element in right half.)
5.  st                                    p''               q''
6.  st                                    p'' mid''       q''
7.  st                                           p'''        q'''
8.  st                                           p'''mid'''q'''
9.  st                                                  p''''q''''
So, the min length starting from 0 is (q''''- st)

Iterate st from 0 to n-1, the min length is the final result.

Code(C++):

class Solution {
public:
    void search(vector<int> &ss, int st, int p, int q, int &res, int &s){
        if (ss[q]-ss[st] >= s && p < q){
            res = min(res, q-st);    
            int mid = p + (q-p)/2;
            if (ss[mid]-ss[st] >= s){
                search(ss, st, p, mid, res, s);
            }else{
                if (mid != p){ 
                    search(ss,st, mid ,q,res, s);
                }
          }
        }
    }
    
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n==0) return 0;
        vector<int> ss(n+1,0);
        int res = n;
        
        for (int i=0;i<n;i++){
            ss[i+1] = ss[i] + nums[i];
        }
        
        if (ss[n] < s) return 0;
        
        for (int i=0;i<n;i++){
            search(ss,i, i, n,res,s);
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    def search(self, ss, st, p, q, res,s):
        if ss[q]-ss[st] >= s and p < q:
            res[0] = min(res[0], q-st)
            mid = p + (q-p)/2
            if ss[mid]-ss[st] >= s:
                self.search(ss, st, p, mid, res, s)
            else:
                if mid != p:
                    self.search(ss,st, mid ,q,res, s)
                    
    # @param {integer} s
    # @param {integer[]} nums
    # @return {integer}
    def minSubArrayLen(self, s, nums):
        n = len(nums)
        if n==0:
            return 0
        ss = [0 for x in range(n+1)]
        res = [n]
        for i in range(n):
            ss[i+1] = ss[i] + nums[i]
        if ss[n] < s:
            return 0
        
        for i in range(n):
            self.search(ss, i, i, n, res, s)
        
        return res[0];