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).
Table of Contents
Example
Input:
nums[] = {2, 3, 1, 2, 4, 3}
s = 7
Output:
2 {Subarray [4, 3] sums to 7 and has the minimum length}
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.
- Initialize ans as infinite.
- 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.
- 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.
- 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.
- If the value of ans is infinite, no subarray with the required sum is found, return 0, else return and.
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.
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
- Initialize ptr1 and ptr2 as 0(zero) and a variable sum as 0(zero).
- While the value of sum is less than the required sum, add value present at ptr2 to sum and move ptr2 ahead.
- 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.
- Repeat step 2 and step 3 while ptr1 is less than the length of the given array.
- 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.