Find Longest Subarray with Given Sum using HashMap - Optimal Solution

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers (which may include positive numbers, negative numbers, or zeros) and a target sum k, your task is to find the length of the longest contiguous subarray that adds up exactly to k.

The subarray must be continuous, and if multiple such subarrays exist, return the length of the longest one.

If no such subarray exists, return 0.

Examples❯

Input Array Target Sum (k) Longest Subarray Length Description
[1, 2, 3, -2, 1] 4 4 Subarray [1, 2, 3, -2] gives sum 4Visualization
[10, -10, 10, -10, 10] 0 4 Subarray [10, -10, 10, -10] gives sum 0Visualization
[5, 1, 1, 3, -2, 1] 4 5 Subarray [1, 1, 3, -2, 1] is the longest that gives sum 5Visualization
[1, 2, 3] 7 0 No subarray has sum 7Visualization
[0, 0, 0, 0] 0 4 Entire array sums to 0Visualization
[3, 4, -7, 1, 2] 0 3 Subarray [3, 4, -7] gives sum 0Visualization
[] 0 0 Empty array, so no subarray existsVisualization

Solution❯

Understanding the Problem Step-by-Step

We are given an array that can contain both positive and negative numbers, and a target sum k. Our goal is to find the length of the longest subarray whose elements sum up exactly to k.

Let’s say the input is:

arr = [1, -1, 5, -2, 3], k = 3

We are to find the longest continuous section (subarray) in arr where the numbers add up to 3. The expected output is 4 because the subarray [1, -1, 5, -2] adds up to 3 and has length 4.

Step-by-Step Strategy

We will use the concepts of prefix sum and a hash map to solve this efficiently.

The idea is to keep a running total (prefix sum) while iterating through the array. For each index i, we calculate the sum from the beginning up to that index, called curr_sum. If we have seen a previous prefix sum value such that:

curr_sum - previous_sum = k

then the subarray between those two indices has a total sum of k.

We store the first occurrence of each prefix sum in a hash map, so we can quickly check if a subarray with sum k ends at the current index.

Working Through the Example

arr = [1, -1, 5, -2, 3], k = 3
  • At index 0: curr_sum = 1 → not equal to k, store (1, 0)
  • At index 1: curr_sum = 0 → not equal to k, store (0, 1)
  • At index 2: curr_sum = 5 → 5 - 3 = 2, not in map, store (5, 2)
  • At index 3: curr_sum = 3 → 3 - 3 = 0, 0 is in map at index 1 → length = 3 - 1 = 2
  • At index 4: curr_sum = 6 → 6 - 3 = 3, 3 is in map at index 3 → length = 4 - 3 = 1
  • Also, at index 4, curr_sum = 6 is a new sum → store (6, 4)
  • Final answer is max length = 4 (from index 0 to 3)

Edge Case Considerations

Case 1: Prefix sum equals k

If curr_sum itself is equal to k at any index, it means the subarray from index 0 to current index is valid.

Case 2: Target sum is 0

Even if the target is 0, the logic works. We just look for previously seen prefix sums that equal the current prefix sum.

Case 3: All elements are zero and target is zero

The entire array is valid. For example, [0, 0, 0] with k = 0 should return 3.

Case 4: No valid subarray found

If we go through the array and never find a suitable subarray, the answer is 0.

Case 5: Empty array

No elements to process means no valid subarray. So, return 0.

Instead of checking every possible subarray, which takes O(n^2) time, we process the array once and use a hash map to find matching prefix sums. This brings down the time complexity to O(n), making it highly efficient even for large arrays.

This approach works well even when the array has negative numbers, which is a limitation for techniques like the sliding window method.

Algorithm Steps❯

  1. Given an array arr of integers (positive, negative, or zero) and a target sum k.
  2. Initialize prefix_sum = 0, max_len = 0, and an empty hash_map to store the first occurrence of each prefix sum.
  3. Iterate through the array with index i:
  4. → Add arr[i] to prefix_sum.
  5. → If prefix_sum == k, update max_len = i + 1.
  6. → If prefix_sum - k exists in hash_map, calculate the length and update max_len accordingly.
  7. → If prefix_sum is not in hash_map, store prefix_sum with index i.
  8. Return max_len after the loop ends.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#define MAX 10000

int longestSubarrayWithSumK(int arr[], int n, int k) {
    int prefixSum = 0, maxLen = 0;
    int prefixMap[MAX];
    for (int i = 0; i < MAX; i++) prefixMap[i] = -1;

    for (int i = 0; i < n; i++) {
        prefixSum += arr[i];

        if (prefixSum == k)
            maxLen = i + 1;

        if (prefixSum - k >= 0 && prefixMap[prefixSum - k] != -1) {
            int len = i - prefixMap[prefixSum - k];
            if (len > maxLen) maxLen = len;
        }

        if (prefixSum >= 0 && prefixMap[prefixSum] == -1) {
            prefixMap[prefixSum] = i;
        }
    }
    return maxLen;
}

int main() {
    int arr[] = {1, -1, 5, -2, 3};
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Length of Longest Subarray: %d\n", longestSubarrayWithSumK(arr, n, k));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)Each element is processed once, and HashMap lookups and insertions are O(1) on average. In the best case, the prefix sum quickly matches the target early in the array.
Average CaseO(n)The algorithm traverses the entire array once, using a HashMap for fast prefix sum lookups and updates.
Worst CaseO(n)Even in the worst case, the algorithm completes a single pass over the array, with constant-time operations per element.

Space Complexity❯

O(n)

Explanation: In the worst case, each prefix sum is unique and stored in the HashMap, resulting in O(n) additional space.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...