|
Be the first user to complete this post
|
Add to List |
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