Contents

Two Pointers

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

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

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

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

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 -
498 Diagonal Traverse Link Solution
189 Rotate Array Link Solution
419 Battleships in a Board Link Solution
661 Image Smoother Link Solution

Array Manipulation

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