Solution: Smallest Subarray With a Greater Sum

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Smallest Subarray With a Greater Sum

Table of Contents

Contents are not accessible

Problem Statement

Given an array of positive integers and a number ‘S,’ find the length of the smallest contiguous subarray whose sum is greater than or equal to 'S'. Return 0 if no such subarray exists.

Example 1:

Input: arr = [2, 1, 5, 2, 3, 2], S=7
Output: 2
Explanation: The smallest subarray with a sum greater than or equal to '7' is [5, 2].

Example 2:

Input: arr = [2, 1, 5, 2, 8], S=7
Output: 1 
Explanation: The smallest subarray with a sum greater than or equal to '7' is [8].

Example 3:

Input: arr = [3, 4, 1, 1, 6], S=8
Output: 3
Explanation: Smallest subarrays with a sum greater than or equal to '8' are [3, 4, 1] or [1, 1, 6].

Constraints:

1 <= S <= $10^9$
1 <= arr.length <= 10<sup>5</sup>
1 <= arr[i] <= 10<sup>4</sup>

Solution

To solve this problem, we use a sliding window approach. This technique involves expanding and contracting a window over the array to find the shortest subarray that meets the condition. By keeping a running sum of the elements in the window, we can check if the current window meets or exceeds the target sum S. If it does, we try to shrink the window from the left to see if we can get a smaller subarray that still meets the requirement. This approach is efficient because it processes each element of the array only once, resulting in a linear time complexity.

The sliding window approach is effective because it avoids the need for nested loops, which would result in higher time complexity. By dynamically adjusting the window size, we can efficiently find the smallest subarray that meets the condition without re-evaluating the sum for different subarrays multiple times.

Step-by-Step Algorithm

Initialize windowSum to 0, minLength to a very large value, and windowStart to 0.
Iterate through the array with a variable windowEnd from 0 to the end of the array.
For each element at windowEnd, add it to windowSum.
While windowSum is greater than or equal to S, do the following:
- Update minLength to be the smaller value between minLength and the current window size (windowEnd - windowStart + 1).
- Subtract the element at windowStart from windowSum.
- Move windowStart one position to the right.
After the loop ends, check if minLength was updated. If it was, return minLength; otherwise, return 0.

Algorithm Walkthrough

Given the input array [2, 1, 5, 2, 3, 2] and S = 7:

windowStart = 0, windowSum = 0, minLength = Infinity.
Iterate windowEnd from 0 to 5:
- windowEnd = 0, windowSum = 2.
- windowEnd = 1, windowSum = 3.
- windowEnd = 2, windowSum = 8 (5 + 3), which is >= 7.
  - Update minLength to 3 (indices 0 to 2).
  - Subtract element at windowStart (2), windowSum = 6, windowStart = 1.
- windowEnd = 3, windowSum = 8 (1 + 5 + 2), which is >= 7.
  - Update minLength to 3 (Unchanged).
  - Subtract element at windowStart (1), windowSum = 7, windowStart = 2.
  - Update minLength to 2.
  - Subtract element at windowStart (5), windowSum = 2, windowStart = 3.
- windowEnd = 4, windowSum = 5 (2 + 3).
- windowEnd = 5, windowSum = 7 (2 + 5), which is >= 7.
  - Update minLength to 2 (unchanged).
  - Subtract element at windowStart (2), windowSum = 5, windowStart = 4.
Final minLength is 2.

Code

Here is what our algorithm will look like:

Python3

. . . .

Complexity Analysis

Time Complexity

Single pass: The algorithm uses a sliding window approach, which involves a single pass through the array. The outer loop runs for each element in the array. This means the outer loop runs $O(N)$ times, where N is the number of elements in the array.
Sliding window adjustment: Inside the outer loop, the inner loop shrinks the window when the window sum becomes greater than or equal to S. Each element is added and removed from the window at most once, so the inner loop runs in $O(N)$ time cumulatively.
Therefore, the overall time complexity is $O(N)$ because both the outer and inner loops together process each element at most twice (once for expanding the window and once for shrinking it).

Overall time complexity: $O(N)$ .

Space Complexity

Additional variables: The algorithm uses a few extra variables (windowSum, minLength, windowStart, and windowEnd), all of which require constant space. No additional data structures are used that depend on the input size.

Overall space complexity: $O(1)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible