- Trapping Rain Water (Leetcode 42) Problem
Given an array representing the height of bars, calculate how much rainwater can be trapped after raining.
Explanation
Rainwater can only be stored when a bar has taller bars on both its left and right sides. For every position, the trapped water depends on the smaller of the tallest bars on either side.
Approach Use two pointers (left and right). Maintain the maximum height seen from both directions. Move the pointer with the smaller height. If the current bar is lower than the maximum height on that side, the difference is added to the total trapped water. ⏱ Time Complexity
O(n)
Space Complexity
O(1)
- First Missing Positive (Leetcode 41) Problem
Find the smallest positive integer that is missing from an unsorted array.
Explanation
Negative numbers and zero do not affect the answer. The goal is to identify the first positive number that does not exist in the array.
Approach Store all numbers in a set. Start checking from 1. Continue increasing the number until a value is not found in the set. Return that missing positive number. ⏱ Time Complexity
O(n)
Space Complexity
O(n)
- Sliding Window Maximum (Leetcode 239) Problem
Given an array and a window size k, find the maximum element in every sliding window.
Explanation
Instead of checking every window repeatedly, maintain only the useful elements that can become the maximum.
Approach Use a deque to store indices. Remove elements outside the current window. Remove smaller elements from the back because they can never become the maximum. The front of the deque always represents the maximum element of the current window. ⏱ Time Complexity
O(n)
Space Complexity
O(k)
- Median of Two Sorted Arrays (Leetcode 4) Problem
Find the median of two sorted arrays without merging them completely.
Explanation
The solution uses binary search to partition both arrays into left and right halves so that every element on the left is smaller than every element on the right.
Approach Perform binary search on the smaller array. Find the correct partition. Validate the partition conditions. Calculate the median depending on whether the total number of elements is odd or even. ⏱ Time Complexity
O(log(min(n, m)))
Space Complexity
O(1)
- Maximum Sum of 3 Non-Overlapping Subarrays (Leetcode 689) Problem
Find three non-overlapping subarrays of size k whose total sum is maximum.
Explanation
The challenge is to maximize the combined sum while ensuring that the selected subarrays do not overlap.
Approach Compute the sum of every possible window of size k. Track the best left subarray and best right subarray for every position. Iterate through the middle subarray and combine it with the best left and right choices. Return the indices of the optimal three subarrays. ⏱ Time Complexity
O(n)
Space Complexity
O(n)
- Minimum Window Substring (Leetcode 76) Problem
Find the smallest substring that contains all characters of another string.
Explanation
The substring should include every required character with the correct frequency while keeping the window as small as possible.
Approach Use the sliding window technique. Expand the window until all required characters are included. Shrink the window while maintaining validity. Store the smallest valid window found. ⏱ Time Complexity
O(n)
Space Complexity
O(n)
- Substring with Concatenation of All Words (Leetcode 30) Problem
Find all starting indices where the concatenation of all given words appears exactly once without extra characters.
Explanation
Every word has the same length, making it possible to scan the string in fixed-size chunks.
Approach Count the frequency of all words. Move through the string using a sliding window. Compare the frequency of words inside the window with the expected frequency. Record every valid starting index. ⏱ Time Complexity
O(n × wordLength)
Space Complexity
O(number of words)
- Regular Expression Matching (Leetcode 10) Problem
Determine whether a string matches a pattern containing . and *.
Explanation
. matches any single character, while * matches zero or more occurrences of the preceding character.
Approach Use Dynamic Programming. Build a DP table where each cell represents whether a substring matches a pattern. Handle normal characters, ., and * separately. The final answer is stored in the last cell of the DP table. ⏱ Time Complexity
O(m × n)
Space Complexity
O(m × n)
- Palindrome Partitioning II (Leetcode 132) Problem
Find the minimum number of cuts needed to divide a string into palindrome substrings.
Explanation
The objective is to partition the string such that every part is a palindrome while minimizing the number of cuts.
Approach Precompute all palindrome substrings. Use Dynamic Programming to determine the minimum cuts for every position. Return the minimum cuts needed for the complete string. ⏱ Time Complexity
O(n²)
Space Complexity
O(n²)
- Distinct Subsequences (Leetcode 115) Problem
Count the number of distinct subsequences of one string that equal another string.
Explanation
Characters can be skipped, but their relative order must remain unchanged.
Approach Use Dynamic Programming. Each state represents the number of ways to match prefixes of the strings. If characters match, include both matching and skipping possibilities. Otherwise, skip the current character. ⏱ Time Complexity
O(m × n)
Space Complexity
O(m × n) 11. Largest Rectangle in Histogram (LeetCode 84) Problem
Given an array representing the heights of histogram bars, find the area of the largest rectangle that can be formed.
Explanation
Each bar can act as the minimum height of a rectangle. The objective is to determine the maximum area that can be formed using consecutive bars.
Approach Use a monotonic increasing stack to store the indices of histogram bars. When a smaller bar is encountered, pop bars from the stack and calculate the rectangle area. Continue until all bars have been processed. The maximum calculated area is the answer. Time Complexity
O(n)
Space Complexity
O(n)
- Maximal Rectangle (LeetCode 85) Problem
Given a binary matrix, find the area of the largest rectangle containing only 1s.
Explanation
Each row can be treated as the base of a histogram. By updating the histogram heights for every row, the problem becomes equivalent to finding the largest rectangle in a histogram.
Approach Traverse the matrix row by row. Update the histogram heights for each column. Apply the Largest Rectangle in Histogram algorithm for every row. Keep track of the maximum area obtained. Time Complexity
O(rows × columns)
Space Complexity
O(columns)
- Remove K Digits (LeetCode 402) Problem
Given a non-negative integer represented as a string, remove exactly k digits to obtain the smallest possible number.
Explanation
Whenever a larger digit appears before a smaller digit, removing the larger digit helps produce a smaller final number.
Approach Use a stack to store digits. Remove larger digits while a smaller digit is encountered and removals are still available. Push the current digit into the stack. Remove any remaining digits from the end if required. Remove leading zeros before returning the answer. Time Complexity
O(n)
Space Complexity
O(n)
- Trapping Rain Water (Stack Approach) (LeetCode 42) Problem
Calculate the total amount of rainwater trapped between elevation bars.
Explanation
The stack maintains the indices of bars. When a taller bar is found, trapped water between two boundaries can be calculated.
Approach Maintain a monotonic decreasing stack. Pop the middle bar whenever a taller bar is encountered. Calculate the width and height of trapped water. Add the trapped water to the final answer. Time Complexity
O(n)
Space Complexity
O(n)
- Sliding Window Maximum (Queue Approach) (LeetCode 239) Problem
Find the maximum element in every sliding window of size k.
Explanation
A deque stores only useful indices in decreasing order so that the maximum element is always available at the front.
Approach Remove indices that are outside the current window. Remove smaller elements from the back of the deque. Insert the current index. The front of the deque represents the maximum element for the current window. Time Complexity
O(n)
Space Complexity
O(k)
- Shortest Subarray with Sum at Least K (LeetCode 862) Problem
Find the length of the shortest subarray whose sum is at least k.
Explanation
Using prefix sums and a monotonic deque helps efficiently identify the shortest valid subarray.
Approach Compute prefix sums. Maintain a deque with increasing prefix sum values. Remove larger prefix sums from the back. Remove valid prefix sums from the front whenever the required sum is achieved. Update the minimum subarray length. Time Complexity
O(n)
Space Complexity
O(n)
- Constrained Subsequence Sum (LeetCode 1425) Problem
Find the maximum subsequence sum where consecutive selected elements are at most k positions apart.
Explanation
Dynamic Programming combined with a deque efficiently keeps track of the maximum subsequence sum within the allowed range.
Approach Define dp[i] as the maximum subsequence sum ending at index i. Maintain a deque containing indices with the highest DP values. Update each DP value using the maximum value in the deque. Return the maximum DP value. Time Complexity
O(n)
Space Complexity
O(n)
- Jump Game VI (LeetCode 1696) Problem
Find the maximum score that can be obtained while reaching the last index.
Explanation
At every position, choose the maximum score from the previous k positions.
Approach Use Dynamic Programming to calculate the maximum score at every index. Maintain a deque to store the best DP values. Remove indices that are no longer within the valid range. Update the current score using the best available value. Time Complexity
O(n)
Space Complexity
O(n)
- Merge K Sorted Lists (LeetCode 23) Problem
Merge multiple sorted linked lists into a single sorted linked list.
Explanation
Using a priority queue ensures that the smallest node among all lists can be selected efficiently.
Approach Insert the first node of every linked list into a min-heap. Extract the smallest node. Insert its next node into the heap. Continue until the heap becomes empty. Time Complexity
O(N log K)
Where:
N = Total number of nodes K = Number of linked lists Space Complexity
O(K)
- Reverse Nodes in K-Group (LeetCode 25) Problem
Reverse the nodes of a linked list in groups of size k.
Explanation
Only complete groups of k nodes should be reversed. Any remaining nodes that do not form a complete group remain unchanged.
Approach Count k nodes from the current position. Reverse the current group. Connect the reversed group with the previous one. Repeat until fewer than k nodes remain. Time Complexity
O(n)
Space Complexity
O(1) 21. Copy List with Random Pointer (LeetCode 138) Problem
Given a linked list where each node contains a next pointer and a random pointer, create a deep copy of the list.
Explanation
The copied list should contain entirely new nodes while preserving both the next and random pointer relationships.
Approach Create a copy of each node and insert it immediately after the original node. Assign the random pointer of each copied node using the original node's random pointer. Separate the original and copied lists. Return the head of the copied list. Time Complexity
O(n)
Space Complexity
O(1)
- LFU Cache (LeetCode 460) Problem
Design a Least Frequently Used (LFU) Cache that supports get() and put() operations in constant time.
Explanation
When the cache reaches its capacity, remove the key with the lowest access frequency. If multiple keys have the same frequency, remove the least recently used one.
Approach Use a hash map to store key-value pairs. Maintain another hash map to group keys based on their frequency. Update the frequency whenever a key is accessed. Remove the least frequently used key when the cache is full. Time Complexity get() → O(1) put() → O(1) Space Complexity
O(capacity)
- Sort List (LeetCode 148) Problem
Sort a singly linked list in ascending order.
Explanation
Since random access is not available in linked lists, Merge Sort is the most efficient sorting algorithm.
Approach Find the middle node using slow and fast pointers. Split the list into two halves. Recursively sort both halves. Merge the sorted halves into a single sorted list. Time Complexity
O(n log n)
Space Complexity
O(log n)
- Median of Two Sorted Arrays (Binary Search) (LeetCode 4) Problem
Find the median of two sorted arrays without merging them.
Explanation
Binary search is performed on the smaller array to partition both arrays correctly.
Approach Perform binary search on the smaller array. Partition both arrays into left and right halves. Validate the partition. Compute the median based on the total number of elements. Time Complexity
O(log(min(n, m)))
Space Complexity
O(1)
- Find Minimum in Rotated Sorted Array (LeetCode 153) Problem
Find the minimum element in a rotated sorted array.
Explanation
A rotated sorted array consists of two sorted portions. Binary search efficiently identifies the smallest element.
Approach Compare the middle element with the last element. If the middle element is greater, search the right half. Otherwise, search the left half. Continue until the minimum element is found. Time Complexity
O(log n)
Space Complexity
O(1)
- Search in Rotated Sorted Array (LeetCode 33) Problem
Search for a target element in a rotated sorted array.
Explanation
At least one half of the array is always sorted. Binary search can determine which half should be explored.
Approach Find the middle element. Determine whether the left or right half is sorted. Check whether the target belongs to the sorted half. Continue searching until the target is found or the search space becomes empty. Time Complexity
O(log n)
Space Complexity
O(1)
- Search a 2D Matrix (LeetCode 74) Problem
Determine whether a target value exists in a sorted 2D matrix.
Explanation
Since the matrix behaves like a sorted one-dimensional array, binary search can be applied directly.
Approach Treat the matrix as a flattened sorted array. Perform binary search. Convert the one-dimensional index into row and column indices during each iteration. Return whether the target is found. Time Complexity
O(log(rows × columns))
Space Complexity
O(1)
- Kth Smallest Element in a Sorted Matrix (LeetCode 378) Problem
Find the kth smallest element in a sorted matrix.
Explanation
Each row and column of the matrix is sorted. Binary search is performed on the value range rather than on indices.
Approach Perform binary search between the smallest and largest values. Count how many elements are less than or equal to the current middle value. Adjust the search range based on the count. Continue until the answer is found. Time Complexity
O(n log(max - min))
Space Complexity
O(1)
- Split Array Largest Sum (LeetCode 410) Problem
Split an array into k continuous subarrays such that the largest subarray sum is minimized.
Explanation
Binary search is applied to the possible range of answers while greedily checking whether a valid partition is possible.
Approach Set the search range between the maximum array element and the total array sum. For each candidate value, determine the number of subarrays required. If more than k subarrays are needed, increase the search range. Otherwise, reduce the search range. Time Complexity
O(n log(sum))
Space Complexity
O(1)
- Capacity To Ship Packages Within D Days (LeetCode 1011) Problem
Determine the minimum ship capacity required to deliver all packages within D days.
Explanation
A larger ship capacity reduces the number of days required. Binary search efficiently finds the minimum valid capacity.
Approach Set the minimum capacity as the maximum package weight. Set the maximum capacity as the sum of all package weights. Use binary search to test possible capacities. Simulate the shipping process to verify whether the packages can be delivered within D days. Time Complexity
O(n log(sum))
Space Complexity
O(1) 31. Binary Tree Maximum Path Sum (LeetCode 124) Problem
Find the maximum path sum in a binary tree. A path can start and end at any node.
Explanation
A valid path may pass through the current node by combining the maximum contribution from its left and right subtrees. Negative path sums are ignored since they reduce the overall result.
Approach Perform a post-order traversal. Compute the maximum gain from the left and right subtrees. Ignore negative gains by treating them as zero. Update the global maximum using the current node and both subtree gains. Return the maximum gain contributed by the current node. Time Complexity
O(n)
Space Complexity
O(h)
- Serialize and Deserialize Binary Tree (LeetCode 297) Problem
Convert a binary tree into a string and reconstruct the original tree from that string.
Explanation
Serialization stores the tree structure, while deserialization rebuilds the exact tree.
Approach Perform a preorder traversal. Store null nodes using a special marker. During deserialization, recursively rebuild the tree using the stored values. Return the reconstructed tree. Time Complexity
O(n)
Space Complexity
O(n)
- Lowest Common Ancestor of a Binary Tree (LeetCode 236) Problem
Find the lowest common ancestor of two given nodes in a binary tree.
Explanation
The lowest common ancestor is the deepest node that has both target nodes as descendants.
Approach Traverse the tree recursively. If the current node matches either target, return it. Search both left and right subtrees. If both sides return valid nodes, the current node is the answer. Otherwise, return the non-null subtree. Time Complexity
O(n)
Space Complexity
O(h)
- Binary Tree Zigzag Level Order Traversal (LeetCode 103) Problem
Return the level order traversal of a binary tree in zigzag order.
Explanation
Nodes are traversed level by level, but the direction alternates between left-to-right and right-to-left.
Approach Perform Breadth-First Search (BFS). Process one level at a time. Reverse the level values whenever the traversal direction changes. Store the result for every level. Time Complexity
O(n)
Space Complexity
O(n)
- Vertical Order Traversal of a Binary Tree (LeetCode 987) Problem
Return the vertical order traversal of a binary tree.
Explanation
Nodes are grouped based on their horizontal distance from the root. If multiple nodes share the same position, they are sorted according to the problem constraints.
Approach Perform DFS or BFS while tracking row and column indices. Store nodes according to their column values. Sort nodes based on row and node value. Return the grouped columns from left to right. Time Complexity
O(n log n)
Space Complexity
O(n)
- Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105) Problem
Construct a binary tree using its preorder and inorder traversals.
Explanation
The first element in preorder is always the root. The inorder traversal divides the tree into left and right subtrees.
Approach Select the first preorder element as the root. Locate the root in the inorder traversal. Recursively construct the left subtree. Recursively construct the right subtree. Time Complexity
O(n)
Space Complexity
O(n)
- Validate Binary Search Tree (LeetCode 98) Problem
Determine whether a binary tree satisfies the properties of a Binary Search Tree.
Explanation
Every node must be greater than all nodes in its left subtree and smaller than all nodes in its right subtree.
Approach Traverse the tree recursively. Maintain valid minimum and maximum boundaries. Verify that every node lies within its allowed range. Return false if any node violates the BST property. Time Complexity
O(n)
Space Complexity
O(h)
- Kth Smallest Element in a BST (LeetCode 230) Problem
Find the kth smallest element in a Binary Search Tree.
Explanation
An inorder traversal of a BST visits nodes in ascending order.
Approach Perform an inorder traversal. Count visited nodes. Return the value when the count reaches k. Time Complexity
O(n)
Space Complexity
O(h)
- Recover Binary Search Tree (LeetCode 99) Problem
Recover a Binary Search Tree where two nodes have been swapped by mistake.
Explanation
The inorder traversal of a valid BST should always be sorted. Swapped nodes create violations in this order.
Approach Perform an inorder traversal. Identify the misplaced nodes by detecting order violations. Swap their values to restore the BST. Time Complexity
O(n)
Space Complexity
O(h)
- Flatten Binary Tree to Linked List (LeetCode 114) Problem
Flatten a binary tree into a linked list following preorder traversal.
Explanation
After flattening, every node should have only a right child, forming a linked list.
Approach Perform a reverse preorder traversal. Keep track of the previously processed node. Connect the current node's right pointer to the previous node. Set the left pointer to null. Time Complexity
O(n)
Space Complexity
O(h)
- Word Ladder (LeetCode 127) Problem
Find the length of the shortest transformation sequence from the begin word to the end word.
Explanation
Only one character can be changed at a time, and every intermediate word must exist in the given dictionary.
Approach Use Breadth-First Search (BFS). Generate all possible one-character transformations. Visit only valid dictionary words. Return the shortest transformation length. Time Complexity
O(N × L × 26)
Where:
N = Number of words L = Length of each word Space Complexity
O(N)
- Course Schedule (LeetCode 207) Problem
Determine whether all courses can be completed given their prerequisite relationships.
Explanation
The courses form a directed graph. A cycle indicates that completing all courses is impossible.
Approach Build a directed graph. Calculate the indegree of every node. Perform Topological Sorting using BFS. If all nodes are processed, all courses can be completed. Time Complexity
O(V + E)
Space Complexity
O(V + E)
- Number of Islands (LeetCode 200) Problem
Count the number of islands in a binary grid.
Explanation
An island is formed by connected land cells. Water cells separate different islands.
Approach Traverse every cell. When an unvisited land cell is found, perform DFS or BFS. Mark all connected land cells as visited. Increment the island count. Time Complexity
O(m × n)
Space Complexity
O(m × n)
- Network Delay Time (LeetCode 743) Problem
Find the minimum time required for a signal to reach all nodes in a network.
Explanation
The graph contains weighted edges. The shortest path from the source to every node determines the total delay.
Approach Represent the network as an adjacency list. Apply Dijkstra's Algorithm using a priority queue. Compute the shortest distance to every node. Return the maximum shortest distance. Time Complexity
O((V + E) log V)
Space Complexity
O(V + E)
- Alien Dictionary (LeetCode 269) Problem
Determine the order of characters in an unknown language using a sorted list of words.
Explanation
Character precedence creates a directed graph. Topological sorting reveals the valid character order.
Approach Compare adjacent words to identify character relationships. Build a directed graph. Calculate indegrees. Perform Topological Sorting. Return the derived character order. Time Complexity
O(C)
Where:
C = Total number of characters across all words Space Complexity
O(V + E) 46. LRU Cache (LeetCode 146) Problem
Design a Least Recently Used (LRU) Cache that supports get() and put() operations in constant time.
Explanation
When the cache reaches its capacity, the least recently used item should be removed before inserting a new one.
Approach Use a hash map for direct key lookup. Use a doubly linked list to maintain the order of recently used elements. Move accessed nodes to the front of the list. Remove the node at the end when the cache exceeds its capacity. Time Complexity get() → O(1) put() → O(1) Space Complexity
O(capacity)
- Longest Increasing Subsequence (LeetCode 300) Problem
Find the length of the longest strictly increasing subsequence in an array.
Explanation
The subsequence does not need to be continuous. The goal is to maximize its length while maintaining increasing order.
Approach Maintain a list that stores the smallest possible ending value for increasing subsequences. Use Binary Search to find the correct position for each element. Replace or append elements accordingly. The size of the list represents the answer. Time Complexity
O(n log n)
Space Complexity
O(n)
- Coin Change (LeetCode 322) Problem
Given different coin denominations, find the minimum number of coins required to make a target amount.
Explanation
Each coin can be used multiple times. If the amount cannot be formed, return -1.
Approach Use Dynamic Programming. Define dp[i] as the minimum coins required to make amount i. Initialize all values with infinity except dp[0]. Update the DP array for every coin. Return the final DP value. Time Complexity
O(amount × number of coins)
Space Complexity
O(amount)
- Longest Common Subsequence (LeetCode 1143) Problem
Find the length of the longest subsequence common to two strings.
Explanation
Characters do not need to be adjacent, but their relative order must remain unchanged.
Approach Use Dynamic Programming. Create a DP table where each cell stores the LCS length for two prefixes. If characters match, extend the subsequence. Otherwise, take the maximum value from the neighboring states. Time Complexity
O(m × n)
Space Complexity
O(m × n)
- Edit Distance (LeetCode 72) Problem
Find the minimum number of operations required to convert one string into another.
Explanation
The allowed operations are insertion, deletion, and replacement.
Approach Use Dynamic Programming. Create a DP table representing the minimum operations for every pair of prefixes. If characters match, copy the previous value. Otherwise, compute the minimum among insert, delete, and replace operations. Time Complexity
O(m × n)
Space Complexity
O(m × n)
- Word Break (LeetCode 139) Problem
Determine whether a string can be segmented into valid dictionary words.
Explanation
Every segment of the string must exist in the given dictionary.
Approach Use Dynamic Programming. Let dp[i] indicate whether the prefix ending at index i can be segmented. Check every possible partition using dictionary words. Return the final DP value. Time Complexity
O(n²)
Space Complexity
O(n)
- N-Queens (LeetCode 51) Problem
Place N queens on an N × N chessboard so that no two queens attack each other.
Explanation
Queens attack horizontally, vertically, and diagonally. Every valid arrangement should satisfy these constraints.
Approach Use Backtracking. Place queens row by row. Check whether the current position is safe. Continue recursively until all queens are placed. Backtrack whenever a conflict occurs. Time Complexity
O(N!)
Space Complexity
O(N)
- Sudoku Solver (LeetCode 37) Problem
Solve a partially filled Sudoku board.
Explanation
Every row, column, and 3 × 3 subgrid must contain digits from 1 to 9 exactly once.
Approach Use Backtracking. Find the next empty cell. Try placing digits from 1 to 9. Validate every placement. Continue recursively until the puzzle is solved. Time Complexity
O(9^(empty cells)) (Worst Case)
Space Complexity
O(empty cells)
- Permutations (LeetCode 46) Problem
Generate all possible permutations of a given array.
Explanation
Each element should appear exactly once in every permutation.
Approach Use Backtracking. Select an unused element. Add it to the current permutation. Continue recursively until all elements are used. Backtrack to explore other possibilities. Time Complexity
O(n × n!)
Space Complexity
O(n)
- Combination Sum (LeetCode 39) Problem
Find all unique combinations of numbers whose sum equals the target value.
Explanation
Each number can be chosen multiple times, and only valid combinations should be returned.
Approach Use Backtracking. Maintain the current combination and remaining target. Include the current number as long as the remaining target is non-negative. Backtrack to explore other combinations. Store every valid combination. Time Complexity
O(2^n) (Approximate, depends on input)
Space Complexity
O(target) (Recursion stack excluding output)