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.
1 Like
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