Continuous Subarray With Min Elements Greater Than a Given Target
Problem statement
Given an array of positive integers a and a positive number K, find the length of the smallest contiguous subarray whose sum is greater than or equal to K. Return 0 if no such subarray exists.
Variations of the problem
- Find the length of the smallest contiguous subarray whose sum is equal to
K(Instead of greater than equal toK). Check out the approach for this variation →- What if the array has negative numbers as well?
Example 1:
Input: a = [ 2, 1, 4, 3, 2, 5 ], K = 7 Output: 2 Explanation: The smallest subarray with a sum greater than or equal to '7' is [ 4, 3 ] Example 2:
Input: [ 3, 4, 1, 1, 6 ], K = 8 Output: 3 Explanation: Smallest subarrays with sum greater than or equal to '8' are [ 3, 4, 1 ] or [ 1, 1, 6 ]. Example 3:
Input: a = [ 1, 3, 2, 1, 5 ], K = 15 Output: 0 Explanation: No subarray exists with sum greater than or equal to 15 Solution
Brute Force
The naive brute force approach is to explore all the subarrays of the array, and for each subarray check if its sum is greater than or equal to K or not. Compare the length of all the subarrays whose sum is greater than or equal to K to find the length of the smallest subarray.
The time complexity for this approach is O(n^2). Let's look at the implementation:
import java.util. Scanner ; public class MinimumSizeSubarraySum { private static int findLengthOfSmallestSubarray_BruteForce ( int [ ] a, int K ) { int n = a.length; int lengthOfSmallestSubarray = Integer .MAX_VALUE; for ( int i = 0 ; i < n; i++ ) { int currentSubarraySum = 0 ; for ( int j = i; j < n; j++ ) { currentSubarraySum += a[j] ; if (currentSubarraySum >= K ) { lengthOfSmallestSubarray = Math . min (lengthOfSmallestSubarray, j-i+ 1 ) ; break ; } } } return lengthOfSmallestSubarray == Integer .MAX_VALUE ? 0 : lengthOfSmallestSubarray; } public static void main ( String [ ] args) { Scanner keyboard = new Scanner ( System .in) ; int n = keyboard. nextInt ( ) ; int [ ] a = new int [n] ; for ( int i = 0 ; i < n; i++ ) { a[i] = keyboard. nextInt ( ) ; } int K = keyboard. nextInt ( ) ; keyboard. close ( ) ; System .out. printf ( "Length of the Smallest subarray with sum greater than or equal to %d = %d%n" , K , findLengthOfSmallestSubarray_BruteForce (a, K ) ) ; } } Time complexity of the brute force algorithm is O(n^2).
Sliding Window
If you observe the way we calculate the sum of the subarrays in the brute force approach, you will realize that we're doing repetitive calculation in the inner loop. Let's understand this with an example:
Input: [ 3, 4, 1, 1, 2, 1 ], K = 9 We start from the first element 3 and start calculating the sum of the subarrays starting from 3.
Subarray [ 3 ] Sum = 2 Subarray [ 3, 4 ] Sum = 7 Subarray [ 3, 4, 1 ] Sum = 8 Subarray [ 3, 4, 1, 1 ] Sum = 9 After doing the above calculations, We got a sum greater than or equal to K. So we update the minimum length and move on to explore subarrays starting from the next element (4).
Subarray [ 4 ] Sum = 1 Subarray [ 4, 1 ] Sum = 5 Subarray [ 4, 1, 1 ] Sum = 6 Subarray [ 4, 1, 1, 2 ] Sum = 8 Subarray [ 4, 1, 1, 2, 1 ] Sum = 9 Notice that, we're calculating the sum of the overlapping subarrays twice. For example, we're calculating the sum of the subarray [4, 1, 1] both in the first iteration of the outer loop as well as the second iteration.
We can use the sliding window technique to save us from recalculating the sum of the overlapping subarrays. We will use a similar strategy explained in Maximum Sum Subarray of Size K. But there is one difference: in this problem, the sliding window size is not fixed. Instead, we need to minimize the window size.
- Consider each subarray as a sliding window.
- Start with a sliding window of size
1(windowStart=0, windowEnd=0). - Iterate over the array and add elements to the window until the sum becomes greater than or equal to
K.- At this point, we have a window (subarray) that conforms to our criteria of
sum >= K. Remember the length of this window as the smallest window so far. - Now, there is no point in adding more elements to the window because we need to find the smallest window. So we will start shrinking the window from the left until the sum becomes smaller than
K. While shrinking the window, we will do two things:- Check if the current window length is the smallest so far. If yes, then update the minimum length.
- Subtract the leftmost element of the window from the window sum to shrink the sliding window.
- At this point, we have a window (subarray) that conforms to our criteria of
Here is the complete implementation:
import java.util. Scanner ; public class MinimumSizeSubarraySum { private static int findLengthOfSmallestSubarray ( int [ ] a, int K ) { int n = a.length; int lengthOfSmallestSubarray = Integer .MAX_VALUE; int windowSum = 0 ; int windowStart = 0 ; for ( int windowEnd = 0 ; windowEnd < n; windowEnd++ ) { windowSum += a[windowEnd] ; // Add the next element to the window while (windowSum >= K ) { // Shrink the window as small as possible until the 'windowSum' is smaller than 'K' lengthOfSmallestSubarray = Math . min (lengthOfSmallestSubarray, windowEnd-windowStart+ 1 ) ; windowSum -= a[windowStart] ; // Discard the element at 'windowStart' since it is going out of the window windowStart++ ; // Shrink the window } } return lengthOfSmallestSubarray == Integer .MAX_VALUE ? 0 : lengthOfSmallestSubarray; } public static void main ( String [ ] args) { Scanner keyboard = new Scanner ( System .in) ; int n = keyboard. nextInt ( ) ; int [ ] a = new int [n] ; for ( int i = 0 ; i < n; i++ ) { a[i] = keyboard. nextInt ( ) ; } int K = keyboard. nextInt ( ) ; keyboard. close ( ) ; System .out. printf ( "Length of the Smallest subarray with sum greater than or equal to %d = %d%n" , K , findLengthOfSmallestSubarray (a, K ) ) ; } } Find the Smallest subarray with Sum exactly equal to K
In this variation of the problem, we're asked to find the length of the smallest contiguous subarray whose sum is exactly equal to K.
Brute Force
This is similar to the brute force approach we discussed for the original problem. The only difference is that we're checking if the subarray sum is equal to K instead of greater than or equal to K.
import java.util. Scanner ; public class MinimumSizeSubarraySum { private static int findLengthOfSmallestSubarray_BruteForce ( int [ ] a, int K ) { int n = a.length; int lengthOfSmallestSubarray = Integer .MAX_VALUE; for ( int i = 0 ; i < n; i++ ) { int currentSubarraySum = 0 ; for ( int j = i; j < n; j++ ) { currentSubarraySum += a[j] ; if (currentSubarraySum == K ) { lengthOfSmallestSubarray = Math . min (lengthOfSmallestSubarray, j-i+ 1 ) ; break ; } if (currentSubarraySum > K ) { // No need to add further elements. Since the array only has positive integers, // the sum will keep increasing. break ; } } } return lengthOfSmallestSubarray == Integer .MAX_VALUE ? 0 : lengthOfSmallestSubarray; } public static void main ( String [ ] args) { Scanner keyboard = new Scanner ( System .in) ; int n = keyboard. nextInt ( ) ; int [ ] a = new int [n] ; for ( int i = 0 ; i < n; i++ ) { a[i] = keyboard. nextInt ( ) ; } int K = keyboard. nextInt ( ) ; keyboard. close ( ) ; System .out. printf ( "Length of the Smallest subarray with sum equal to %d = %d%n" , K , findLengthOfSmallestSubarray_BruteForce (a, K ) ) ; } } Sliding Window
The sliding window implementation of this variation is also similar to the implementation of the original problem. The difference is that we update the minimum length only when the windowSum is equal to K.
import java.util. Scanner ; public class MinimumSizeSubarraySum { private static int findLengthOfSmallestSubarray ( int [ ] a, int K ) { int n = a.length; int lengthOfSmallestSubarray = Integer .MAX_VALUE; int windowSum = 0 ; int windowStart = 0 ; for ( int windowEnd = 0 ; windowEnd < n; windowEnd++ ) { windowSum += a[windowEnd] ; // Add the next element to the window while (windowSum > K ) { // Shrink the window as small as possible until the 'windowSum' is smaller than or equal to 'K' windowSum -= a[windowStart] ; // Discard the element at 'windowStart' since it is going out of the window windowStart++ ; // Shrink the window } if (windowSum == K ) { lengthOfSmallestSubarray = Math . min (lengthOfSmallestSubarray, windowEnd-windowStart+ 1 ) ; } } return lengthOfSmallestSubarray == Integer .MAX_VALUE ? 0 : lengthOfSmallestSubarray; } public static void main ( String [ ] args) { Scanner keyboard = new Scanner ( System .in) ; int n = keyboard. nextInt ( ) ; int [ ] a = new int [n] ; for ( int i = 0 ; i < n; i++ ) { a[i] = keyboard. nextInt ( ) ; } int K = keyboard. nextInt ( ) ; keyboard. close ( ) ; System .out. printf ( "Length of the Smallest subarray with sum equal to %d = %d%n" , K , findLengthOfSmallestSubarray (a, K ) ) ; } } Source: https://www.callicoder.com/minimum-size-subarray-sum-smallest-subarray-with-given-sum/
0 Response to "Continuous Subarray With Min Elements Greater Than a Given Target"
Post a Comment