Longest Subarray with Given Sum (Positives and Negatives)

Algorithm Steps

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

Longest Subarray with Given Sum using HashMap Code

Python

JavaScript

Java

C++

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))

Longest Subarray with Given Sum (Positives and Negatives) - Optimal Approach

Algorithm Steps

Longest Subarray with Given Sum using HashMap Code