sliding window algorithm - condition for start < n

Question

Below is a sliding window solution for finding the minimum length subarray with a sum greater than x from geeksforgeeks (https://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/)

# O(n) solution for finding smallest 
# subarray with sum greater than x 

# Returns length of smallest subarray 
# with sum greater than x. If there  
# is no subarray with given sum, then 
# returns n + 1 
def smallestSubWithSum(arr, n, x): 

    # Initialize current sum and minimum length 
    curr_sum = 0
    min_len = n + 1

    # Initialize starting and ending indexes 
    start = 0
    end = 0
    while (end < n): 

        # Keep adding array elements while current 
        # sum is smaller than x 
        while (curr_sum <= x and end < n): 
            curr_sum += arr[end] 
            end+= 1

        # If current sum becomes greater than x. 
        while (curr_sum > x and start < n): 

            # Update minimum length if needed 
            if (end - start < min_len): 
                min_len = end - start  

            # remove starting elements 
            curr_sum -= arr[start] 
            start+= 1

    return min_len  

I have tested that this solution can work, but I'm confused by why in the last while loop, start is checked for being less than n - wouldn't you want it to be less than end, otherwise start can go beyond end, which doesn't really make sense to me?

Answer 1

Since curr_sum was built by adding elements up to end, it will get to zero (or smaller than x) before start can reach end. This will exit the while loop. This also implies that the algorithm will probably not work with negative numbers in the array.

Personally I would have written it a little differently. Here's an example with the negative number condition taken into account:

def minSub(arr,x):
    subTotal      = 0
    size,minSize  = 0,len(arr)+1
    start         = iter(arr)
    for value in arr:
        subTotal += value
        size     += 1
        while subTotal not in range(0,x+1):
            if subTotal>x :
                minSize = min(minSize,size)
            subTotal -= next(start,0)
            size     -= 1
    return minSize

output:

arr  = [1, 4, 45, 6, 0, 19] 
x    = 51 
print(minSub(arr,x)) #3

arr = [-8, 1, 4, -1, 3, -6]
x   = 6 
print(minSub(arr,x)) # 4

arr = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
x   = 280 
print(minSub(arr,x)) # 4

arr = [1, 10, 5, 2, 7]
x   = 9
print(minSub(arr,x)) # 1

arr = [1, 2, 4]
x   = 8
print(minSub(arr,x)) # 4