Welcome to the Array & Matrix template collection! These are ready-to-use C++ snippets for the most common array patterns: two pointers, sliding window, prefix sum, binary search, and matrix operations. Each template is minimal enough to memorize yet complete enough to paste into a solution and adapt. See also Arrays & Strings and Search.

Arrays are the most common data structure in interviews. Most problems start with an array or can be reduced to one. Learning these patterns well — two pointers, sliding window, prefix sum, and binary search — covers roughly 40% of all LeetCode problems.

Contents

Two Pointers

When to use: The problem says “sorted array”, asks for a “pair with target sum”, mentions “container with most water”, or requires comparing elements from both ends.

Two Sum on Sorted Array

def two_sum_sorted(a: list[int], target: int) -> bool:
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return True
        if s < target:
            l += 1
        else:
            r -= 1
    return False

Three Sum / Four Sum

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    n = len(nums)
    result: list[list[int]] = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result
ID Title Link Solution
15 3Sum Link -
18 4Sum Link Solution
11 Container With Most Water Link -
75 Sort Colors Link Solution
360 Sort Transformed Array Link Solution
344 Reverse String Link Solution
844 Backspace String Compare Link Solution
1868 Product of Two Run-Length Encoded Arrays Link Solution

Sliding Window

When to use: The problem asks for a “subarray of size k”, “longest/shortest subarray with property X”, or any contiguous subarray optimization.

3 0 1 1 7 2 2 3 5 4 9 5 4 6 8 7 left right shrink left expand right window [left, right]

Fixed Size Window

# Maximum sum of subarray of size k
def max_sum_subarray(nums: list[int], k: int) -> int:
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Variable Size Window

# Longest subarray with sum <= k
def longest_subarray(nums: list[int], k: int) -> int:
    left = 0
    total = 0
    max_len = 0
    for right in range(len(nums)):
        total += nums[right]
        while total > k:
            total -= nums[left]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len
ID Title Link Solution
3 Longest Substring Without Repeating Characters Link Solution
209 Minimum Size Subarray Sum Link -
239 Sliding Window Maximum Link Solution
480 Sliding Window Median Link Solution
2799 Count Complete Subarrays in an Array Link Solution
346 Moving Average from Data Stream Link Solution
713 Subarray Product Less Than K Link -

Prefix Sum

When to use: The problem involves “range sum queries”, “subarray sum equals k”, or asks you to compute cumulative totals over a range efficiently.

Prefix Sum — Range Query Original 10 21 32 43 54 range [2..4] Prefix 00 11 32 63 104 155 sum(a[2..4]) = prefix[5] − prefix[2] = 15 − 3 = 12 Range sum in O(1) after O(n) preprocessing

Basic Prefix Sum

def prefix_sum(a: list[int]) -> list[int]:
    ps = [0] * (len(a) + 1)
    for i in range(len(a)):
        ps[i + 1] = ps[i] + a[i]
    return ps


def range_sum(prefix: list[int], l: int, r: int) -> int:
    return prefix[r + 1] - prefix[l]

Difference Array

# Range addition
def get_modified_array(length: int, updates: list[list[int]]) -> list[int]:
    diff = [0] * (length + 1)
    for start, end, inc in updates:
        diff[start] += inc
        diff[end + 1] -= inc
    result = [0] * length
    cur = 0
    for i in range(length):
        cur += diff[i]
        result[i] = cur
    return result
ID Title Link Solution
303 Range Sum Query - Immutable Link Solution
307 Range Sum Query - Mutable Link Solution
560 Subarray Sum Equals K Link -
525 Contiguous Array Link Solution
1124 Longest Well-Performing Interval Link Solution
327 Count of Range Sum Link Solution
370 Range Addition Link -
1094 Car Pooling Link Solution

When to use: The input is sorted, the problem says “find position”, “search”, or you need to minimize/maximize a value where the answer is monotonic.

Search in Sorted Array

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Search in Rotated Sorted Array

def search_rotated(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
ID Title Link Solution
33 Search in Rotated Sorted Array Link Solution
34 Find First and Last Position Link -
240 Search a 2D Matrix II Link Solution

Matrix Operations

When to use: The problem says “rotate image”, “spiral order”, “transpose matrix”, or involves traversing a 2D grid in a specific pattern.

Spiral Matrix — Traversal Order 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 → right ↓ down ← left ↑ up outer ring (1–12) inner ring (13–16) right → down → left → up → repeat inward

Rotate Matrix

# Rotate 90 degrees clockwise
def rotate_matrix(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Spiral Matrix

def spiral_order(matrix: list[list[int]]) -> list[int]:
    if not matrix:
        return []
    m, n = len(matrix), len(matrix[0])
    top, bottom, left, right = 0, m - 1, 0, n - 1
    result: list[int] = []
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result
ID Title Link Solution
48 Rotate Image Link Solution
54 Spiral Matrix Link Solution
59 Spiral Matrix II Link Solution
498 Diagonal Traverse Link Solution
189 Rotate Array Link Solution
419 Battleships in a Board Link Solution
661 Image Smoother Link Solution
73 Set Matrix Zeroes Link Solution

Array Manipulation

When to use: The problem involves “merge intervals”, “jump game”, “overlapping ranges”, or requires rearranging array elements in-place.

Merge Intervals

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged: list[list[int]] = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

Jump Game

# Jump Game II - Minimum jumps
def jump_game_ii(nums: list[int]) -> int:
    n = len(nums)
    jumps = cur_end = cur_far = 0
    for i in range(n - 1):
        cur_far = max(cur_far, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = cur_far
    return jumps
ID Title Link Solution
56 Merge Intervals Link Solution
45 Jump Game II Link Solution
969 Pancake Sorting Link Solution

Summary

Pattern Signal Phrases Key Idea
Two Pointers “sorted array”, “pair sum”, “container” Start/end pointers moving inward
Sliding Window “substring”, “subarray of size k” Expand right, shrink left
Prefix Sum “range sum”, “subarray sum equals k” Precompute cumulative sums
Binary Search “sorted”, “find position” Halve search space
Matrix “rotate”, “spiral”, “transpose” Index mapping

More templates