{"id":6126,"date":"2025-01-05T19:53:04","date_gmt":"2025-01-05T19:53:04","guid":{"rendered":"https:\/\/algocademy.com\/blog\/mastering-subarray-problem-solving-techniques-a-comprehensive-guide\/"},"modified":"2026-10-15T12:51:16","modified_gmt":"2026-10-15T12:51:16","slug":"mastering-subarray-problem-solving-techniques-a-comprehensive-guide","status":"publish","type":"post","link":"https:\/\/algocademy.com\/blog\/mastering-subarray-problem-solving-techniques-a-comprehensive-guide\/","title":{"rendered":"Subarray Problems: Sliding Window, Kadane, Prefix Sum"},"content":{"rendered":"

A subarray is a contiguous slice of an array, and almost every subarray problem is solved by one of four techniques. Use a sliding window<\/strong> when the values are non-negative or the window has a fixed size, Kadane’s algorithm<\/strong> for the best-sum subarray, prefix sums with a hash map<\/strong> when negatives are allowed and you need a target sum, and binary search on the answer<\/strong> when you must split an array into k pieces. This guide shows how to tell them apart, with code that has been run.<\/p>\n

A subarray is not a subsequence. For [1, 2, 3, 4]<\/code>, [2, 3]<\/code> is a subarray, but [1, 3]<\/code> is not because it skips an element. An array of length n has n(n+1)\/2 subarrays, which is why checking all of them is O(n2<\/sup>) at best.<\/p>\n

Which technique fits? A quick decision table<\/h2>\n\n\n\n\n\n\n\n\n\n\n
The problem says<\/th>\nTechnique<\/th>\nTime<\/th>\n<\/tr>\n<\/thead>\n
Best sum (or product) of any subarray<\/td>\nKadane’s algorithm<\/td>\nO(n)<\/td>\n<\/tr>\n
Best subarray of exactly k elements<\/td>\nFixed sliding window<\/td>\nO(n)<\/td>\n<\/tr>\n
Longest or shortest subarray with a condition, all values non-negative (or a count\/distinct-value condition)<\/td>\nVariable sliding window<\/td>\nO(n)<\/td>\n<\/tr>\n
Number of subarrays with sum k, negatives allowed<\/td>\nPrefix sums + hash map<\/td>\nO(n)<\/td>\n<\/tr>\n
Many range-sum queries on a fixed array<\/td>\nPrefix sums<\/td>\nO(n) build, O(1) per query<\/td>\n<\/tr>\n
Split into k subarrays, minimize the largest sum<\/td>\nBinary search on the answer<\/td>\nO(n log(sum))<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The most common mistake is reaching for a sliding window when the array contains negative numbers. A window works by saying “adding an element can only increase the sum, so if the sum is too big, shrink from the left”. With negatives that statement is false, and the window gives wrong answers.<\/p>\n

Brute force: the baseline to state first<\/h2>\n

In an interview, say the brute force out loud first, then improve it. Fix the start index, extend the end index, and keep a running sum so you never re-add the same elements:<\/p>\n

def max_sum_brute(a):\n    best = a[0]\n    for i in range(len(a)):\n        s = 0\n        for j in range(i, len(a)):\n            s += a[j]\n            best = max(best, s)\n    return best\n\nprint(max_sum_brute([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6\n<\/code><\/pre>\n
This is O(n2<\/sup>) time and O(1) space. Calling sum(a[i:j+1])<\/code> inside the inner loop, as many tutorials do, makes it O(n3<\/sup>) and is a red flag in an interview.<\/p>\n
Kadane’s algorithm: maximum sum subarray<\/h2>\n
At each index, the best subarray ending here<\/em> is either the element alone or the element added to the best subarray ending at the previous index. If the previous best is negative, drop it and start fresh.<\/p>\n
def kadane(a):\n    cur = best = a[0]\n    for x in a[1:]:\n        cur = max(x, cur + x)\n        best = max(best, cur)\n    return best\n\nprint(kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6\n<\/code><\/pre>\n
Trace on [-2, 1, -3, 4, -1, 2, 1, -5, 4]<\/code>:<\/p>\n\n\n\n\n\n\n
x<\/th>\n-2<\/th>\n1<\/th>\n-3<\/th>\n4<\/th>\n-1<\/th>\n2<\/th>\n1<\/th>\n-5<\/th>\n4<\/th>\n<\/tr>\n<\/thead>\n
cur (best ending here)<\/td>\n-2<\/td>\n1<\/td>\n-2<\/td>\n4<\/td>\n3<\/td>\n5<\/td>\n6<\/td>\n1<\/td>\n5<\/td>\n<\/tr>\n
best so far<\/td>\n-2<\/td>\n1<\/td>\n1<\/td>\n4<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n6<\/td>\n6<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The answer is 6, the subarray [4, -1, 2, 1]<\/code>. It runs in O(n) time and O(1) space. Initialize with a[0]<\/code>, not 0, so an all-negative array returns its largest element instead of an empty sum. The same idea, tracking both a maximum and a minimum because a negative flips them, solves Maximum Product Subarray. There is a dedicated walkthrough in Kadane’s algorithm: the maximum subarray problem<\/a>.<\/p>\n
Sliding window<\/h2>\n
A window is a pair of indices, left<\/code> and right<\/code>, with a running value for what is inside. Each element enters once and leaves at most once, so the total work is O(n) even though there is a loop inside a loop.<\/p>\n
Fixed size: best sum of k consecutive elements<\/h3>\n
Add the new element on the right, subtract the one that fell off the left:<\/p>\n
def max_sum_k(a, k):\n    s = sum(a[:k])\n    best = s\n    for i in range(k, len(a)):\n        s += a[i] - a[i - k]\n        best = max(best, s)\n    return best\n\nprint(max_sum_k([2, 1, 5, 1, 3, 2], 3))  # 9  (5 + 1 + 3)\n<\/code><\/pre>\n
Variable size: shortest subarray with sum at least target<\/h3>\n
Grow the window with right<\/code>. While the condition holds, record the length and shrink from the left. This is LeetCode 209 and it requires non-negative values:<\/p>\n
def min_len_at_least(target, a):\n    left = s = 0\n    best = float('inf')\n    for right, x in enumerate(a):\n        s += x\n        while s >= target:\n            best = min(best, right - left + 1)\n            s -= a[left]\n            left += 1\n    return 0 if best == float('inf') else best\n\nprint(min_len_at_least(7, [2, 3, 1, 2, 4, 3]))  # 2  ([4, 3])\n<\/code><\/pre>\n
The template is always the same: expand, then shrink while the window is invalid (or while it is valid, if you want the shortest). What changes between problems is the thing you keep inside the window: a sum, a count of distinct values, a frequency map. For more variants see the sliding window guide<\/a>, and practice on the lesson Longest Subarray with Sum at most S<\/a>.<\/p>\n
Prefix sums with a hash map: when negatives are allowed<\/h2>\n
Let P[i]<\/code> be the sum of the first i elements. The sum of the subarray from index i to j-1 is P[j] - P[i]<\/code>. So a subarray ending at the current position sums to k exactly when an earlier prefix equals current_prefix - k<\/code>. Keep a count of every prefix seen so far:<\/p>\n
def count_sum_k(a, k):\n    seen = {0: 1}          # the empty prefix\n    s = count = 0\n    for x in a:\n        s += x\n        count += seen.get(s - k, 0)\n        seen[s] = seen.get(s, 0) + 1\n    return count\n\nprint(count_sum_k([1, 2, 3, -3, 1, 1], 3))  # 4\n<\/code><\/pre>\n
The four subarrays are [1, 2]<\/code>, [3]<\/code>, [1, 2, 3, -3]<\/code> and [2, 3, -3, 1]<\/code>. It is O(n) time and O(n) space, and it works with negatives because it never assumes the sum moves in one direction. Forgetting {0: 1}<\/code> is the usual bug: it makes you miss subarrays that start at index 0.<\/p>\n
If you only need many range sums on a static array, build the prefix array once and answer each query as P[j] - P[i]<\/code> in O(1). More patterns are in when to use a prefix sum array<\/a>.<\/p>\n
Variations use the same idea with a different key. For “longest subarray with sum divisible by k”, store the first index at which each prefix % k<\/code> remainder appeared; two equal remainders mean the sum between them is divisible by k.<\/p>\n
Splitting an array into k subarrays: binary search on the answer<\/h2>\n
The problem (LeetCode 410, Split Array Largest Sum): cut an array of positive integers into k contiguous non-empty pieces so that the largest piece sum is as small as possible. Searches for this problem often phrase it as “divide the array into k contiguous subarrays”.<\/p>\n
Trying every way to cut is exponential. Instead, ask a yes\/no question: “can I split the array into at most k pieces if no piece may exceed limit<\/code>?” That is answered by one greedy pass: keep adding to the current piece, and start a new one when the next element would break the limit. The answer is monotonic (a larger limit never needs more pieces), so binary search finds the smallest limit that works. The search range is from max(a)<\/code> (a piece must hold the largest element) to sum(a)<\/code> (one piece):<\/p>\n
def split_array(a, k):\n    def pieces(limit):\n        n, cur = 1, 0\n        for x in a:\n            if cur + x > limit:\n                n += 1\n                cur = 0\n            cur += x\n        return n\n\n    lo, hi = max(a), sum(a)\n    while lo < hi:\n        mid = (lo + hi) \/\/ 2\n        if pieces(mid) <= k:\n            hi = mid\n        else:\n            lo = mid + 1\n    return lo\n\nprint(split_array([7, 2, 5, 10, 8], 2))  # 18  ([7, 2, 5] and [10, 8])\nprint(split_array([1, 2, 3, 4, 5], 3))   # 6   ([1, 2, 3], [4], [5])\n<\/code><\/pre>\n
Each check is O(n) and the search takes O(log(sum)) steps, so the total is O(n log(sum)). The greedy check only works because all values are positive. The same “binary search on the answer” shape solves minimum shipping capacity and “koko eating bananas”. A refresher on the search itself is in the Binary Search lesson<\/a>.<\/p>\n
Common mistakes<\/h2>\n