Four Algorithmic Patterns That Solve Most Subarray Problems Efficiently

Subarray problems are a staple of coding interviews and data structures courses, but brute-force approaches using nested loops quickly become inefficient at scale, running at O(n²) time complexity. A small set of recurring patterns can solve the most common variants in linear time: Kadane's Algorithm for maximum sum, tracking both maximum and minimum for maximum product, and Prefix Sum or Prefix XOR combined with a HashMap for counting subarrays with a target sum or XOR value. The Prefix Sum with HashMap technique is preferred over sliding window when arrays contain negative numbers, since negative values break the assumption that expanding a window always increases the sum. The same mathematical structure underlying Prefix Sum applies directly to XOR problems, with only the arithmetic operation changing. Understanding the reasoning behind each pattern, rather than memorising code, allows developers to adapt these solutions across a wide range of subarray variants.