educative.io

Time complexity in Smallest Subarray with a given sum (easy)

Courses
,
#1

Hi,

In the solution of Smallest Subarray with a given sum (easy), when while condition is used, how could we be sure the loop runs only once?? If its going to run only once, why not use if condition?

I am trying to understand how we could arrive to conclusion that it could run only once? Please explain

#2

Hi @Krishna_Tej_Chalamal, hope you are doing well.

I think that there is a misunderstanding. The author means that the loop will process each element only once, not run only once. That’s why the complexity can be reduced to O(N) and not O(N+M).

Hope that helps.

Artur Baruchi

#3

Hi @Artur_Baruchi, thanks for the explaining.

I am still not able to catch the point. Could you please explain more about the while loop processing element only once and not run only once?

Regards,
Krishna Tej

#4

Hi @Krishna_Tej_Chalamal

I see your point now. The author’s solution is different and can be a little bit confusing. The thing is, the first for loop is setting the end of the window. The inner while is just for sum the elements from the beginning of the window til the end (which is set by the for loop). Indeed, a given element can be processed more than once (and processed I mean, it can be used as part of the sum of the current window).

Saying that, the while loop will be running to sum the elements and as long the for loop do not reach the end, but the window interval (start - end) will be different every loop.

I give a try to solve this problem myself (I didn’t care for optimizations, but I think it is simpler than the author’s solution) and I used only a single while with the “if’s” and it worked fine. Take a look:

def min_subarray_sum(s, array):
    min_len = float('Inf')
    win_start = 0
    win_end = 0
    while win_start < len(array):
        if sum(array[win_start:win_end]) >= s:
            if len(array[win_start:win_end]) < min_len:
                min_len = len(array[win_start:win_end])
           win_start += 1
        else:
            if win_end < len(array):
                win_end += 1
           else:
                win_start += 1
   return min_len

Hope this helps!

Regards,
Artur Baruchi

Follow me on twitter for coding tips and technical content
twitter.com/abaruchi

1 Like