Longest Subarray with Given Sum (Positives and Negatives)

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.

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.

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.

#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;
}

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int longestSubarrayWithSumK(vector<int>& arr, int k) {
    unordered_map<int, int> prefixMap;
    int prefixSum = 0, maxLen = 0;

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

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

        if (prefixMap.find(prefixSum - k) != prefixMap.end()) {
            maxLen = max(maxLen, i - prefixMap[prefixSum - k]);
        }

        if (prefixMap.find(prefixSum) == prefixMap.end()) {
            prefixMap[prefixSum] = i;
        }
    }

    return maxLen;
}

int main() {
    vector<int> arr = {1, -1, 5, -2, 3};
    int k = 3;
    cout << "Length of Longest Subarray: " << longestSubarrayWithSumK(arr, k) << endl;
    return 0;
}

def longest_subarray_with_sum_k(arr, k):
    prefix_sum = 0
    max_len = 0
    prefix_map = {}

    for i in range(len(arr)):
        prefix_sum += arr[i]

        if prefix_sum == k:
            max_len = i + 1

        if (prefix_sum - k) in prefix_map:
            max_len = max(max_len, i - prefix_map[prefix_sum - k])

        if prefix_sum not in prefix_map:
            prefix_map[prefix_sum] = i

    return max_len

# Sample Input
arr = [1, -1, 5, -2, 3]
k = 3
print("Length of Longest Subarray:", longest_subarray_with_sum_k(arr, k))

import java.util.*;

public class LongestSubarraySumK {
    public static int longestSubarrayWithSumK(int[] arr, int k) {
        Map<Integer, Integer> prefixMap = new HashMap<>();
        int prefixSum = 0, maxLen = 0;

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

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

            if (prefixMap.containsKey(prefixSum - k)) {
                maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum - k));
            }

            prefixMap.putIfAbsent(prefixSum, i);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] arr = {1, -1, 5, -2, 3};
        int k = 3;
        System.out.println("Length of Longest Subarray: " + longestSubarrayWithSumK(arr, k));
    }
}

function longestSubarrayWithSumK(arr, k) {
    let prefixSum = 0;
    let maxLen = 0;
    const prefixMap = new Map();

    for (let i = 0; i < arr.length; i++) {
        prefixSum += arr[i];

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

        if (prefixMap.has(prefixSum - k)) {
            maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum - k));
        }

        if (!prefixMap.has(prefixSum)) {
            prefixMap.set(prefixSum, i);
        }
    }

    return maxLen;
}

// Sample Input
const arr = [1, -1, 5, -2, 3];
const k = 3;
console.log('Length of Longest Subarray:', longestSubarrayWithSumK(arr, k));

package main

import (
    "fmt"
)

func longestSubarrayWithSumK(arr []int, k int) int {
    prefixMap := make(map[int]int)
    prefixSum := 0
    maxLen := 0

    for i := 0; i < len(arr); i++ {
        prefixSum += arr[i]

        if prefixSum == k {
            maxLen = i + 1
        }

        if idx, ok := prefixMap[prefixSum - k]; ok {
            if i - idx > maxLen {
                maxLen = i - idx
            }
        }

        if _, exists := prefixMap[prefixSum]; !exists {
            prefixMap[prefixSum] = i
        }
    }

    return maxLen
}

func main() {
    arr := []int{1, -1, 5, -2, 3}
    k := 3
    fmt.Println("Length of Longest Subarray:", longestSubarrayWithSumK(arr, k))
}

use std::collections::HashMap;

fn longest_subarray_with_sum_k(arr: Vec<i32>, k: i32) -> usize {
    let mut prefix_map = HashMap::new();
    let mut prefix_sum = 0;
    let mut max_len = 0;

    for (i, &val) in arr.iter().enumerate() {
        prefix_sum += val;

        if prefix_sum == k {
            max_len = i + 1;
        }

        if let Some(&idx) = prefix_map.get(&(prefix_sum - k)) {
            max_len = max_len.max(i - idx);
        }

        prefix_map.entry(prefix_sum).or_insert(i);
    }
    max_len
}

fn main() {
    let arr = vec![1, -1, 5, -2, 3];
    let k = 3;
    println!("Length of Longest Subarray: {}", longest_subarray_with_sum_k(arr, k));
}

fun longestSubarrayWithSumK(arr: IntArray, k: Int): Int {
    val prefixMap = mutableMapOf<Int, Int>()
    var prefixSum = 0
    var maxLen = 0

    for (i in arr.indices) {
        prefixSum += arr[i]

        if (prefixSum == k) {
            maxLen = i + 1
        }

        if (prefixMap.containsKey(prefixSum - k)) {
            maxLen = maxOf(maxLen, i - prefixMap[prefixSum - k]!!)
        }

        if (!prefixMap.containsKey(prefixSum)) {
            prefixMap[prefixSum] = i
        }
    }
    return maxLen
}

fun main() {
    val arr = intArrayOf(1, -1, 5, -2, 3)
    val k = 3
    println("Length of Longest Subarray: ${longestSubarrayWithSumK(arr, k)}")
}

func longestSubarrayWithSumK(_ arr: [Int], _ k: Int) -> Int {
    var prefixMap = [Int: Int]()
    var prefixSum = 0
    var maxLen = 0

    for i in 0..<arr.count {
        prefixSum += arr[i]

        if prefixSum == k {
            maxLen = i + 1
        }

        if let index = prefixMap[prefixSum - k] {
            maxLen = max(maxLen, i - index)
        }

        if prefixMap[prefixSum] == nil {
            prefixMap[prefixSum] = i
        }
    }

    return maxLen
}

let arr = [1, -1, 5, -2, 3]
let k = 3
print("Length of Longest Subarray:", longestSubarrayWithSumK(arr, k))

function longestSubarrayWithSumK(arr: number[], k: number): number {
    let prefixSum = 0;
    let maxLen = 0;
    const prefixMap = new Map<number, number>();

    for (let i = 0; i < arr.length; i++) {
        prefixSum += arr[i];

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

        if (prefixMap.has(prefixSum - k)) {
            maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum - k)!);
        }

        if (!prefixMap.has(prefixSum)) {
            prefixMap.set(prefixSum, i);
        }
    }

    return maxLen;
}

const arr: number[] = [1, -1, 5, -2, 3];
const k = 3;
console.log('Length of Longest Subarray:', longestSubarrayWithSumK(arr, k));

Time complexity

Space complexity

O(n)

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