Patterns Quick Reference Guide¶

Table of Contents¶

Two Pointers
Fast & Slow Pointers
Sliding Window
Intervals
Stack
Linked List
Binary Search
Heap / Priority Queue
DFS (Depth-First Search)
BFS (Breadth-First Search)
Backtracking
Monotonic Stack
Greedy
Bit Manipulation
Prefix Sum
Matrix Manipulation
Union Find (Disjoint Set)
Graphs
Dynamic Programming
Trie (Prefix Tree)
Topological Sort
Segment Tree
Binary Indexed Tree (Fenwick Tree)
Two Heaps
Cyclic Sort

1. Two Pointers¶

Description¶

Uses two pointers to iterate through data structures, typically moving toward each other or in the same direction. Reduces time complexity from O(n²) to O(n).

When to Use¶

Sorted arrays/lists
Finding pairs with a specific sum/condition
Removing duplicates in-place
Partitioning arrays
Palindrome verification
Container/area problems

Example Problems¶

Problem	Difficulty	Key Insight
Two Sum II (Sorted)	Easy	Start from both ends
3Sum	Medium	Fix one, two-pointer on rest
Container With Most Water	Medium	Move pointer with smaller height
Trapping Rain Water	Hard	Track left/right max
Remove Duplicates from Sorted Array	Easy	Slow/fast pointer
Sort Colors (Dutch National Flag)	Medium	Three pointers

Java Code Snippets¶

Two Sum II (Sorted Array)¶

public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

3Sum¶

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates

        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(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;
}

Container With Most Water¶

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxArea = Math.max(maxArea, width * h);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

Trapping Rain Water¶

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    return water;
}

2. Fast & Slow Pointers¶

Description¶

Also known as "Floyd's Tortoise and Hare" algorithm. Uses two pointers moving at different speeds to detect cycles or find middle elements.

When to Use¶

Cycle detection in linked lists or arrays
Finding the middle of a linked list
Finding the start of a cycle
Palindrome linked list verification
Happy number problem

Example Problems¶

Problem	Difficulty	Key Insight
Linked List Cycle	Easy	Fast catches slow if cycle
Linked List Cycle II	Medium	Reset one to head after meeting
Find the Duplicate Number	Medium	Array as linked list
Middle of the Linked List	Easy	Fast moves 2x
Happy Number	Easy	Number sequence forms cycle
Palindrome Linked List	Easy	Find middle, reverse, compare

Java Code Snippets¶

Linked List Cycle Detection¶

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;

    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Find Cycle Start (Linked List Cycle II)¶

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) return null;

    ListNode slow = head, fast = head;

    // Detect cycle
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }

    if (fast == null || fast.next == null) return null;

    // Find cycle start
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

Find the Duplicate Number¶

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];

    // Find intersection point
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // Find entrance to cycle
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

Middle of Linked List¶

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

3. Sliding Window¶

Description¶

Maintains a "window" over a contiguous sequence of elements, sliding it across the data structure. Converts O(n*k) problems to O(n).

When to Use¶

Subarray/substring problems with constraints
Finding max/min in subarrays of size k
Longest/shortest substring with conditions
Anagram finding
Fixed or variable window size problems

Example Problems¶

Problem	Difficulty	Key Insight
Maximum Sum Subarray of Size K	Easy	Fixed window
Longest Substring Without Repeating	Medium	Variable window + HashSet
Minimum Window Substring	Hard	Variable window + frequency map
Longest Repeating Character Replacement	Medium	Track max frequency
Permutation in String	Medium	Fixed window + frequency match
Sliding Window Maximum	Hard	Monotonic deque

Java Code Snippets¶

Fixed Window - Maximum Sum Subarray¶

public int maxSumSubarray(int[] nums, int k) {
    int windowSum = 0, maxSum = 0;

    for (int i = 0; i < nums.length; i++) {
        windowSum += nums[i];

        if (i >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= nums[i - k + 1];
        }
    }
    return maxSum;
}

Longest Substring Without Repeating Characters¶

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0, left = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            left = Math.max(left, map.get(c) + 1);
        }
        map.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Minimum Window Substring¶

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";

    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, minLen = Integer.MAX_VALUE, minStart = 0;
    int required = need.size(), formed = 0;
    Map<Character, Integer> window = new HashMap<>();

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);

        if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
            formed++;
        }

        while (formed == required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            char leftChar = s.charAt(left);
            window.put(leftChar, window.get(leftChar) - 1);
            if (need.containsKey(leftChar) && window.get(leftChar) < need.get(leftChar)) {
                formed--;
            }
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

Longest Repeating Character Replacement¶

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int maxCount = 0, maxLen = 0, left = 0;

    for (int right = 0; right < s.length(); right++) {
        count[s.charAt(right) - 'A']++;
        maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);

        // Window size - max frequency > k means we need to shrink
        while (right - left + 1 - maxCount > k) {
            count[s.charAt(left) - 'A']--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

4. Intervals¶

Description¶

Deals with problems involving intervals (start, end pairs). Often requires sorting and merging/comparing intervals.

When to Use¶

Merging overlapping intervals
Finding intersections
Meeting room scheduling
Inserting intervals
Interval coverage problems

Example Problems¶

Problem	Difficulty	Key Insight
Merge Intervals	Medium	Sort by start, merge overlaps
Insert Interval	Medium	Find position, merge
Non-overlapping Intervals	Medium	Greedy, sort by end
Meeting Rooms	Easy	Sort, check overlap
Meeting Rooms II	Medium	Min heap or two pointers
Interval List Intersections	Medium	Two pointers

Java Code Snippets¶

Merge Intervals¶

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;

    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> result = new ArrayList<>();
    int[] current = intervals[0];
    result.add(current);

    for (int[] interval : intervals) {
        if (interval[0] <= current[1]) {
            current[1] = Math.max(current[1], interval[1]);
        } else {
            current = interval;
            result.add(current);
        }
    }
    return result.toArray(new int[result.size()][]);
}

Meeting Rooms II (Minimum Meeting Rooms)¶

public int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) return 0;

    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];

    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }

    Arrays.sort(starts);
    Arrays.sort(ends);

    int rooms = 0, endPtr = 0;
    for (int i = 0; i < starts.length; i++) {
        if (starts[i] < ends[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    return rooms;
}

// Alternative: Min Heap approach
public int minMeetingRoomsHeap(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    for (int[] interval : intervals) {
        if (!heap.isEmpty() && heap.peek() <= interval[0]) {
            heap.poll();
        }
        heap.offer(interval[1]);
    }
    return heap.size();
}

Non-overlapping Intervals (Minimum Removals)¶

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;

    // Sort by end time (greedy)
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

    int count = 0, prevEnd = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= prevEnd) {
            prevEnd = interval[1];
        } else {
            count++; // Remove this interval
        }
    }
    return count;
}

Insert Interval¶

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;

    // Add all intervals before newInterval
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }

    // Merge overlapping intervals
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);

    // Add remaining intervals
    while (i < n) {
        result.add(intervals[i++]);
    }

    return result.toArray(new int[result.size()][]);
}

5. Stack¶

Description¶

LIFO (Last-In-First-Out) data structure. Essential for parsing, matching, and maintaining order of elements.

When to Use¶

Parentheses/brackets matching
Expression evaluation
Next greater/smaller element
Undo operations
DFS implementation
Simplifying paths

Example Problems¶

Problem	Difficulty	Key Insight
Valid Parentheses	Easy	Push open, pop close
Evaluate Reverse Polish Notation	Medium	Stack for operands
Daily Temperatures	Medium	Monotonic decreasing stack
Decode String	Medium	Stack for nested structures
Basic Calculator	Hard	Stack for precedence
Largest Rectangle in Histogram	Hard	Monotonic stack

Java Code Snippets¶

Valid Parentheses¶

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');

    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

Evaluate Reverse Polish Notation¶

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();

    for (String token : tokens) {
        if ("+-*/".contains(token)) {
            int b = stack.pop(), a = stack.pop();
            switch (token) {
                case "+": stack.push(a + b); break;
                case "-": stack.push(a - b); break;
                case "*": stack.push(a * b); break;
                case "/": stack.push(a / b); break;
            }
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

Decode String¶

public String decodeString(String s) {
    Stack<Integer> countStack = new Stack<>();
    Stack<StringBuilder> stringStack = new Stack<>();
    StringBuilder current = new StringBuilder();
    int k = 0;

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            countStack.push(k);
            stringStack.push(current);
            current = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            StringBuilder decoded = stringStack.pop();
            int count = countStack.pop();
            while (count-- > 0) {
                decoded.append(current);
            }
            current = decoded;
        } else {
            current.append(c);
        }
    }
    return current.toString();
}

Daily Temperatures (Next Greater Element)¶

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>(); // Store indices

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = i - idx;
        }
        stack.push(i);
    }
    return result;
}

6. Linked List¶

Description¶

Linear data structure with nodes connected via pointers. Essential for understanding memory and pointer manipulation.

When to Use¶

In-place reversal
Merging sorted lists
Finding cycles
Removing nth node
Reordering lists
Adding numbers represented as lists

Example Problems¶

Problem	Difficulty	Key Insight
Reverse Linked List	Easy	Three pointers
Merge Two Sorted Lists	Easy	Dummy head
Remove Nth Node From End	Medium	Two pointers, n apart
Reorder List	Medium	Find middle, reverse, merge
Add Two Numbers	Medium	Carry handling
LRU Cache	Medium	HashMap + Doubly Linked List

Java Code Snippets¶

Reverse Linked List (Iterative)¶

public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;

    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Reverse Linked List (Recursive)¶

public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Merge Two Sorted Lists¶

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Remove Nth Node From End¶

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;

    // Move fast n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // Move both until fast reaches end
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;
    return dummy.next;
}

LRU Cache¶

class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private int capacity;
    private Map<Integer, Node> map;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        insertAtHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        }
        Node node = new Node(key, value);
        map.put(key, node);
        insertAtHead(node);

        if (map.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertAtHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

7. Binary Search¶

Description¶

Divide-and-conquer algorithm for searching in sorted arrays. Reduces time complexity from O(n) to O(log n).

When to Use¶

Sorted arrays/lists
Finding boundaries (first/last occurrence)
Search space problems
Rotated sorted arrays
Finding peak elements
Minimizing/maximizing answers

Example Problems¶

Problem	Difficulty	Key Insight
Binary Search	Easy	Classic template
First Bad Version	Easy	Left boundary
Search in Rotated Sorted Array	Medium	Find pivot or compare
Find Peak Element	Medium	Gradient ascent
Koko Eating Bananas	Medium	Binary search on answer
Median of Two Sorted Arrays	Hard	Binary search on partition

Java Code Snippets¶

Classic Binary Search¶

public int search(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 -1;
}

Find First/Last Position (Left/Right Boundary)¶

public int[] searchRange(int[] nums, int target) {
    return new int[]{findFirst(nums, target), findLast(nums, target)};
}

private int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1; // Continue searching left
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

private int findLast(int[] nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            left = mid + 1; // Continue searching right
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Search in Rotated Sorted Array¶

public int searchRotated(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;

        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // Right half is sorted
        else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

Binary Search on Answer (Koko Eating Bananas)¶

public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = Arrays.stream(piles).max().getAsInt();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, mid, h)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private boolean canFinish(int[] piles, int speed, int h) {
    int hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed; // Ceiling division
    }
    return hours <= h;
}

8. Heap / Priority Queue¶

Description¶

Tree-based data structure that maintains max/min at root. Supports O(log n) insertion and extraction.

When to Use¶

Finding k largest/smallest elements
Merge k sorted lists/arrays
Continuous median
Task scheduling
Dijkstra's algorithm
Huffman coding

Example Problems¶

Problem	Difficulty	Key Insight
Kth Largest Element	Medium	Min heap of size k
Top K Frequent Elements	Medium	Min heap by frequency
Merge K Sorted Lists	Hard	Min heap of list heads
Find Median from Data Stream	Hard	Two heaps
Task Scheduler	Medium	Max heap + cooldown
Reorganize String	Medium	Max heap for alternating

Java Code Snippets¶

Kth Largest Element¶

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

Top K Frequent Elements¶

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    // Min heap by frequency
    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> freq.get(a) - freq.get(b)
    );

    for (int num : freq.keySet()) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = heap.poll();
    }
    return result;
}

Merge K Sorted Lists¶

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );

    for (ListNode list : lists) {
        if (list != null) heap.offer(list);
    }

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        curr.next = node;
        curr = curr.next;
        if (node.next != null) {
            heap.offer(node.next);
        }
    }
    return dummy.next;
}

Task Scheduler¶

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char task : tasks) {
        freq[task - 'A']++;
    }

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int f : freq) {
        if (f > 0) maxHeap.offer(f);
    }

    int cycles = 0;
    while (!maxHeap.isEmpty()) {
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            if (!maxHeap.isEmpty()) {
                temp.add(maxHeap.poll());
            }
        }

        for (int count : temp) {
            if (--count > 0) {
                maxHeap.offer(count);
            }
        }

        cycles += maxHeap.isEmpty() ? temp.size() : n + 1;
    }
    return cycles;
}

9. DFS (Depth-First Search)¶

Description¶

Explores as far as possible along each branch before backtracking. Uses recursion or explicit stack.

When to Use¶

Tree/graph traversal
Path finding
Connected components
Cycle detection
Topological sorting
Island problems
Generating permutations/combinations

Example Problems¶

Problem	Difficulty	Key Insight
Number of Islands	Medium	DFS to mark visited
Clone Graph	Medium	HashMap for visited
Path Sum	Easy	Track remaining sum
Binary Tree Maximum Path Sum	Hard	Track max through node
Course Schedule	Medium	Cycle detection
Word Search	Medium	Backtracking DFS

Java Code Snippets¶

Number of Islands¶

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
        || grid[i][j] != '1') {
        return;
    }

    grid[i][j] = '0'; // Mark visited
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

Clone Graph¶

public Node cloneGraph(Node node) {
    if (node == null) return null;

    Map<Node, Node> visited = new HashMap<>();
    return dfsClone(node, visited);
}

private Node dfsClone(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) {
        return visited.get(node);
    }

    Node clone = new Node(node.val);
    visited.put(node, clone);

    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfsClone(neighbor, visited));
    }
    return clone;
}

Binary Tree Maximum Path Sum¶

private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
}

private int maxGain(TreeNode node) {
    if (node == null) return 0;

    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);

    // Path through current node
    int pathSum = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, pathSum);

    // Return max gain if continuing path
    return node.val + Math.max(leftGain, rightGain);
}

Word Search¶

public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, word, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int i, int j, int idx) {
    if (idx == word.length()) return true;

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
        || board[i][j] != word.charAt(idx)) {
        return false;
    }

    char temp = board[i][j];
    board[i][j] = '#'; // Mark visited

    boolean found = dfs(board, word, i + 1, j, idx + 1)
                 || dfs(board, word, i - 1, j, idx + 1)
                 || dfs(board, word, i, j + 1, idx + 1)
                 || dfs(board, word, i, j - 1, idx + 1);

    board[i][j] = temp; // Restore
    return found;
}

10. BFS (Breadth-First Search)¶

Description¶

Explores all neighbors at current depth before moving to next level. Uses queue. Optimal for shortest path in unweighted graphs.

When to Use¶

Shortest path (unweighted)
Level-order traversal
Finding minimum steps
Multi-source BFS
Graph exploration by layers
Word ladder problems

Example Problems¶

Problem	Difficulty	Key Insight
Binary Tree Level Order Traversal	Medium	Queue + level size
Rotting Oranges	Medium	Multi-source BFS
Word Ladder	Hard	BFS for shortest transformation
Shortest Path in Binary Matrix	Medium	BFS with 8 directions
Open the Lock	Medium	State space BFS
Minimum Knight Moves	Medium	BFS on infinite board

Java Code Snippets¶

Level Order Traversal¶

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

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

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Rotting Oranges (Multi-source BFS)¶

public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    // Initialize: add all rotten oranges to queue
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 2) {
                queue.offer(new int[]{i, j});
            } else if (grid[i][j] == 1) {
                fresh++;
            }
        }
    }

    if (fresh == 0) return 0;

    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int minutes = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] curr = queue.poll();
            for (int[] dir : dirs) {
                int ni = curr[0] + dir[0];
                int nj = curr[1] + dir[1];

                if (ni >= 0 && ni < rows && nj >= 0 && nj < cols
                    && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;
                    fresh--;
                    queue.offer(new int[]{ni, nj});
                }
            }
        }
        if (!queue.isEmpty()) minutes++;
    }

    return fresh == 0 ? minutes : -1;
}

Word Ladder¶

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;

    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    Set<String> visited = new HashSet<>();
    visited.add(beginWord);
    int level = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            char[] chars = word.toCharArray();

            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    chars[j] = c;
                    String newWord = new String(chars);

                    if (newWord.equals(endWord)) return level + 1;

                    if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                        visited.add(newWord);
                        queue.offer(newWord);
                    }
                }
                chars[j] = original;
            }
        }
        level++;
    }
    return 0;
}

Shortest Path in Binary Matrix¶

public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0});
    grid[0][0] = 1; // Mark visited
    int path = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] curr = queue.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) return path;

            for (int[] dir : dirs) {
                int ni = curr[0] + dir[0];
                int nj = curr[1] + dir[1];

                if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] == 0) {
                    grid[ni][nj] = 1;
                    queue.offer(new int[]{ni, nj});
                }
            }
        }
        path++;
    }
    return -1;
}

11. Backtracking¶

Description¶

Systematic way to explore all potential solutions by building candidates and abandoning them when they fail to satisfy constraints.

When to Use¶

Permutations and combinations
Subset generation
N-Queens problem
Sudoku solver
Path finding with constraints
Generating all valid configurations

Example Problems¶

Problem	Difficulty	Key Insight
Subsets	Medium	Include/exclude each element
Permutations	Medium	Swap and recurse
Combination Sum	Medium	Choices with duplicates allowed
N-Queens	Hard	Validate diagonal attacks
Sudoku Solver	Hard	Try each number, backtrack
Palindrome Partitioning	Medium	Validate + generate

Java Code Snippets¶

Subsets¶

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> current,
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(current));

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

Permutations¶

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackPermute(nums, new ArrayList<>(), new boolean[nums.length], result);
    return result;
}

private void backtrackPermute(int[] nums, List<Integer> current,
                               boolean[] used, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        used[i] = true;
        current.add(nums[i]);
        backtrackPermute(nums, current, used, result);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

Combination Sum¶

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackCombSum(candidates, target, 0, new ArrayList<>(), result);
    return result;
}

private void backtrackCombSum(int[] candidates, int remain, int start,
                               List<Integer> current, List<List<Integer>> result) {
    if (remain == 0) {
        result.add(new ArrayList<>(current));
        return;
    }
    if (remain < 0) return;

    for (int i = start; i < candidates.length; i++) {
        current.add(candidates[i]);
        backtrackCombSum(candidates, remain - candidates[i], i, current, result);
        current.remove(current.size() - 1);
    }
}

N-Queens¶

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');

    backtrackQueens(board, 0, result);
    return result;
}

private void backtrackQueens(char[][] board, int row, List<List<String>> result) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }

    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrackQueens(board, row + 1, result);
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    // Check column
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    // Check diagonal (upper left)
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    // Check diagonal (upper right)
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

private List<String> construct(char[][] board) {
    List<String> result = new ArrayList<>();
    for (char[] row : board) {
        result.add(new String(row));
    }
    return result;
}

12. Monotonic Stack¶

Description¶

A stack that maintains elements in sorted (increasing or decreasing) order. Used to find next/previous greater/smaller elements efficiently.

When to Use¶

Next greater element problems
Stock span problems
Largest rectangle in histogram
Trapping rain water
Building with view of ocean
Temperature problems

Example Problems¶

Problem	Difficulty	Key Insight
Next Greater Element I	Easy	Map + monotonic stack
Daily Temperatures	Medium	Decreasing stack, store indices
Largest Rectangle in Histogram	Hard	Find boundaries
Maximal Rectangle	Hard	Build histogram per row
132 Pattern	Medium	Decreasing stack from right
Sum of Subarray Minimums	Medium	Contribution of each element

Java Code Snippets¶

Largest Rectangle in Histogram¶

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0;
    int n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];

        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Next Greater Element I¶

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> nextGreater = new HashMap<>();
    Stack<Integer> stack = new Stack<>();

    // Build map of next greater elements for nums2
    for (int num : nums2) {
        while (!stack.isEmpty() && stack.peek() < num) {
            nextGreater.put(stack.pop(), num);
        }
        stack.push(num);
    }

    // Answer queries from nums1
    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        result[i] = nextGreater.getOrDefault(nums1[i], -1);
    }
    return result;
}

Sum of Subarray Minimums¶

public int sumSubarrayMins(int[] arr) {
    int MOD = 1_000_000_007;
    int n = arr.length;

    // left[i] = count of subarrays ending at i where arr[i] is min
    // right[i] = count of subarrays starting at i where arr[i] is min
    int[] left = new int[n];
    int[] right = new int[n];

    Stack<Integer> stack = new Stack<>();

    // Calculate left boundaries
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
            stack.pop();
        }
        left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
        stack.push(i);
    }

    stack.clear();

    // Calculate right boundaries
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            stack.pop();
        }
        right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
        stack.push(i);
    }

    // Calculate sum
    long sum = 0;
    for (int i = 0; i < n; i++) {
        sum = (sum + (long) arr[i] * left[i] * right[i]) % MOD;
    }
    return (int) sum;
}

132 Pattern¶

public boolean find132pattern(int[] nums) {
    int n = nums.length;
    if (n < 3) return false;

    Stack<Integer> stack = new Stack<>();
    int third = Integer.MIN_VALUE; // The "2" in 132

    // Traverse from right to left
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] < third) return true; // Found "1" < "2"

        while (!stack.isEmpty() && nums[i] > stack.peek()) {
            third = stack.pop(); // Update "2" to be as large as possible
        }
        stack.push(nums[i]);
    }
    return false;
}

13. Greedy¶

Description¶

Makes locally optimal choices at each step hoping to find global optimum. Works when problem has optimal substructure.

When to Use¶

Interval scheduling
Activity selection
Huffman coding
Minimum spanning trees
Jump game problems
Gas station problems

Example Problems¶

Problem	Difficulty	Key Insight
Jump Game	Medium	Track max reachable
Jump Game II	Medium	BFS-like level jumps
Gas Station	Medium	If total >= 0, solution exists
Candy	Hard	Two passes (left, right)
Task Scheduler	Medium	Fill gaps around max freq
Partition Labels	Medium	Track last occurrence

Java Code Snippets¶

Jump Game¶

public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

Jump Game II (Minimum Jumps)¶

public int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;

    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);

        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

Gas Station¶

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalTank = 0, currentTank = 0, startStation = 0;

    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        totalTank += diff;
        currentTank += diff;

        if (currentTank < 0) {
            startStation = i + 1;
            currentTank = 0;
        }
    }
    return totalTank >= 0 ? startStation : -1;
}

Partition Labels¶

public List<Integer> partitionLabels(String s) {
    // Track last occurrence of each character
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) {
        last[s.charAt(i) - 'a'] = i;
    }

    List<Integer> result = new ArrayList<>();
    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);
        if (i == end) {
            result.add(end - start + 1);
            start = end + 1;
        }
    }
    return result;
}

Candy Distribution¶

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);

    // Left to right: higher rating than left neighbor
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // Right to left: higher rating than right neighbor
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    int total = 0;
    for (int c : candies) total += c;
    return total;
}

14. Bit Manipulation¶

Description¶

Operations directly on binary representations. Very efficient for certain problems involving powers of 2, XOR operations, or compact state representation.

When to Use¶

Single number problems (XOR)
Counting bits
Power of 2 checks
Subset generation
Bit masking in DP
Finding missing/duplicate numbers

Example Problems¶

Problem	Difficulty	Key Insight
Single Number	Easy	XOR all elements
Single Number II	Medium	Count bits mod 3
Missing Number	Easy	XOR with indices
Counting Bits	Easy	DP with bit shift
Reverse Bits	Easy	Shift and build
Subsets (using bits)	Medium	2^n bitmasks

Common Bit Operations¶

// Check if i-th bit is set
boolean isSet = (n & (1 << i)) != 0;

// Set i-th bit
n = n | (1 << i);

// Clear i-th bit
n = n & ~(1 << i);

// Toggle i-th bit
n = n ^ (1 << i);

// Check if power of 2
boolean isPowerOf2 = (n & (n - 1)) == 0 && n > 0;

// Get lowest set bit
int lowestBit = n & (-n);

// Clear lowest set bit
n = n & (n - 1);

// Count set bits
int count = Integer.bitCount(n);

Java Code Snippets¶

Single Number¶

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

Single Number II (Every element appears 3 times except one)¶

public int singleNumber2(int[] nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
}

Missing Number¶

public int missingNumber(int[] nums) {
    int xor = nums.length;
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}

Counting Bits¶

public int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

Subsets Using Bitmask¶

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;

    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.add(nums[i]);
            }
        }
        result.add(subset);
    }
    return result;
}

15. Prefix Sum¶

Description¶

Precomputes cumulative sums to enable O(1) range sum queries. The prefix sum at index i represents the sum of all elements from index 0 to i.

When to Use¶

Range sum queries
Subarray sum equals k
Find pivot index
Product of array except self
2D matrix sum queries
Equilibrium index

Example Problems¶

Problem	Difficulty	Key Insight
Range Sum Query - Immutable	Easy	prefix[j] - prefix[i-1]
Subarray Sum Equals K	Medium	HashMap for complement
Product Except Self	Medium	Left and right products
Contiguous Array	Medium	Map balance to index
Find Pivot Index	Easy	Left sum = Right sum
Range Sum Query 2D	Medium	2D prefix sum

Java Code Snippets¶

Range Sum Query¶

class NumArray {
    private int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

Subarray Sum Equals K¶

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);

    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) + 1);
    }
    return count;
}

Product Except Self¶

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // Left products
    result[0] = 1;
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Multiply by right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    return result;
}

Contiguous Array (Equal 0s and 1s)¶

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);

    int maxLen = 0, count = 0;
    for (int i = 0; i < nums.length; i++) {
        count += nums[i] == 1 ? 1 : -1;

        if (map.containsKey(count)) {
            maxLen = Math.max(maxLen, i - map.get(count));
        } else {
            map.put(count, i);
        }
    }
    return maxLen;
}

2D Range Sum Query¶

class NumMatrix {
    private int[][] prefix;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j]
                             + prefix[i][j-1] - prefix[i-1][j-1];
            }
        }
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2+1][c2+1] - prefix[r1][c2+1]
             - prefix[r2+1][c1] + prefix[r1][c1];
    }
}

16. Matrix Manipulation¶

Description¶

Techniques for traversing and manipulating 2D arrays efficiently, including rotations, spirals, and search.

When to Use¶

Matrix rotation
Spiral traversal
Diagonal traversal
Search in 2D matrix
Game boards (Sudoku, Tic-tac-toe)
Image processing

Example Problems¶

Problem	Difficulty	Key Insight
Rotate Image	Medium	Transpose + reverse
Spiral Matrix	Medium	Layer by layer
Set Matrix Zeroes	Medium	Use first row/col as markers
Search a 2D Matrix	Medium	Binary search
Valid Sudoku	Medium	Track rows, cols, boxes
Game of Life	Medium	Encode states in bits

Java Code Snippets¶

Rotate Image (90° clockwise)¶

public void rotate(int[][] matrix) {
    int n = matrix.length;

    // Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    // Reverse each row
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - 1 - j];
            matrix[i][n - 1 - j] = temp;
        }
    }
}

Spiral Matrix¶

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) return result;

    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // Right
        for (int j = left; j <= right; j++) {
            result.add(matrix[top][j]);
        }
        top++;

        // Down
        for (int i = top; i <= bottom; i++) {
            result.add(matrix[i][right]);
        }
        right--;

        // Left
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                result.add(matrix[bottom][j]);
            }
            bottom--;
        }

        // Up
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            left++;
        }
    }
    return result;
}

Set Matrix Zeroes (O(1) space)¶

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;

    // Check if first row/col has zero
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) firstRowZero = true;
    }
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstColZero = true;
    }

    // Mark zeros in first row/col
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Set zeros based on markers
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // Handle first row/col
    if (firstRowZero) {
        for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
    if (firstColZero) {
        for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

Search a 2D Matrix¶

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int left = 0, right = m * n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int value = matrix[mid / n][mid % n];

        if (value == target) return true;
        else if (value < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

17. Union Find (Disjoint Set)¶

Description¶

Data structure to track elements partitioned into disjoint sets. Supports efficient union and find operations with path compression and union by rank.

When to Use¶

Connected components
Detecting cycles in undirected graphs
Kruskal's MST algorithm
Dynamic connectivity
Friend circles/network connections
Accounts merge problems

Example Problems¶

Problem	Difficulty	Key Insight
Number of Connected Components	Medium	Count roots
Redundant Connection	Medium	Cycle detection
Accounts Merge	Medium	Email as nodes
Longest Consecutive Sequence	Medium	Union consecutive
Number of Islands II	Hard	Dynamic island count
Satisfiability of Equality Equations	Medium	== unions, != checks

Java Code Snippets¶

Union Find Template¶

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int count; // Number of connected components

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;

        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getCount() {
        return count;
    }
}

Number of Connected Components¶

public int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] edge : edges) {
        uf.union(edge[0], edge[1]);
    }
    return uf.getCount();
}

Redundant Connection¶

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);

    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return edge; // Already connected = cycle
        }
    }
    return new int[0];
}

Longest Consecutive Sequence¶

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;

    Map<Integer, Integer> numToIdx = new HashMap<>();
    int n = nums.length;
    UnionFind uf = new UnionFind(n);

    for (int i = 0; i < n; i++) {
        if (numToIdx.containsKey(nums[i])) continue;

        numToIdx.put(nums[i], i);

        if (numToIdx.containsKey(nums[i] - 1)) {
            uf.union(i, numToIdx.get(nums[i] - 1));
        }
        if (numToIdx.containsKey(nums[i] + 1)) {
            uf.union(i, numToIdx.get(nums[i] + 1));
        }
    }

    Map<Integer, Integer> componentSize = new HashMap<>();
    int maxLen = 1;

    for (int i = 0; i < n; i++) {
        int root = uf.find(i);
        int size = componentSize.getOrDefault(root, 0) + 1;
        componentSize.put(root, size);
        maxLen = Math.max(maxLen, size);
    }
    return maxLen;
}

18. Graphs¶

Description¶

Non-linear data structure with vertices and edges. Foundation for many complex algorithms.

When to Use¶

Shortest path problems (Dijkstra, Bellman-Ford)
Minimum spanning tree (Prim, Kruskal)
Network flow
Detecting cycles
Path existence
Social network analysis

Example Problems¶

Problem	Difficulty	Key Insight
Network Delay Time	Medium	Dijkstra's algorithm
Cheapest Flights	Medium	Bellman-Ford with k stops
Course Schedule II	Medium	Topological sort
Is Graph Bipartite?	Medium	2-coloring BFS/DFS
Clone Graph	Medium	DFS with visited map
Alien Dictionary	Hard	Topological sort

Java Code Snippets¶

Dijkstra's Algorithm¶

public int networkDelayTime(int[][] times, int n, int k) {
    // Build adjacency list
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] t : times) {
        graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
    }

    // Min heap: [distance, node]
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, k});

    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];

        if (d > dist[u]) continue;

        if (graph.containsKey(u)) {
            for (int[] neighbor : graph.get(u)) {
                int v = neighbor[0], w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
    }

    int maxDist = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
}

Bellman-Ford (with K stops)¶

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] prices = new int[n];
    Arrays.fill(prices, Integer.MAX_VALUE);
    prices[src] = 0;

    for (int i = 0; i <= k; i++) {
        int[] temp = Arrays.copyOf(prices, n);
        for (int[] flight : flights) {
            int from = flight[0], to = flight[1], price = flight[2];
            if (prices[from] != Integer.MAX_VALUE) {
                temp[to] = Math.min(temp[to], prices[from] + price);
            }
        }
        prices = temp;
    }
    return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
}

Is Graph Bipartite?¶

public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    int[] colors = new int[n]; // 0: unvisited, 1: color A, -1: color B

    for (int i = 0; i < n; i++) {
        if (colors[i] == 0 && !bfs(graph, i, colors)) {
            return false;
        }
    }
    return true;
}

private boolean bfs(int[][] graph, int start, int[] colors) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    colors[start] = 1;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : graph[node]) {
            if (colors[neighbor] == colors[node]) return false;
            if (colors[neighbor] == 0) {
                colors[neighbor] = -colors[node];
                queue.offer(neighbor);
            }
        }
    }
    return true;
}

Detect Cycle in Directed Graph¶

public boolean hasCycle(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
    }

    int[] state = new int[numCourses]; // 0: unvisited, 1: visiting, 2: visited

    for (int i = 0; i < numCourses; i++) {
        if (hasCycleDFS(graph, i, state)) return true;
    }
    return false;
}

private boolean hasCycleDFS(List<List<Integer>> graph, int node, int[] state) {
    if (state[node] == 1) return true;  // Back edge = cycle
    if (state[node] == 2) return false; // Already processed

    state[node] = 1; // Mark as visiting
    for (int neighbor : graph.get(node)) {
        if (hasCycleDFS(graph, neighbor, state)) return true;
    }
    state[node] = 2; // Mark as visited
    return false;
}

19. Dynamic Programming¶

Description¶

Solves complex problems by breaking them into overlapping subproblems and storing results to avoid recomputation.

When to Use¶

Optimization problems (min/max)
Counting problems
Overlapping subproblems
Optimal substructure
Decision making at each step

DP Patterns¶

0/1 Knapsack: Take or skip items
Unbounded Knapsack: Unlimited items
Longest Common Subsequence: Match sequences
Longest Increasing Subsequence: Monotonic sequences
Matrix Chain: Parenthesization
Palindromic: Substring/subsequence
Grid Paths: 2D traversal
State Machine: Buy/sell stocks

Example Problems¶

Problem	Difficulty	Key Insight
Climbing Stairs	Easy	Fibonacci variant
Coin Change	Medium	Unbounded knapsack
Longest Common Subsequence	Medium	2D DP
Word Break	Medium	Check all prefixes
Edit Distance	Hard	Insert/delete/replace
Best Time to Buy and Sell Stock	Easy-Hard	State machine

Java Code Snippets¶

Climbing Stairs (Fibonacci)¶

public int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Coin Change (Unbounded Knapsack)¶

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

0/1 Knapsack¶

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];

    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Longest Common Subsequence¶

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

Longest Increasing Subsequence¶

public int lengthOfLIS(int[] nums) {
    // O(n log n) solution using binary search
    List<Integer> tails = new ArrayList<>();

    for (int num : nums) {
        int pos = Collections.binarySearch(tails, num);
        if (pos < 0) pos = -(pos + 1);

        if (pos == tails.size()) {
            tails.add(num);
        } else {
            tails.set(pos, num);
        }
    }
    return tails.size();
}

Edit Distance¶

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // Replace
                               Math.min(dp[i - 1][j],     // Delete
                                       dp[i][j - 1]));    // Insert
            }
        }
    }
    return dp[m][n];
}

Word Break¶

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

Best Time to Buy and Sell Stock (State Machine)¶

// Multiple transactions allowed
public int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE, cash = 0;

    for (int price : prices) {
        int prevHold = hold;
        hold = Math.max(hold, cash - price);    // Buy
        cash = Math.max(cash, prevHold + price); // Sell
    }
    return cash;
}

// With cooldown
public int maxProfitWithCooldown(int[] prices) {
    int hold = Integer.MIN_VALUE, cash = 0, cooldown = 0;

    for (int price : prices) {
        int prevCash = cash;
        cash = Math.max(cash, hold + price);     // Sell
        hold = Math.max(hold, cooldown - price); // Buy
        cooldown = prevCash;                     // Cooldown
    }
    return cash;
}

20. Trie (Prefix Tree)¶

Description¶

Tree data structure for efficient storage and retrieval of strings, particularly for prefix-based operations.

When to Use¶

Autocomplete/typeahead
Spell checker
IP routing (longest prefix match)
Word search problems
Dictionary implementation
String matching with wildcards

Example Problems¶

Problem	Difficulty	Key Insight
Implement Trie	Medium	Node array for children
Word Search II	Hard	Trie + backtracking
Design Add and Search Words	Medium	DFS for wildcard
Replace Words	Medium	Find shortest prefix
Longest Word in Dictionary	Medium	BFS level by level
Palindrome Pairs	Hard	Trie for reversed words

Java Code Snippets¶

Trie Implementation¶

class Trie {
    private TrieNode root;

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

Word Search II¶

public List<String> findWords(char[][] board, String[] words) {
    List<String> result = new ArrayList<>();
    TrieNode root = buildTrie(words);

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs(board, i, j, root, result);
        }
    }
    return result;
}

private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
    char c = board[i][j];
    if (c == '#' || node.children[c - 'a'] == null) return;

    node = node.children[c - 'a'];
    if (node.word != null) {
        result.add(node.word);
        node.word = null; // Avoid duplicates
    }

    board[i][j] = '#';
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int[] d : dirs) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
            dfs(board, ni, nj, node, result);
        }
    }
    board[i][j] = c;
}

private TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String word : words) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.word = word;
    }
    return root;
}

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word;
}

21. Topological Sort¶

Description¶

Linear ordering of vertices in a directed acyclic graph (DAG) where for every edge (u, v), u comes before v.

When to Use¶

Task scheduling with dependencies
Course prerequisites
Build systems
Package dependencies
Detecting cycles in directed graphs

Example Problems¶

Problem	Difficulty	Key Insight
Course Schedule	Medium	Cycle detection
Course Schedule II	Medium	Return order
Alien Dictionary	Hard	Build graph from words
Parallel Courses	Medium	BFS levels = time
Sequence Reconstruction	Medium	Unique topological order
Minimum Height Trees	Medium	Leaf removal

Java Code Snippets¶

Kahn's Algorithm (BFS)¶

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
        indegree[pre[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }

    int[] order = new int[numCourses];
    int idx = 0;

    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[idx++] = course;

        for (int next : graph.get(course)) {
            if (--indegree[next] == 0) {
                queue.offer(next);
            }
        }
    }

    return idx == numCourses ? order : new int[0];
}

DFS-based Topological Sort¶

public int[] topologicalSortDFS(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
    }

    int[] state = new int[numCourses]; // 0: unvisited, 1: visiting, 2: visited
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < numCourses; i++) {
        if (state[i] == 0) {
            if (!dfs(graph, i, state, stack)) {
                return new int[0]; // Cycle detected
            }
        }
    }

    int[] result = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        result[i] = stack.pop();
    }
    return result;
}

private boolean dfs(List<List<Integer>> graph, int node, int[] state, Stack<Integer> stack) {
    state[node] = 1; // Visiting

    for (int neighbor : graph.get(node)) {
        if (state[neighbor] == 1) return false; // Cycle
        if (state[neighbor] == 0 && !dfs(graph, neighbor, state, stack)) {
            return false;
        }
    }

    state[node] = 2; // Visited
    stack.push(node);
    return true;
}

Alien Dictionary¶

public String alienOrder(String[] words) {
    Map<Character, Set<Character>> graph = new HashMap<>();
    Map<Character, Integer> indegree = new HashMap<>();

    // Initialize
    for (String word : words) {
        for (char c : word.toCharArray()) {
            graph.putIfAbsent(c, new HashSet<>());
            indegree.putIfAbsent(c, 0);
        }
    }

    // Build graph
    for (int i = 0; i < words.length - 1; i++) {
        String w1 = words[i], w2 = words[i + 1];
        if (w1.length() > w2.length() && w1.startsWith(w2)) {
            return ""; // Invalid
        }

        for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
            if (w1.charAt(j) != w2.charAt(j)) {
                if (!graph.get(w1.charAt(j)).contains(w2.charAt(j))) {
                    graph.get(w1.charAt(j)).add(w2.charAt(j));
                    indegree.put(w2.charAt(j), indegree.get(w2.charAt(j)) + 1);
                }
                break;
            }
        }
    }

    // Topological sort
    Queue<Character> queue = new LinkedList<>();
    for (char c : indegree.keySet()) {
        if (indegree.get(c) == 0) queue.offer(c);
    }

    StringBuilder result = new StringBuilder();
    while (!queue.isEmpty()) {
        char c = queue.poll();
        result.append(c);
        for (char next : graph.get(c)) {
            indegree.put(next, indegree.get(next) - 1);
            if (indegree.get(next) == 0) queue.offer(next);
        }
    }

    return result.length() == indegree.size() ? result.toString() : "";
}

22. Segment Tree¶

Description¶

Tree data structure for efficient range queries and updates on arrays. Supports O(log n) updates and queries.

When to Use¶

Range sum/min/max queries with updates
Interval problems with modifications
Counting inversions
Lazy propagation for range updates

Example Problems¶

Problem	Difficulty	Key Insight
Range Sum Query - Mutable	Medium	Basic segment tree
Count of Smaller Numbers After Self	Hard	Merge sort or segment tree
Range Sum Query 2D - Mutable	Hard	2D segment tree
Falling Squares	Hard	Coordinate compression
My Calendar III	Hard	Track overlapping events
Count of Range Sum	Hard	Merge sort variant

Java Code Snippets¶

Segment Tree Implementation¶

class SegmentTree {
    private int[] tree;
    private int[] nums;
    private int n;

    public SegmentTree(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.tree = new int[4 * n];
        build(0, 0, n - 1);
    }

    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
        } else {
            int mid = start + (end - start) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    public void update(int idx, int val) {
        update(0, 0, n - 1, idx, val);
    }

    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            nums[idx] = val;
            tree[node] = val;
        } else {
            int mid = start + (end - start) / 2;
            if (idx <= mid) {
                update(2 * node + 1, start, mid, idx, val);
            } else {
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    public int query(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }

    private int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0; // Out of range
        }
        if (left <= start && end <= right) {
            return tree[node]; // Fully within range
        }
        int mid = start + (end - start) / 2;
        return query(2 * node + 1, start, mid, left, right)
             + query(2 * node + 2, mid + 1, end, left, right);
    }
}

Count of Smaller Numbers After Self¶

public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    Integer[] result = new Integer[n];
    int[][] indexed = new int[n][2]; // [value, original index]

    for (int i = 0; i < n; i++) {
        indexed[i] = new int[]{nums[i], i};
        result[i] = 0;
    }

    mergeSort(indexed, 0, n - 1, result);
    return Arrays.asList(result);
}

private void mergeSort(int[][] arr, int left, int right, Integer[] result) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, result);
    mergeSort(arr, mid + 1, right, result);
    merge(arr, left, mid, right, result);
}

private void merge(int[][] arr, int left, int mid, int right, Integer[] result) {
    int[][] temp = new int[right - left + 1][2];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i][0] <= arr[j][0]) {
            // Count elements from right half that are smaller
            result[arr[i][1]] += j - mid - 1;
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        result[arr[i][1]] += j - mid - 1;
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    System.arraycopy(temp, 0, arr, left, temp.length);
}

23. Binary Indexed Tree (Fenwick Tree)¶

Description¶

Data structure providing O(log n) prefix sum queries and point updates. More memory efficient than segment trees for certain operations.

When to Use¶

Prefix sum queries with updates
Counting inversions
Range sum queries
Cumulative frequency tables

Example Problems¶

Problem	Difficulty	Key Insight
Range Sum Query - Mutable	Medium	Basic BIT
Count of Smaller Numbers After Self	Hard	Discretization + BIT
Reverse Pairs	Hard	Merge sort or BIT
Create Sorted Array through Instructions	Hard	BIT for counting
Global and Local Inversions	Medium	BIT or observation

Java Code Snippets¶

Binary Indexed Tree Implementation¶

class BinaryIndexedTree {
    private int[] tree;
    private int n;

    public BinaryIndexedTree(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    // Add val to index i (1-indexed)
    public void update(int i, int val) {
        while (i <= n) {
            tree[i] += val;
            i += i & (-i); // Add lowest set bit
        }
    }

    // Get prefix sum [1, i]
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & (-i); // Remove lowest set bit
        }
        return sum;
    }

    // Get range sum [left, right]
    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

Range Sum Query - Mutable (using BIT)¶

class NumArray {
    private BinaryIndexedTree bit;
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.bit = new BinaryIndexedTree(nums.length);
        for (int i = 0; i < nums.length; i++) {
            bit.update(i + 1, nums[i]);
        }
    }

    public void update(int index, int val) {
        int diff = val - nums[index];
        nums[index] = val;
        bit.update(index + 1, diff);
    }

    public int sumRange(int left, int right) {
        return bit.rangeQuery(left + 1, right + 1);
    }
}

24. Two Heaps¶

Description¶

Uses two heaps (max-heap and min-heap) to efficiently track median or partition elements.

When to Use¶

Finding median from data stream
Sliding window median
Balancing two groups
IPO problem (maximizing profit)

Example Problems¶

Problem	Difficulty	Key Insight
Find Median from Data Stream	Hard	Max heap for lower, min for upper
Sliding Window Median	Hard	Two heaps + lazy removal
IPO	Hard	Max heap for profit, min for capital
Balance a Binary Search Tree	Medium	Sort + rebuild

Java Code Snippets¶

Find Median from Data Stream¶

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // Lower half
    private PriorityQueue<Integer> minHeap; // Upper half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        // Balance: maxHeap can have at most 1 more element
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

Sliding Window Median¶

public double[] medianSlidingWindow(int[] nums, int k) {
    double[] result = new double[nums.length - k + 1];
    TreeMap<Integer, Integer> lower = new TreeMap<>(Collections.reverseOrder());
    TreeMap<Integer, Integer> upper = new TreeMap<>();
    int lowerSize = 0, upperSize = 0;

    for (int i = 0; i < nums.length; i++) {
        // Add number
        if (lower.isEmpty() || nums[i] <= lower.firstKey()) {
            add(lower, nums[i]);
            lowerSize++;
        } else {
            add(upper, nums[i]);
            upperSize++;
        }

        // Remove old number
        if (i >= k) {
            int old = nums[i - k];
            if (lower.containsKey(old)) {
                remove(lower, old);
                lowerSize--;
            } else {
                remove(upper, old);
                upperSize--;
            }
        }

        // Balance
        while (lowerSize > upperSize + 1) {
            int move = lower.firstKey();
            remove(lower, move);
            lowerSize--;
            add(upper, move);
            upperSize++;
        }
        while (upperSize > lowerSize) {
            int move = upper.firstKey();
            remove(upper, move);
            upperSize--;
            add(lower, move);
            lowerSize++;
        }

        // Calculate median
        if (i >= k - 1) {
            if (k % 2 == 1) {
                result[i - k + 1] = lower.firstKey();
            } else {
                result[i - k + 1] = ((double) lower.firstKey() + upper.firstKey()) / 2;
            }
        }
    }
    return result;
}

private void add(TreeMap<Integer, Integer> map, int num) {
    map.put(num, map.getOrDefault(num, 0) + 1);
}

private void remove(TreeMap<Integer, Integer> map, int num) {
    map.put(num, map.get(num) - 1);
    if (map.get(num) == 0) map.remove(num);
}

25. Cyclic Sort¶

Description¶

Sorts arrays where elements are in a known range [1, n] by placing each element at its correct index in O(n) time.

When to Use¶

Find missing number
Find duplicate
Find all missing numbers
First missing positive
Array contains numbers in range [1, n]

Example Problems¶

Problem	Difficulty	Key Insight
Missing Number	Easy	XOR or cyclic sort
Find All Numbers Disappeared	Easy	Mark as negative
Find the Duplicate Number	Medium	Cyclic sort or Floyd's
First Missing Positive	Hard	Place each in correct position
Find All Duplicates	Medium	Mark and detect

Java Code Snippets¶

Cyclic Sort Template¶

public void cyclicSort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int correctIdx = nums[i] - 1;
        if (nums[i] > 0 && nums[i] <= nums.length
            && nums[i] != nums[correctIdx]) {
            // Swap to correct position
            int temp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = temp;
        } else {
            i++;
        }
    }
}

First Missing Positive¶

public int firstMissingPositive(int[] nums) {
    int n = nums.length;

    // Place each number in its correct position
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n
               && nums[nums[i] - 1] != nums[i]) {
            int correctIdx = nums[i] - 1;
            int temp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = temp;
        }
    }

    // Find first missing
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

Find All Duplicates¶

public List<Integer> findDuplicates(int[] nums) {
    List<Integer> result = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {
        int idx = Math.abs(nums[i]) - 1;
        if (nums[idx] < 0) {
            result.add(idx + 1);
        }
        nums[idx] = -nums[idx];
    }
    return result;
}

Quick Pattern Recognition Cheat Sheet¶

If you see...	Consider...
Sorted array	Binary Search, Two Pointers
Find pairs/triplets	Two Pointers, HashMap
Linked list cycle	Fast & Slow Pointers
Contiguous subarray	Sliding Window, Prefix Sum
Start/end times	Intervals, Sorting
Matching brackets	Stack
Shortest path (unweighted)	BFS
Shortest path (weighted)	Dijkstra, Bellman-Ford
All paths/permutations	Backtracking, DFS
Connected components	Union Find, DFS
Tree traversal	DFS, BFS
Dependencies	Topological Sort
K largest/smallest	Heap
String prefix	Trie
Range queries + updates	Segment Tree, BIT
Optimization (min/max)	DP, Greedy
Counting ways	DP
Median stream	Two Heaps
Numbers in range [1,n]	Cyclic Sort
XOR properties	Bit Manipulation
Previous/next greater	Monotonic Stack

Time Complexity Quick Reference¶

Pattern	Time	Space
Two Pointers	O(n)	O(1)
Sliding Window	O(n)	O(k)
Binary Search	O(log n)	O(1)
BFS/DFS	O(V + E)	O(V)
Heap operations	O(log n)	O(n)
Union Find	O(α(n)) ≈ O(1)	O(n)
Trie insert/search	O(m)	O(ALPHABET × m × n)
Segment Tree	O(log n)	O(n)
DP (2D)	O(m × n)	O(m × n) or O(n)
Backtracking	O(k^n) or O(n!)	O(n)
Topological Sort	O(V + E)	O(V)

Interview Tips¶

Clarify first: Ask about constraints, edge cases, expected input size
State pattern: Mention the pattern you're using and why
Start simple: Begin with brute force if needed, then optimize
Test thoroughly: Walk through examples before coding
Consider edge cases: Empty input, single element, duplicates
Analyze complexity: State time and space complexity
Optimize: Consider if there's a better approach after solving