educative.io

Confusing Comment in Solution and Asymptotic Analysis Issue - Smallest Subarray with Greater Sum

Courses
, ,
#1

Here is the solution given in Python:

import math

def smallest_subarray_sum(s, arr):
  
  min_length = math.inf

  for window_start in range(0, len(arr)):
    window_sum = 0
    window_end = window_start
    # shrink the window as small as possible until the 'window_sum' is smaller than 's'
    while window_end < len(arr):
      window_sum += arr[window_end]  # add the next element
      if window_sum >=s:
        min_length = min(min_length, window_end - window_start + 1)
        break
      window_end += 1     # Sliding the window
      
  if min_length == math.inf:
    return 0
  return min_length

First, the comment below the for loop says: “# shrink the window as small as possible until the ‘window_sum’ is smaller than ‘s’”. However, we are actually growing the window not shrinking it, and checking if the window_sum is >= s. To me, it seems the worst case runtime is closer to O(n^2) in this solution… for instance take arr = [1, 2, 3, 4, 5] and s = [100], then for each element we iterate over (n-i) elements where i is our current index (going from 0 to 4 in the example) and n is the length of the array (which is 5 in our example).

#2

Your conclusion makes sense. The solution runtime appears to be approximately (n^2)/2 (which is O(n^2)). To confirm it, I counted the inner while loop with the input s=10, arr=[0,0,0,0,0,0,0,0,0,0], and the count was 55. With the array of size 1000, the count was 500500.

1 Like
#3

That doesn’t seem to be the latest solution in python, but rather:

import math


def smallest_subarray_sum(s, arr):
  
  min_length = math.inf
  window_sum = 0
  window_start = 0
  for window_end in range(0, len(arr)):
      window_sum += arr[window_end]  # add the next element
    # shrink the window as small as possible until the 'window_sum' is smaller than 's'
      while window_sum >= s:
        min_length = min(min_length, window_end - window_start + 1)
        window_sum -= arr[window_start]
        window_start += 1
      
  if min_length == math.inf:
    return 0
  return min_length


def main():
  print("Smallest subarray length: " + str(smallest_subarray_sum(7, [2, 1, 5, 2, 3, 2])))
  print("Smallest subarray length: " + str(smallest_subarray_sum(8, [3, 4, 1, 1, 6])))
  print("Smallest subarray length: " + str(smallest_subarray_sum(8, [2, 1, 5, 2, 3, 2])))


main()

The worst case runtime for your example (100, [1, 2, 3, 4, 5]) will still be O(N) in this case right?