Home » Technical Interview Questions » Array Interview Questions » Minimum Size Subarray Sum

Minimum Size Subarray Sum


Reading Time - 6 mins

Given an array nums of a positive integer and a sum s, find the minimum size of a contiguous subarray of nums such that whose sum equals to or greater than s(given value).

Example

Input:
nums[] = {2, 3, 1, 2, 4, 3}
s = 7
Output:
2   {Subarray [4, 3] sums to 7 and has the minimum length}

Minimum Size Subarray Sum

Naive Approach for Minimum Size Subarray Sum

The naive approach to solve the above problem is to run two nested loop, where the outer loop represents the starting index of subarray and the inner loop finds the ending index of subarray with sum greater than or equals to a given sum.
Select the subarray with minimum length as the answer.

  1. Initialize ans as infinite.
  2. Run a loop for i = 0 to n(not included), where n is the number of elements in the array, and repeat steps 3 and 4.
  3. Initialize a variable sum as 0. Initialize a boolean variable found as false. Run a nested loop for j = (i + 1) to n(not included) and at every iteration check if the sum is greater than or equals to required sum, if it is greater set found as true and update the ans as a minimum of ans and (j – i), as (j – i) is the length of this subarray and break out of the loop. Else add the value of the current element to the sum.
  4. If found is false, check if the sum is greater than or equals to the required sum if it is updated ans as a minimum of ans and (n – i) as (n – i) is the length of subarray starting from I and ending at the last element.
  5. If the value of ans is infinite, no subarray with the required sum is found, return 0, else return and.
READ  Move all negative elements to end in order with extra space allowed

JAVA Code

public class MinimumSizeSubarray {
    private static int findMinimumSizeSubarray(int[] nums, int s) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        // Outer loop denotes starting index
        for (int i = 0; i < n; i++) {
            int sum = nums[i];
            boolean found = false;
            // Inner loop finds the ending index
            for (int j = i + 1; j < n; j++) {
                if (sum >= s) {
                    // Subarray found
                    int length = j - i;
                    ans = Math.min(ans, length);
                    found = true;
                    break;
                }

                // Add the current value to sum
                sum += nums[j];
            }

            if (!found) {
                // This handles the case of subarray from i to last
                if (sum >= s) {
                    int length = n - i;
                    ans = Math.min(ans, length);
                }
            }
        }
        
        // Subarray with required sum is not found
        if (ans == Integer.MAX_VALUE) {
            ans = 0;
        }
        
        return ans;
    }

    public static void main(String[] args) {
        int nums[] = new int[] {2, 3, 1, 2, 4, 3};
        int sum = 7;
        
        int minSize = findMinimumSizeSubarray(nums, sum);
        System.out.println(minSize);
    }
}

C++ Code

#include <bits/stdc++.h>
using namespace std;

int findMinimumSizeSubarray(int *nums, int s, int n) {
    int ans = INT_MAX;
    // Outer loop denotes starting index
    for (int i = 0; i < n; i++) {
        int sum = nums[i];
        bool found = false;
        // Inner loop finds the ending index
        for (int j = i + 1; j < n; j++) {
            if (sum >= s) {
                // Subarray found
                int length = j - i;
                ans = std::min(ans, length);
                found = true;
                break;
            }
            // Add the current value to sum
            sum += nums[j];
        }
        
        if (!found) {
            // This handles the case of subarray from i to last
            if (sum >= s) {
                int length = n - i;
                ans = std::min(ans, length);
            }
        }
    }
    
    // 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;
}
2

Complexity Analysis for Minimum Size Subarray Sum

Time Complexity = O(n2
Space Complexity = O(1) 
where n is the number of elements in the array.

READ  Sort Colors

Optimal Approach for Minimum Size Subarray Sum

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.

Algorithm

  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.

JAVA Code

public class MinimumSizeSubarray {
    private static int findMinimumSizeSubarray(int[] nums, int s) {
        int n = nums.length;
        // Initialize ptr1, ptr2 and sum as 0
        int ptr1 = 0, ptr2 = 0, sum = 0;
        int ans = Integer.MAX_VALUE;

        // 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 = Math.min(ans, ptr2 - ptr1);
                sum -= nums[ptr1++];
            }
        }

        // Subarray with required sum is not found
        if (ans == Integer.MAX_VALUE) {
            ans = 0;
        }

        return ans;
    }

    public static void main(String[] args) {
        int nums[] = new int[] {2, 3, 1, 2, 4, 3};
        int sum = 7;

        int minSize = findMinimumSizeSubarray(nums, sum);
        System.out.println(minSize);
    }
}

C++ Code

#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; 
}
2

Complexity Analysis for Minimum Size Subarray Sum

Time Complexity = O(n) 
Space Complexity = O(1)
where n is the number of elements in the array.

READ  Find a sorted subsequence of size 3 in linear time

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions