Updated 3 years ago
Subarray with Given Sum
The following question was asked during a coding interview for Amazon:
You are given an array of numbers (non-negative). Find a continuous subarray of the list which adds up to a given sum.
# Solve the problem here
arr0 = [1, 7, 4, 2, 1, 3, 11, 5]
target0 = 10
output0 = 2, 6
def subarray_sum(arr, target):
pass
"""
1. Generaic array wherer the subarray is in the center
2. Subarray could be at the start
3. Subarray could be at the end
4. There is no subarray that adds up to 10
5. You have a few zeros in the list
6. There are multiple subarrays with the same sum
7. The array is empty
8. The subarray is a single element
"""
def subarray_sum1(arr, target):
n = len(arr)
# i goes from 0 to n-1
for i in range(0, n):
# j goes from i to n
for j in range(i, n+1):
# check if subarray sum equal target
if sum(arr[i:j]) == target:
# answer found
return i,j
return None, None
# maintain a running sum for inner loop
# when sum exceeds target, break inner loop
def subarray_sum2(arr, target):
n = len(arr)
# i goes from 0 to n-1
for i in range(0, n):
s = 0 # running sum
for j in range(i, n+1):
if s == target:
return i,j
elif s > target:
break
if j < n:
s += arr[j]
return None, None
def subarray_sum3(arr, target):
n = len(arr)
i, j, s = 0, 0, 0
while i < n and j < n+1:
if s == target:
return i,j
elif s < target:
if j < n:
s += arr[j]
j += 1
else:
s -= arr[i]
i += 1
return None, None
# Test the solution here
subarray_sum3(arr0, target0)
(2, 6)