Longest Subarray with Sum K | Brute, Better, and Optimal Approaches

This chapter covers how to find the length of the longest contiguous subarray that sums to a given value $K$. We will explore the evolution of solutions from a naive $O(N^3)$ brute-force approach to an $O(N)$ optimal sliding window technique, highlighting critical edge cases involving zeros and negative numbers.

1. Understanding Subarrays vs. Subsequences

Before solving the problem, we must establish a precise definition of a subarray and contrast it with a subsequence.

• Subarray: A contiguous, unbroken part of an array. The elements must be adjacent to one another in the original array without any gaps.
• Subsequence: A sequence derived from the array by deleting some or no elements without changing the order of the remaining elements (elements do not need to be contiguous).

Real-World Analogy

Think of a train. A subarray is like a set of connected train cars (e.g., cars 2, 3, and 4). You cannot skip a car and call it contiguous. A subsequence is like selecting passengers from cars 1, 3, and 5; they maintain their relative order from front to back, but they are not sitting in adjacent cars.

Visual Comparison

Given the array: [1, 2, 3, 1, 1, 1]

2. The Core Mental Model: Reverse Mathematics

To optimize beyond brute force, we use a mathematical relationship based on prefix sums.

Suppose we are standing at index $i$, and the sum of all elements from the beginning of the array up to index $i$ is $x$ (this is the prefix sum). We want to find if there is a contiguous subarray ending at index $i$ that sums to exactly $K$.

If such a subarray exists, the remaining prefix of the array must sum to exactly $x - K$.

The Reverse Engineering Formula

If we store the prefix sums we have seen so far in a hash map, we can check if we have ever encountered a prefix sum of $x - K$. If we did (say, at index $j$), then the subarray from index $j + 1$ to $i$ has a sum of exactly $K$. Its length is:

3. Brute Force Approach (Evolution from $O(N^3)$ to $O(N^2)$)

The most intuitive way to solve this problem is to generate every possible subarray, calculate its sum, and track the maximum length among those that sum to $K$.

Naive $O(N^3)$ Implementation

We use three nested loops:

1. The outer loop i marks the starting index of the subarray.
2. The middle loop j marks the ending index of the subarray.
3. The inner loop k iterates from i to j to calculate the sum.

// Naive O(N^3) Brute Force
int maxLen = 0;
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        long long sum = 0;
        for (int k = i; k <= j; k++) {
            sum += arr[k];
        }
        if (sum == K) {
            maxLen = max(maxLen, j - i + 1);
        }
    }
}

Optimized $O(N^2)$ Brute Force

We can eliminate the third loop. As the pointer j moves to the right, we do not need to recompute the sum from scratch. We can simply add the new element arr[j] to the running sum of the previous subarray.

// Optimized O(N^2) Brute Force
int maxLen = 0;
for (int i = 0; i < n; i++) {
    long long sum = 0;
    for (int j = i; j < n; j++) {
        sum += arr[j];
        if (sum == K) {
            maxLen = max(maxLen, j - i + 1);
        }
    }
}

4. Better Approach: Hashing (Prefix Sum)

By applying our Reverse Mathematics mental model, we can use a hash map to store the prefix sums and their corresponding indices. This allows us to find the required prefix sum $x - K$ in $O(1)$ average time.

Hashing Algorithm Steps

1. Initialize an empty hash map preSumMap to store (prefix_sum, index).
2. Maintain a running sum initialized to 0 and maxLen initialized to 0.
3. Iterate through the array:
   • Add the current element to sum.
   • If sum == K, update maxLen = i + 1 (since the subarray starts from index 0).
   • Calculate the remaining sum needed: rem = sum - K.
   • If rem exists in the map, update maxLen with the maximum of its current value and i - preSumMap[rem].
   • If the current sum is not already in the map, add it with its index i.

C++ Implementation

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int getLongestSubarray(vector<int>& a, long long k) {
    unordered_map<long long, int> preSumMap;
    long long sum = 0;
    int maxLen = 0;
    int n = a.size();

    for (int i = 0; i < n; i++) {
        sum += a[i];

        // Case 1: Subarray starts from index 0
        if (sum == k) {
            maxLen = max(maxLen, i + 1);
        }

        // Case 2: Check if (sum - k) exists in map
        long long rem = sum - k;
        if (preSumMap.find(rem) != preSumMap.end()) {
            int len = i - preSumMap[rem];
            maxLen = max(maxLen, len);
        }

        // Case 3: Only add sum to map if it doesn't already exist
        if (preSumMap.find(sum) == preSumMap.end()) {
            preSumMap[sum] = i;
        }
    }
    return maxLen;
}

5. The Zero/Negative Edge Case & Map Update Pitfall

A common mistake is to update the index of a prefix sum in the map every time we see it. This breaks the algorithm when the array contains zeros or negative numbers.

Why We Must Not Re-Update the Map

To find the longest subarray, we want the starting index $j$ of our prefix sum $x - K$ to be as far left as possible. If we update the map with a newer index for an existing prefix sum, we push $j$ to the right, which decreases the length of the resulting subarray.

Dry Run Example

Let's trace the array [2, 0, 0, 3] with $K = 3$.

Index:    0    1    2    3
Array:  [ 2,   0,   0,   3 ]

Incorrect Trace (Updating the map on duplicate sums):

1. i = 0: sum = 2. Map: {2: 0}
2. i = 1: sum = 2. Map updated to {2: 1} (Overwritten!)
3. i = 2: sum = 2. Map updated to {2: 2} (Overwritten!)
4. i = 3: sum = 5. rem = 5 - 3 = 2.
   • We look up 2 in the map. It returns index 2.
   • length = i - map[2] = 3 - 2 = 1 (Subarray [3]).

Correct Trace (Keeping the leftmost index):

1. i = 0: sum = 2. Map: {2: 0}
2. i = 1: sum = 2. Map already contains 2, so do not update.
3. i = 2: sum = 2. Map already contains 2, so do not update.
4. i = 3: sum = 5. rem = 5 - 3 = 2.
   • We look up 2 in the map. It returns the leftmost index 0.
   • length = i - map[2] = 3 - 0 = 3 (Subarray [0, 0, 3]).

Note: This hashing approach is the optimal solution if the array contains negative numbers, as the sliding window approach fails when sums do not increase monotonically.

6. Optimal Approach for Positives & Zeros (Two-Pointer / Sliding Window)

If the array contains only positive numbers and zeros, we can use a highly optimized two-pointer (sliding window) approach. This eliminates the space overhead of a hash map.

Why It Works for Positives

Because all elements are non-negative, moving the right pointer to the right is guaranteed to either increase or maintain the window sum. If the sum exceeds $K$, we can safely shrink the window from the left to decrease the sum.

Sliding Window Algorithm Steps

1. Initialize left = 0, right = 0, sum = arr[0], and maxLen = 0.
2. While right < n:
   • If sum > K, shrink the window from the left by subtracting arr[left] from sum and incrementing left until sum <= K (and left <= right).
   • If sum == K, update maxLen = max(maxLen, right - left + 1).
   • Increment right. If right < n, add arr[right] to sum.

C++ Implementation

#include <vector>
#include <algorithm>

using namespace std;

int getLongestSubarrayOptimal(vector<int>& a, long long k) {
    int left = 0, right = 0;
    long long sum = a[0];
    int maxLen = 0;
    int n = a.size();

    while (right < n) {
        // Shrink the window from the left if sum exceeds k
        while (left <= right && sum > k) {
            sum -= a[left];
            left++;
        }

        // Check if we found a valid subarray
        if (sum == k) {
            maxLen = max(maxLen, right - left + 1);
        }

        // Move the right pointer forward
        right++;
        if (right < n) {
            sum += a[right];
        }
    }
    return maxLen;
}

7. Complexity Analysis & Comparison

The choice of the optimal algorithm depends entirely on the constraints of the input array (whether it contains negative numbers).

Why is the Two-Pointer Time Complexity $O(N)$ and not $O(N^2)$?

Even though there is a nested while loop to shrink the window, the left pointer only moves forward and never resets. In the worst-case scenario, both the right pointer and the left pointer will traverse the array exactly once. This results in at most $2N$ operations, which simplifies to $O(N)$.

8. Complete Flow Walkthrough (Two-Pointer)

Let's trace the optimal two-pointer approach on the following array with $K = 6$:

Array: [ 1, 2, 3, 1, 1, 1 ]
K = 6

9. Summary and Key Takeaways

• Subarrays are contiguous: A subarray must represent an uninterrupted block of elements from the original array.
• The $O(N^2)$ optimization: You can optimize the brute-force approach by accumulating the sum as the right boundary of the subarray expands, eliminating an inner loop.
• Prefix Sum Hashing: The core formula $x - K$ allows us to look backward in time to see if a matching subarray exists ending at our current index.
• The Map Update Trap: When using hashing, never overwrite an existing prefix sum in the map. Keeping the earliest (leftmost) index guarantees the longest subarray length.
• Negatives require Hashing: The sliding window approach fails when negative numbers are present because the prefix sum does not grow monotonically. Hashing is the optimal approach for arrays with negative numbers.
• Two-Pointer is optimal for positives: When the array contains only positives and zeros, the two-pointer sliding window approach achieves $O(N)$ time complexity and $O(1)$ auxiliary space.
• Amortized $O(N)$ complexity: The nested loop in the sliding window approach does not make it $O(N^2)$ because both pointers only move forward, resulting in a maximum of $2N$ total steps.