Grokking the Coding Interview: The Original Course
Vote

0% completed

​

Solution: Smallest Subarray With a Greater Sum

Problem Statement

Why this is a Sliding Window problem

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

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>

Why this is a Sliding Window problem

What the question saysThe signal it matches
"smallest contiguous subarray whose sum is greater than or equal to" Sthe range is contiguous, and you want the shortest one that satisfies a condition
"an array of positive integers"extending the window can only raise the sum, so shrinking is the only way back
scanning forward from every start until the sum is reachedyour first idea is for each starting index, scan forward

Grow until the condition holds, then pull the left edge in as far as it will go. That is the shrink to the smallest legal window variant.

The closest alternative. The words "positive integers" decide more than they look. A window works because adding a number always increases the sum. Removing one always decreases it.

Allow negative numbers and neither is true. The shrink step becomes wrong. The problem then becomes a Prefix Sum question with a map of running totals. Check the sign of the values before choosing this pattern.

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

mediaLink

The array is [2, 1, 5, 2, 3, 2] and the target is 7. All values are positive, which is what makes a window work: growing it can only raise the sum, and shrinking it can only lower the sum.

1 of 9

Code

Here is what our algorithm will look like:

Python3
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).

Barsik Samogonov

Barsik Samogonov

· a month ago

//Single loop solution with if statements
//Helped me reason about this in a more intuitive way
class Solution {
  findMinSubArray(s, arr) {
    let result = Infinity; 
    let currentWindowSum = arr[0]; 
    for (let windowStart = 0, windowEnd = 0; windowEnd < arr.length;) {
      if (currentWindowSum >= s) {
        if (windowEnd - windowStart + 1 < result) {
          result = windowEnd - windowStart + 1
        }
        currentWindowSum = currentWindowSum - arr[windowStart] 
        windowStart += 1
      } else if (currentWindowSum < s) {
        windowEnd += 1 
        currentWindowSum = currentWindowSum + arr[windowEnd] 
      }
    }
    if (result == Infinity) return 0
    return result 
  };
}
pankajaddi A

pankajaddi A

· 5 months ago

Even i had used if , and was wondering why ? here's the Explanation (AI generated)

The Walk through

Input: arr = [2, 1, 5, 2, 3, 2], S = 7

Step 1: Expanding the window

Your outer for loop expands windowEnd from index 0 to 2:

  • Add 2: windowSum = 2
  • Add 1: windowSum = 3
  • Add 5: windowSum = 8 (Now, windowSum >= 7 is True)

Our current window is [2, 1, 5] (length = 3).

Step 2: The Inner while Loop kicks in

If we used an if statement instead of a while loop, we would just record the length 3, drop the first 2, and move on. But watch what happens because it's a while loop:

  • Iteration 1 of while: * Current window: [2, 1, 5], windowSum = 8.
    • minLength becomes Math.min(MAX, 3) = 3.
    • Shrink from left:
Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

import math

class Solution:
  def findMinSubArray(self, s, arr):
    sum = 0
    j = 0
    min_sum = float('inf')
    for i in range(len(arr)):
      
      sum += arr[i]
      
      while sum >= s:
        diff = i - j + 1
        min_sum = min(min_sum, diff)
        sum -= arr[j]
        j += 1

    # inf happens if we have nothing >= s we want to return 0 not inf
    return min_sum if min_sum != float('inf') else 0
Show 2 replies
K

karrad

· 3 years ago

I think there is a bug in the solution.

The line

min_length = min(min_length, window_end - window_start)

should be

min_length = min(min_length, window_end - window_start + 1)

It works with the +1.

Murthy

Show 2 replies
S

Salah Osman

· 4 years ago

Why would time complexity be O(n+n) instead of maybe something like O(n*n). [1,2,3...infinity], s = infinity. While loop would have to run in the worst case infinity times with each process?

Show 1 reply
A

Anthony DiFede

· 4 years ago

I was using if instead of while, wondering why my length result was wrong. I understand now why shrinking the window until the sum is less than S is important.

Image

Show 1 reply
B

Bryan Pena

· 4 years ago

I dont understand the logic behind using the math.in and the integer.max_value. can someone please explain how this works

Show 3 replies
V

Vatsal Mavani

· 4 years ago

Can someone explain how did they calculate the time complexity?

Show 1 reply
C

Christian Salinas

· 4 years ago

In the python solution, here's a more pythonic way of returning min_length. I also just prefer using float('inf') instead of importing math.

return (min_length if min_length != float('inf') else 0)

J

Jess

· 5 years ago

can someone explain the necessity of the check:

if min_length == math.inf

in the Python3 solution? How would min_length ever be an infinite number in this scenario?

Show 5 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Why this is a Sliding Window problem

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity