Grokking the Coding Interview: Patterns for Coding Questions

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!
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
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
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
S

Syed Hassan

· 5 years ago

I think there is a better solution for

Smallest Subarray with a Greater Sum (easy)

We dont have to use two loops, even though the inner one runs only once. Can you please suggest if this function is ok? public int smallest(int[] array , int tarSum) {

int smallest_Elements = 0; int sum=0; int startPtr = 0; // O (N) for(int endPtr =0;endPtr=tarSum) { int currentElements = (endPtr - startPtr)+1; if(smallest_Elements==0 || currentElementsendPtr) { endPtr = startPtr; endPtr--; } }

}

return smallest_Elements;

}

Show 1 reply
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
F

farhad nooralahzadeh

· 5 years ago

I think the solution for the smallest subarray with a given sum has a bug. We are incrementing the window end after the if or while so there is no chance to catch the min_lenght=2 in the example

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