Be the first user to complete this post

  • 0
Add to List
Medium

476. Find subarray with a sum to given number-2 | Handle negative numbers

Problem: Given an array (positive and negative) and an integer, find the subarray with sum is equal to the given integer. 

Note: This problem is an extension of - find the subarray with sum to a Given Value, in which arrays with negative numbers are not handled. 

Example:

Given input: [25, 12, -14, 22, -19, 15, -10, 23]
K = -11.
Subarray with sum = -11
Output: [-14 22 -19 ]

Given input: [10, 0, -1, 20, 25, 30]
K = 45
Subarray with sum = 45
Output: [20 25]

Approach: 

Given : input[] and K

Idea: We need to find subarray input[a, b] - sum of elements from index a to b  = K. 

input[a, b] = input[0, b] - input[0, a-1]

Steps:

  • Initialize a map which will store the sum up to element at the current index and current index as a value.
  • Initialize i = 0, j = -1.
  • Initialize curr_sum = 0, keep adding elements during iteration.
  • Iterate through array and for  currenct index n,
    • curr_sum = curr_sum +  input[n].
    • Check if curr_sum = K, we have found a subarray and means all the elements till the current element are included, do j = n, and break the loop.
    • Check if the map contains curr_sum - K, if yes then we have found a subarray, get the index from the map for key curr_sum - K and do i = index + 1 and j = n, the elements from index i to j will have sum = K.  
  • Check if j!=-1, means we have found the subarray during iteration. Print the elements from index i to index j. (input[i, j]), else if j==-1 then no subarray exists with sum = K.

Time Complexity: O(N), Space Complexity: O(N)

Output:

Given input: [25, 12, 14, 22, 19, 15, 10, 23]
Subarray with sum = 55
14 22 19
 --------------------------------
Given input: [25, 12, -14, 22, -19, 15, -10, 23]
Subarray with sum = -11
-14 22 -19
 --------------------------------
Given input: [10, 0, -1, 20, 25, 30]
Subarray with sum = 45
20 25