Grokking the Engineering Manager Coding Interview
Vote

0% completed

​

Solution: Smallest Subarray With a Greater Sum

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

.....

.....

.....

Like the course? Get enrolled and start learning!
pankajaddi A

pankajaddi A

· 3 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:
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

· 3 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

· 4 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
S

Syed Hassan

· 5 years ago

Could please describe the logic of inner while loop running only once? what is the worst case? Dont you think at worst it can be On2?

Show 1 reply

Reading Progress

0%