Leetcode Patterns Cheatsheet

2026-04-11 2165 words 11 minutes

Contents

Leetcode Patterns Cheat Sheet

Two Pointers

Use one pointer at the start and other at the end
Keep moving them towards each other until they meet

Example: Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

public int maxArea(int[] heights) {
    int left = 0; int right = heights.length-1;
    int maxArea = 0;
    while (left < right) {
        int currentArea = (right-left)*Math.min(heights[left], heights[right]);
        maxArea = Math.max(currentArea, maxArea);
        // left is shorter, so move left pointer
        if (heights[left] < heights[right])
            left++;
        else
            right--;
    }
    return maxArea;
}

LeetCode questions

Sliding Window

Fixed window size

Calculate the value for first window
Calculate for the next window by subtracting the first element (or element exiting the window) and adding the new element entering the window to calculate the value.

Example:

Maximum Average Subarray I

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

public double findMaxAverage(int[] nums, int k) {
    int n = nums.length;
    double windowSum = 0;
    // calculate for first window
    for (int i=0; i<k; i++) windowSum += nums[i];

    double maxSum = windowSum;
    // calculate for other windows
    for (int i=k; i<n; i++) {
        windowSum += nums[i] - nums[i-k];
        maxSum = Math.max(windowSum, maxSum);
    }
    return maxSum/k;   
}

Variable window size

Keep expanding the window by by moving the right pointer from beginning to the end
If the condition is getting dissatisfied, shrink the window by moving the left pointer

Example:

Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.

public int longestOnes(int[] nums, int k) {
    int maxCount = 0, left = 0, right = 0, n = nums.length, zeroCount = 0;
    // keep expanding the window
    for (right=0; right<n; right++) {
        if (nums[right] == 0) zeroCount++;
        // shrink the window i.e. move left pointer forward
        while (k < zeroCount) {
            if (nums[left] == 0) zeroCount--;
            left++;
        }
        // get max window size
        maxCount = Math.max(right - left + 1, maxCount);
    }
      return maxCount;
}

LeetCode questions

Prefix Sum

Maintain a cumulative sum once (as array or variable) , then reuse it.

Example: Find Pivot Index

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.

Return the leftmost pivot index. If no such index exists, return -1.

public int pivotIndex(int[] nums) {
    int totalSum = 0;
    for (int num : nums) totalSum += num;

    int leftSum = 0;
    for (int i=0; i<nums.length; i++) {
        int rightSum = totalSum - leftSum - nums[i];
        if (leftSum == rightSum) return i;
        leftSum += nums[i];
    }

    return -1;
}

LeetCode questions:

Monotonic Stack

Create a stack to store indices.
Iterate through the array:
1. While the stack is not empty and current element > element at stack top index:
  - The current element is the next greater for that index.
  - Pop the index and update the result.
2. Push the current index onto the stack.
After the loop, any indices left in the stack
- No greater element exists for them.
- Fill result with default value like 0.

Note: For next smaller element, change the comparison in 2.a. to current element < element at stack top index

Example: Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Stack<Integer> stack = new Stack();
int[] result = new int[temperatures.length];

for (int i=0; i<temperatures.length; i++) {
    // check if current temparture > previous temparature
    // if yes, days = current idx - previous temperature's idx
    while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
        int prevIdx = stack.pop();
        result[prevIdx] = i-prevIdx;
    }
    stack.push(i);
}
// populate 0 for which greater not found
while (!stack.isEmpty()) {
    result[stack.pop()] = 0;
}
return result;

LeetCode questions:

Binary Search

Pick the middle of the sorted array (mid = left + (right-left)/2)
If target == middle element, return
If target > middle element, search for target in the right half (left = mid+1)
If target < middle element, search for target in the left half (right = mid-1)

Binary Search Iterative

int left = 0, right = n - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid; // target found
    else if (nums[mid] < target) left = mid + 1; // search right half
    else right = mid - 1; // search left half
}

Binary Search Recursive

public int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;

    int mid = left + (right - left) / 2; 
    if (arr[mid] == target) 
            return mid; // target found
    else if (arr[mid] < target) 
            return binarySearch(arr, target, mid + 1, right); // search right half
    else 
            return binarySearch(arr, target, left, mid - 1); // search left half
}

Binary Search based on condition

int left = min, right = max;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (canDo(mid)) right = mid; // use a function to find which half to search
    else left = mid + 1;
}
return left;

Example: Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid+1;
            else right = mid-1;
        }
        return right+1;
    }
}

LeetCode questions:

LinkedList: fast + slow pointers

Iterate in the linked list with two pointers: fast and slow
Fast pointer takes 2 steps at a time
Slow pointer takes 1 step at a time
When fast pointer reaches the end, slow will be in the middle.

Example: 876. Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

ListNode slow = head;
ListNode fast = head;
        
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

return slow;

LeetCode questions:

Tree DFS (Recursive)

int dfs(TreeNode root) {
    if (root == null) return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);
    return Math.max(left, right) + 1;
}

Tree BFS (Level Order)

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
    int level = queue.size();
    for (int i = 0; i < level; i++) {
        TreeNode node = queue.poll();
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Graph DFS

void dfs(int node, Set<Integer> visited) {
    if (visited.contains(node)) return;
    visited.add(node);
    for (int nei : graph.get(node)) {
        dfs(nei, visited);
    }
}

Graph BFS

Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited.add(start);

while (!q.isEmpty()) {
    int node = q.poll();
    for (int nei : graph.get(node)) {
        if (!visited.contains(nei)) {
            visited.add(nei);
            q.offer(nei);
        }
    }
}

Backtracking

void backtrack(List<Integer> path, int start) {
    result.add(new ArrayList<>(path));

    for (int i = start; i < n; i++) {
        path.add(nums[i]);
        backtrack(path, i + 1);
        path.remove(path.size() - 1);
    }
}

Dynamic Programming

This approach breaks problem into subproblems and reusing their answer to find the final solution. Consider the various answers to the problem as a graph (or a DAG), where each node represents a subproblem. With DP, this graph is traversed to find the most optimal solution. Base case is the source node while the final answer is the target node, dp finds the shortest path to it.

When to choose bottom-up or top-down approach:

If thinking recursively is easy: Top-Down
If optimizing for performance/space: Bottom-Up
Tree/Graph DP: Usually Top-Down
Array/Grid DP: Usually Bottom-Up

1D

Define dp array with length usually n+1 (in case of 0 or empty string case)
Initialize with base case (dp[0], dp[1] …)
Find dp formula (for fibonacci: dp[i] = dp[i-1]+dp[i-2])
Return the last dp element (or max dp value)

Note: If dp[i] only depends on fixed previous states: use variables instead of array (like previous 1 and previous2)

Example: 322. Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

int[] memo = new int[amount+1];
// dont use integer.max_val to avoid integer overflow
Arrays.fill(memo, amount+1);
memo[0] = 0;
for (int i=0; i<=amount; i++) {
    for (int coin : coins)
        // only use coin when amount > coin value
        if (i>= coin) memo[i] = Math.min(memo[i-coin]+1, memo[i]);
}
return memo[amount] == amount+1 ? -1 : memo[amount];

// same as above but recursive
public int coinChange(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, amount+1);
    return helper(coins, amount, memo);
}

private int helper(int[] coins, int amount, int[] memo) {
    if (amount < 0) return -1;   // invalid
    if (amount == 0) return 0;   // base case
    if (memo[amount] != amount+1) return memo[amount]; // return pre-computed value

    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int res = helper(coins, amount - coin, memo);
        if (res >= 0 && res < min) {
            min = res + 1;
        }
    }

    memo[amount] = (min == Integer.MAX_VALUE) ? -1 : min;
    return memo[amount];
}

LeetCode questions:

2D

Define dp array with length usually n+1, m+1 (in case of 0 or empty string case)
Initialize with base case for first row and column items (usually dp[i][…] and dp[…][j])
Find dp formula (usually: dp[i][j] = dp[i-1][j]+dp[i][j-1] etc pointing to top, left, diagonal)
Return the last dp element (or max dp value)

Note: If dp[i][j] only depends on previous row it can be compressed to 1D.

Example: 62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

public int uniquePaths(int m, int n) {
    int[][] memo = new int[m][n];
    memo[0][0] = 0; // base case
    for (int r=0; r<m; r++) {
        for (int c=0; c<n; c++) {
            if (r==0 || c==0) memo[r][c] = 1; // at edge
            else memo[r][c] = memo[r][c-1]+memo[r-1][c]; // dp calculation
        }
    }
    return memo[m-1][n-1];
}

LeetCode questions:

Heap (Top K)

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
    pq.offer(num);
    if (pq.size() > k) pq.poll();
}

Bit Manipulation

Iterate in bits, where the last bit is current bit used in the loop
- (n & 1) gets the last bit
- Iterate by: n = n >> 1
- The loop should break when n becomes 0

Tips:

Get bit: (num >> i) & 1
Set bit: num | (1 << i)
Clear bit: num & ~(1 << i)
Use >>> instead of >> when working with unsigned values
For fixed 32-bit problems or where leading zeros are important, always loop 32 times.

Example: 190. Reverse Bits

Reverse bits of a given 32 bits signed integer.

public int reverseBits(int n) {
  int result = 0;
  for (int i=0; i<32; i++) {
      // get bit
      int bit = (n >> i) & 1;
      // if bit is 1, set the result's 31-i place to reverse
      if (bit == 1)
          result |= 1 << (31 - i);
  }
  return result;
}

LeetCode questions:

References