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

bool twoSumSorted(const vector<int>& a, int target){
    int l = 0, r = (int)a.size() - 1;
    while (l < r){
        long long sum = (long long)a[l] + a[r];
        if (sum == target) return true;
        if (sum < target) ++l; else --r;
    }
    return false;
}

Three Sum / Four Sum

// 3Sum
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();
    
    for (int i = 0; i < n - 2; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left+1]) left++;
                while (left < right && nums[right] == nums[right-1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    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
int maxSumSubarray(vector<int>& nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; ++i) {
        sum += nums[i];
    }
    int maxSum = sum;
    
    for (int i = k; i < nums.size(); ++i) {
        sum = sum - nums[i-k] + nums[i];
        maxSum = max(maxSum, sum);
    }
    
    return maxSum;
}

Variable Size Window

// Longest subarray with sum <= k
int longestSubarray(vector<int>& nums, int k) {
    int left = 0, sum = 0, maxLen = 0;
    
    for (int right = 0; right < nums.size(); ++right) {
        sum += nums[right];
        
        while (sum > k) {
            sum -= nums[left++];
        }
        
        maxLen = max(maxLen, right - left + 1);
    }
    
    return maxLen;
}
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

vector<int> prefixSum(const vector<int>& a){
    vector<int> ps(a.size()+1);
    for (int i = 0; i < (int)a.size(); ++i) {
        ps[i+1] = ps[i] + a[i];
    }
    return ps;
}

// Range sum query
int rangeSum(vector<int>& prefix, int l, int r) {
    return prefix[r+1] - prefix[l];
}

Difference Array

// Range addition
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    vector<int> diff(length + 1, 0);
    
    for (auto& update : updates) {
        diff[update[0]] += update[2];
        diff[update[1] + 1] -= update[2];
    }
    
    vector<int> result(length);
    result[0] = diff[0];
    for (int i = 1; i < length; ++i) {
        result[i] = result[i-1] + diff[i];
    }
    
    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

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int 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

int searchRotated(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && 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
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    
    // Transpose
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    
    // Reverse each row
    for (int i = 0; i < n; ++i) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
}

Spiral Matrix

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;
    
    int m = matrix.size(), n = matrix[0].size();
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    
    while (top <= bottom && left <= right) {
        // Right
        for (int j = left; j <= right; ++j) {
            result.push_back(matrix[top][j]);
        }
        top++;
        
        // Down
        for (int i = top; i <= bottom; ++i) {
            result.push_back(matrix[i][right]);
        }
        right--;
        
        // Left
        if (top <= bottom) {
            for (int j = right; j >= left; --j) {
                result.push_back(matrix[bottom][j]);
            }
            bottom--;
        }
        
        // Up
        if (left <= right) {
            for (int i = bottom; i >= top; --i) {
                result.push_back(matrix[i][left]);
            }
            left++;
        }
    }
    
    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

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    
    for (auto& interval : intervals) {
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            merged.back()[1] = max(merged.back()[1], interval[1]);
        }
    }
    
    return merged;
}

Jump Game

// Jump Game II - Minimum jumps
int jump(vector<int>& nums) {
    int n = nums.size();
    int jumps = 0, curEnd = 0, curFar = 0;
    
    for (int i = 0; i < n - 1; ++i) {
        curFar = max(curFar, i + nums[i]);
        
        if (i == curEnd) {
            jumps++;
            curEnd = curFar;
        }
    }
    
    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