What Is a Subarray? Contiguous, Counted, and Everywhere

Somewhere around your 40th LeetCode problem, the word "subarray" becomes invisible. Just another piece of problem-statement furniture. Like "return" or "valid" or "non-decreasing." You stop reading it.

That is a mistake. The word has a precise meaning, and confusing it with "subsequence" or "subset" will send you down completely the wrong algorithm path. One wrong word. Two completely different time complexities.

What Is a Subarray?

A subarray is a contiguous, ordered slice of an array. Same elements, same relative order, no gaps.

Take [1, 2, 3, 4, 5]. The slice [2, 3, 4] is a subarray. The slice [1, 3, 5] is not. There is a gap between 1 and 3, and another between 3 and 5. That makes it a subsequence, which sounds similar but is a completely different beast algorithmically.

That single word, "contiguous," is what makes subarrays tractable. It is also why so many efficient algorithms exist to work with them.

Subarrays, Subsequences, Subsets: Get Them Straight

One clarification question in your interview, one completely different solution.

Term	Definition	Example from [1, 2, 3, 4]
Subarray	Contiguous slice, order maintained	[2, 3, 4]
Subsequence	Ordered, gaps allowed	[1, 3, 4]
Subset	Any elements, no order requirement	{2, 4, 1}

Subarrays are the most constrained. Subsets are the least. Subsequences sit in between.

When a problem says "subarray," it is handing you a constraint. Use it. Longest contiguous subarray with some property P is often solvable in O(n). Longest subsequence with the same property is typically O(n log n) or O(n²) dynamic programming. Not a small difference when n is 100,000.

Some interviewers use "subarray" and "subsequence" interchangeably. They are wrong, and you should clarify anyway. Ask: "Do the elements need to be contiguous?" One sentence. The answer changes the entire approach.

How Many Subarrays Are There?

Every subarray is defined by a start index and an end index. For an array of length n, count the valid (start, end) pairs where start <= end.

Starting at index 0: n subarrays (lengths 1, 2, ..., n)
Starting at index 1: n-1 subarrays
Starting at index k: n-k subarrays

Total: n + (n-1) + ... + 1 = n * (n+1) / 2

For [1, 2, 3]:

[1], [1,2], [1,2,3]
[2], [2,3]
[3]

Six subarrays. n=3, so 3*4/2 = 6. For n=1,000 that is 500,500. You do not want to check all of them.

Subsequences are worse. A length-n array has 2^n of them, because each element is either in or out. For n=20 that is over a million. The contiguity constraint is what keeps subarray problems in the polynomial realm. That is why they show up constantly in interviews, and why they are actually solvable in a 45-minute window.

The quadratic count also tells you the complexity floor. Any algorithm that examines every subarray does at least O(n²) work. When you see an O(n) or O(n log n) solution, it found a way to skip most subarrays without checking them. That is the whole trick.

What Subarrays Look Like in Code

In practice you rarely store subarrays as actual arrays. You represent them with two indices.

def all_subarrays(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i, n):
            print(arr[i:j+1])  # O(j-i+1) copy per slice

That slice arr[i:j+1] copies elements every time. If you stored every subarray, total space would be O(n³): O(n²) subarrays, each up to length O(n).

Interview problems almost never ask you to store every subarray. They want a property: maximum sum, count of valid subarrays, length of the longest one satisfying some constraint. Track the property, not the slice, and your space drops to O(1) or O(n).

The Four Patterns That Power Every Subarray Problem

Once you recognize a problem is about subarrays, it almost always maps to one of four approaches. Miss one of these and you are staring at O(n²) when O(n) was sitting right there.

The four subarray patterns: sliding window, prefix sums, Kadane's, and monotonic deque, each with time complexity and canonical LeetCode problems

Sliding Window

When you want the best subarray satisfying a size or sum constraint, two pointers let you expand the window right and shrink it left. Each element enters the window once and leaves once. The whole traversal is O(n).

Classic version: minimum length subarray with sum >= target (LeetCode 209). Grow the right pointer until the sum qualifies, then shrink the left until it no longer does.

def min_subarray_len(target, nums):
    left = total = 0
    min_len = float('inf')
    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            min_len = min(min_len, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if min_len == float('inf') else min_len

More on the general pattern: The Sliding Window Algorithm.

Prefix Sums

When you need range sum queries or counts of subarrays with a specific sum, build a prefix array where prefix[i] = sum of the first i elements. Then sum(arr[i..j]) = prefix[j+1] - prefix[i]. O(n) to build, O(1) per query.

LeetCode 560 (Subarray Sum Equals K) uses this with a hash map. For each index j, count how many previous prefix sums equal prefix[j] - k. Store frequencies as you go, one pass, O(n) time and space.

def subarray_sum(nums, k):
    count = prefix = 0
    seen = {0: 1}
    for n in nums:
        prefix += n
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

The full breakdown: What Is a Prefix Sum?

Kadane's Algorithm

Maximum subarray sum (LeetCode 53). At each index, the best subarray ending here is either just this element alone, or this element appended to the best subarray ending at the previous index. Take the max. O(n), one pass, O(1) space.

def max_subarray(nums):
    max_sum = current = nums[0]
    for n in nums[1:]:
        current = max(n, current + n)
        max_sum = max(max_sum, current)
    return max_sum

Notice the initialization: nums[0], not 0. Initializing to 0 breaks on all-negative arrays because zero is not achievable with any non-empty subarray. Input [-3, -1, -2] should return -1, not 0.

This is the most satisfying trap in Kadane's. It passes on every positive-number test case. You submit, it says correct. You feel good. Then the interviewer asks "what if all the numbers are negative?" and you stare at your initialization for a long, quiet moment.

Monotonic Deques

Some problems need the maximum or minimum within every sliding window of size k. A monotonic deque maintains a decreasing (or increasing) sequence of indices, discarding any that can never be the answer for a future window. Each element is added and removed at most once: O(n) total.

LeetCode 239 (Sliding Window Maximum) is the canonical version. The deque stores indices rather than values so you can evict elements that have slid past the current window boundary.

When to Reach for Which Pattern

Brute force for any subarray problem: O(n²) to enumerate all pairs. For n <= 1,000, that is fine. For n <= 10^5, it is not.

Quick guide:

"Maximum/minimum subarray satisfying a monotone constraint" → sliding window
"Count subarrays with sum equal to k" → prefix sum + hash map
"Maximum subarray sum" → Kadane's
"Maximum in every window of size k" → monotonic deque

If you find yourself writing three nested loops on a subarray problem, you are missing one of these four patterns. Prefix sums combined with a hash map cover a surprising fraction of the cases that look hard at first glance.

The Edge Cases That Always Come Up

Most problems require at least one element. Some do not. When in doubt, ask.

For Kadane's: initialize to nums[0], not 0. For prefix sum problems: pre-populate the hash map with {0: 1} before the loop. That single entry handles the case where a valid subarray starts at index 0. It is easy to miss and your interviewer is definitely testing it.

The three edge cases that bite on subarray problems: empty array, single-element array, all-negative values. Cover those and you have eliminated most of the gotchas before you even start.

Why Subarrays Show Up in Every Interview

"Maximum profit from stock prices" is secretly a maximum subarray problem applied to consecutive price differences. "Minimum operations to reduce array sum" might want binary search on the answer combined with prefix sums. The subarray framing is everywhere once you train your eye for it.

The constraint "contiguous" is the hint. The problem structure tells you which of the four patterns to reach for.

SpaceComplexity runs voice-based mock interviews where you practice exactly this kind of pattern recognition out loud, under realistic pressure, with rubric-based feedback after each session.