Coding Problems Cheatsheet
Category Problem Key Concepts/Strategies Detailed Explanation Code Example Arrays & Hashing Contains Duplicate Use a set to track seen numbers Iterate through the array, adding each element to the set; return true if an element is already in the set. Valid Anagram Use a hashmap to count character frequencies Count characters in both strings using hashmaps and compare the counts. Two Sum Use a hashmap to store indices of elements Iterate through the array, for each element, check if the complement (target - element) exists in the hashmap. Two Pointers Valid Palindrome Use two pointers to compare characters from both ends Initialize two pointers at the beginning and end of the string, move towards the center, and compare characters. 3Sum Sort the array, use two pointers to find triplets After sorting, fix one element and use two pointers to find pairs that sum up to the target value. Container With Most Water Use two pointers from both ends, move towards the center Start with two pointers at the ends of the array, calculate area, and move the pointer pointing to the shorter line. Sliding Window Best Time to Buy and Sell Stock Track the minimum price and maximum profit Iterate through prices, keeping track of the minimum price so far and calculating the maximum profit at each step. Longest Substring Without Repeating Characters Use a sliding window and a set to track characters Use a set to keep track of characters in the current window, move the window if a duplicate is found. Stack Valid Parentheses Use a stack to match opening and closing brackets Push opening brackets onto the stack, pop for closing brackets, ensuring they match. Binary Search Search in Rotated Sorted Array Modify binary search to handle rotation Determine which half is sorted, then use binary search logic on the sorted half. Find Minimum in Rotated Sorted Array Use binary search with rotation consideration Similar to searching in a rotated array, adjust the binary search to find the minimum element. Linked List Reverse Linked List Iterate and reverse pointers Use three pointers to reverse the direction of the list iteratively. Merge Two Sorted Lists Use a dummy node to merge iteratively Use a dummy node to simplify merging two lists, iteratively comparing and linking nodes. Reorder List Find middle, reverse second half, merge Split the list, reverse the second half, and merge the two halves by alternating nodes. Trees Binary Tree Inorder Traversal Use recursion or a stack Traverse left subtree, visit the node, then traverse the right subtree. Validate Binary Search Tree Use in-order traversal to check order Perform an in-order traversal and ensure each value is greater than the previous one. Same Tree Use recursion to compare nodes Recursively compare corresponding nodes in both trees. Tries Implement Trie (Prefix Tree) Use a TrieNode class to insert and search Use a nested TrieNode class to represent nodes, with methods for insert, search, and startsWith. Dynamic Programming Climbing Stairs Use DP array or memoization Use an array where each entry represents the number of ways to reach that step. House Robber Use a DP array to track maximum loot Use a DP array where each entry represents the maximum amount of money that can be robbed up to that house. Coin Change Use a DP array to track the minimum coins Use a DP array where each entry represents the minimum number of coins needed for that amount. Graphs Number of Islands Use DFS/BFS to mark visited islands Use DFS or BFS to traverse and mark all connected lands (islands) as visited. Clone Graph Use DFS/BFS and a hashmap for copies Use DFS or BFS with a hashmap to store already cloned nodes. Course Schedule Use DFS to detect cycles Perform a DFS and use a state array to detect cycles in the graph. Intervals Merge Intervals Sort intervals, then merge overlapping ones Sort intervals by start time, then iterate through and merge overlapping intervals. Insert Interval Insert and merge as necessary Insert the new interval into the list, then merge overlapping intervals. Meeting Rooms Sort intervals and check for overlaps Sort intervals by start time, use a min-heap to track end times of ongoing meetings. Strings Longest Substring Without Repeating Characters Use sliding window and a hashmap Use a sliding window to maintain a window of unique characters, updating the start of the window when a duplicate is found. Longest Palindromic Substring Use DP or expand around center approach Use dynamic programming to track palindromes or expand around each character to find the longest palindrome. Longest Common Prefix Compare characters of each string Compare characters of each string one by one until a mismatch is found. Backtracking Subsets Use backtracking to generate all subsets Recursively build subsets, choosing to include or exclude each element. Combination Sum Use backtracking to find combinations Recursively build combinations, subtracting from the target, and avoiding duplicates. Permutations Use backtracking to generate permutations Recursively generate permutations by swapping elements. Heap / Priority Queue Top K Frequent Elements Use a hashmap and a heap Use a hashmap to count frequencies, then use a heap to find the top K elements. Find Median from Data Stream Use two heaps to maintain the median Use a max-heap for the lower half and a min-heap for the upper half of the data stream. Greedy Best Time to Buy and Sell Stock II Sum up all the increasing differences Iterate through the array, summing up all positive differences between consecutive days. Jump Game Track the farthest reach possible Iterate through the array, updating the maximum reachable index and checking if the end is reachable. Bit Manipulation Single Number Use XOR to find the unique number XOR all elements, as XOR of two identical numbers is zero, and XOR of a number with zero is the number itself. Matrix Set Matrix Zeroes Use first row/column as markers Use the first row and column to mark zero rows and columns, then iterate and set zeros accordingly. Spiral Matrix Traverse in layers and change directions Use loops to traverse the matrix in a spiral order, changing direction at boundaries. Rotate Image Transpose and then reverse rows Transpose the matrix (swap rows and columns) and then reverse each row. Miscellaneous LRU Cache Use an ordered dictionary Use an ordered dictionary to maintain insertion order and implement LRU logic. Min Stack Use two stacks for value and minimum Use one stack for all values and another stack to keep track of minimum values.