How a Prefix Sum and Hashmap Cut a Coding Problem from O(n²) to O(n)

A developer tackled the classic 'longest subarray with sum equal to k' problem, initially using a brute-force approach with two nested loops that timed out on large inputs of 100,000 elements. The breakthrough came by shifting focus to prefix sums, where the sum of any subarray can be derived from the difference of two cumulative totals. A hashmap is used to store the earliest index at which each prefix sum was seen, allowing the algorithm to find valid subarrays in a single linear pass. Each step requires only a constant-time hashmap lookup, bringing overall time complexity down from O(n²) to O(n). The approach illustrates a broader problem-solving principle: reusing previously computed work rather than recalculating it from scratch.