Minimum Size Subarray Sum (Smallest subarray whose sum is greater than or equal to target).
Given an array of positive integers and a positive number k. Find the smallest contiguous subarray whose sum is either greater than or equal to k. If no subarray is found then return 0.
For example –
Example 1 –
Input : {7, 2, 1, 1, 6, 5}, k = 11
Output: 2 ( subarray {6, 5} has the minimum length )
Example 2 –
Input : {1, 4, 3}, k = 12
Output: 0 (No subarray is possible)
In this tutorial, I am going to discuss multiple approaches and their time complexities to solve this problem.
Method 1 : By using brute force approach
The easiest approach is to form all the subarrays of the array whose sum is greater than or equal to k. To form all the subarrays we need to use two for loops.
From the outer loop we pick each element of an array one by one. And from the inner loop we keep adding the elements (starting from that index) till it is less than the value of k.
Whenever sum of elements between current start and end becomes equal or greater than the given number, update the min length value.
The time complexity of this approach is O(n^2).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//Find minimum length subarray sum using brute force approach public static int minSubArrayLengthBruteForce(int[] nums, int k){ //Declare a variable and assign integer max value int minLength = Integer.MAX_VALUE; int sum = 0; //outer loop starts from 0th index for(int i = 0; i < nums.length; i++) { sum = 0; //Inner starts from the value of i for(int j = i; j < nums.length; j++) { //Add the value in sum variable sum = sum + nums[j]; /* If the value of sum is greater than or equal to the value of k. */ if(sum >= k ) { //Update the value of minlength, if it's applicable minLength = Math.min(minLength, (j-i)+1); break; } } } //Return minlength return (minLength == Integer.MAX_VALUE) ? 0 : minLength; } |
We have solved this problem in O(n^2). Now, let’s think how we can solve this problem efficiently. How we can improve our time complexity?
Minimum Size Subarray Sum – Java Code
How we can find smallest subarray with sum greater than or equal to the given value?
We can solve this problem using two pointers in O(n) time complexity. Here are the following steps –
i) Declare three pointers start, sum and minLength. Initialize start and sum with zero and minLength with integer max value.
start = 0, sum = 0, minLength = Integer.MAX_VALUE
ii) Start traversing an array and do the following operations.
a) Add current array index value to the sum variable.
b) while sum is greater than or equal to k. Then, update min length and subtract arr[start] value from sum variable. Also increment the value of start index.
Also, I have added the video tutorial at the end of this post.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
/* Find smallest subarray with sum greater than or equal to the given value */ public class MinimumSizeSubarray { public static int minSubArrayLength(int[] nums, int k) { int start = 0; int sum = 0; int minLength = Integer.MAX_VALUE; //Move end pointer for (int end = 0; end < nums.length; end++) { //Add value to the sum variable sum = sum + nums[end]; //while sum is greater than the value of k while (sum >= k && start <= end) { //Keep track of minLength minLength = Math.min(minLength, (end - start) + 1); /* Subtract the value from sum variable and Move start pointer sum = sum - nums[start++]; } } return (minLength == Integer.MAX_VALUE) ? 0 : minLength; } public static void main(String[] args) { int[] arr = { 7, 2, 1, 1, 6, 5 }; int k = 11; //int[] arr = {1, 4, 3}; //int k = 12; int length = minSubArrayLength(arr, k); System.out.println(length); } } |
Find triplet with given sum in an array
Find maximum sum of a subarray of size k
