Header Ad

Leetcode Minimum Size Subarray Sum problem solution

In this Leetcode Minimum Size Subarray Sum problem solution Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Leetcode Minimum Size Subarray Sum problem solution


Problem solution in Python.

class Solution(object):
    def minSubArrayLen(self, s, nums):
        res = float("inf")
        if(nums):
            i=0
            window,currWindowSum = 0,0
            while(i+window<len(nums)):
                currWindowSum+=nums[i+window]
                if(currWindowSum>=s):
                    while(currWindowSum>=s): 
                        res=min(window+1,res)
                        currWindowSum-=nums[i] 
                        i+=1
                        window-=1
                window+=1
        return 0 if(res==float("inf")) else res



Problem solution in Java.

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums.length == 0) return 0;
        int left = 0, right = 0, min = Integer.MAX_VALUE, sum = nums[0];
        while(right < nums.length){
            if(sum < s){
                right++;
                if(right == nums.length) break;
                sum += nums[right];
            }else{
                min = Math.min(min, right-left+1);
                left++;
                sum -= nums[left-1];
            }
        }
        return min == Integer.MAX_VALUE? 0 : min;
    }
}


Problem solution in C++.

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0, right = 0;
        int res = INT_MAX;
        int cnt = 0;
        while(right < nums.size()){
            cnt += nums[right];
            while(left <= right && cnt >= s){
                res = min(res, right-left+1);
                cnt -= nums[left];
                left++;
            }
            right++;
        }
        return res == INT_MAX ? 0 : res;
    }
};


Problem solution in C.

int minSubArrayLen(int s, int* nums, int numsSize) {
    int *slowRunner, *fastRunner;
    int sumSoFar;
    int shortest;
    int curLength;
    
    slowRunner = fastRunner = nums;
    sumSoFar = 0;
    shortest = numsSize;
    
    while (fastRunner < nums + numsSize) {
        sumSoFar += *fastRunner;
        fastRunner++;   
   
        while (sumSoFar >= s) {
            sumSoFar -= *(slowRunner++);
            curLength = fastRunner - slowRunner + 1;
            shortest = curLength < shortest ? curLength : shortest; 
        }
    }
    return fastRunner - slowRunner == numsSize ? 0 : shortest;
}


Post a Comment

0 Comments