Solution: Smallest Subarray With a Greater Sum

import math

class Solution:
  def findMinSubArray(self, s, arr):
    sum = 0
    j = 0
    min_sum = float('inf')
    for i in range(len(arr)):
      
      sum += arr[i]
      
      while sum >= s:
        diff = i - j + 1
        min_sum = min(min_sum, diff)
        sum -= arr[j]
        j += 1

    # inf happens if we have nothing >= s we want to return 0 not inf
    return min_sum if min_sum != float('inf') else 0 

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

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?

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.

I dont understand the logic behind using the math.in and the integer.max_value. can someone please explain how this works

Can someone explain how did they calculate the time complexity?

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?

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?

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;

}