educative.io

Educative

Changing the constraint

What if the constraint that the numbers inside the array should be positive is removed and we might also include negative numbers. This solution clearly won’t work. What is the alternative solution which works for positive as well as negative integers, not just positive integers?

HI @Jibran_Mohammad,

This algorithm in every provided language also works for negative numbers. for example, we can take the code for python and print the second sample output provided:

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(8, [3, 4, 1, 1, 6])))
main()

Here the output given is :

Smallest subarray length: 3

Here either

[3, 4, 1] or [1, 1, 6]

can be selected as the smallest sub-arrays.

If we change the array in the main function to

print("Smallest subarray length: " + str(smallest_subarray_sum(8, [3, 4, -1, 1, 6])))

the output would be

Smallest subarray length: 4

as [4, -1, 1, 6] would be selected as it is the only sub-array equal or greater to the target sum.
So negative numbers are accounted for in this lesson.

Thank you for using Educative, Let us know if you have any more confusions.

Thanks, Moeel for replying. Can you dry run this algorithm on the input [-3,-2,0,1,2,3] with the sum of 3. If I am not mistaken the algorithm gives output as 0 but should be 1, because the smallest subarray with a sum greater than or equal to 3 is [3]. This element is present in the last index. Can you explain it?

Hello @Jibran_Mohammad,

You are correct this code does not accommodate all edge cases, it runs on negative numbers if they occur in between, but this code works if the sum is positive only. one suggestion to handle this constraint, taking python as an example, is to add conditions to handle negative numbers

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)):

      if arr[window_end] <=0:  # if negative numbern, then we ignore
        continue
      else:
        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)

        if arr[window_start]<0: # if negative number found, we ignore
          pass
        else:
          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(3, [-3, -2, 0, 1, 2, 3])))
  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()

This also has some constraints, such as the target number must be greater than 0.

1 Like