Jovian
Sign In
import jovian

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.

alt

Solve the problem here

# Brute Force

def subarray_slow(arr, target):
    # Start the for loop for starting index of solution
    for i in range(len(arr)):
        s = 0 # initial sum
        
        # Second index to find the required array
        for j in range(i, len(arr)):
            # adding the element to the sum for current arr
            s += arr[j]
                
            # Checking if sum is equal
            if s == target:
                return arr[i : j+1]
            
            # if sum exceeds the target then we can terminate the loop
            if s > target:
                break
            
    # No array found with sum equal to target
    return []

Time Complexity : O(n2)O(n^2)