Minimum Size Subarray Sum

Companies:
  • Uber Interview Questions

Problem Statement

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.

Sample Test Cases

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.

Problem Solution

The better approach to solving the problem is to use two pointers, ptr1 and ptr2, where ptr1 represents the starting index of subarray and ptr2 represents the ending index.

  1. Initialize ptr1 and ptr2 as 0(zero) and a variable sum as 0(zero).
  2. While the value of sum is less than the required sum, add value present at ptr2 to sum and move ptr2 ahead.
  3. While the value of sum is greater than or equals to the required sum, update the minimum subarray length, and remove the value present at ptr1 from sum and move ptr1 ahead.
  4. Repeat step 2 and step 3 while ptr1 is less than the length of the given array.
  5. If there is no subarray with the required sum, return 0, else return the length of minimum length subarray.

Complexity Analysis

Time Complexity: O(n ) since both the pointers will iterate array only once.

Space Complexity: O(1) since no extra data structure was used to store.

Code Implementation

#include <bits/stdc++.h> 
using namespace std; 
int findMinimumSizeSubarray(int *nums, int s, int n) { 
  // Initialize ptr1, ptr2 and sum as 0 
  int ptr1 = 0, ptr2 = 0, sum = 0; 
  int ans = INT_MAX; 
  // While ptr2 is less than n 
  while (ptr2 < n) { 
    // While the sum is less than s, add value present at ptr2 to sum and move ptr2 ahead 
    while (sum < s && ptr2 < n) { 
      sum += nums[ptr2++]; 
    } 
    // While sum greater than or equals to s, update the minimum subarray length and remove value 
    // present at ptr1 from sum and move ptr1 ahead 
    while (sum >= s && ptr1 < n) { 
      ans = std::min(ans, ptr2 - ptr1); 
      sum -= nums[ptr1++]; 
    } 
  } 
  // Subarray with required sum is not found 
  if (ans == INT_MAX) { 
    ans = 0; 
  } 
  return ans; 
} 
int main() { 
  int nums[] = {2, 3, 1, 2, 4, 3}; 
  int sum = 7; 
  int minSize = findMinimumSizeSubarray(nums, sum, 6); 
  cout<<minSize<<endl; 
  return 0; 
}

 

Scroll to Top

Full Stack Integrated Bootcamp Free Trial

  • Please enter a number from 7000000000 to 9999999999.