I think the runtime is O(n*n) since the inner loop is not guaranteed to run only once.

for example if s =100 and the array is [1,1,1,…1,1,100] the inner while would run x times, with x being the number of 1’s

as such it isn’t O(n)

@Talha_Suboor As written in the explanation of this lesson, “The outer `for`

loop runs for all elements, and the inner `while`

loop processes each element only once; therefore, the time complexity of the algorithm will be O(N+N), which is asymptotically equivalent to O(N).”

We can see from this explanation that the outer `for`

loop is running `N`

times, and the inner while loop is going to process each element only once because the window size is shrinking with each iteration. so even if `s =100`

and the array is `[1,1,1,…1,1,100]`

the inner `while`

loop would run x times, with `x`

being the number of `1’s`

. so the time complexity will be

`for loop = N`

`While loop = N`

hence `N + N`

would still be `N`

.

Great explanation.

I think the trick to understanding the time complexity lies in understanding that “the inner while loop processes each element only once”, and as you also added, “because the window size is shrinking with each iteration”.

Although there is a while loop inside a for loop, each element in the array does not get processed n times, therefore, O(n*n) would not make sense.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively

Lesson: Smallest Subarray With a Greater Sum (easy) - Grokking the Coding Interview: Patterns for Coding Questions