dsa1 min read
Candy [Hard/Medium] — Two-Pass Greedy
Distribute minimum candies so each child with higher rating than neighbors gets more, using left-to-right then right-to-left passes.
Read →
Hard
120 articles
dsa2 min read
Trapping Rain Water [Hard] — Two Pointers O(n)
Calculate trapped rain water using inward two pointers that track left-max and right-max, replacing the classic O(n) space approach.
Read →
dsa2 min read
Sliding Window Maximum [Hard] — Monotonic Deque
Find the maximum in every sliding window of size k in O(n) using a monotonic decreasing deque.
Read →
dsa2 min read
First Missing Positive [Hard] — Cyclic Sort / Index Marking
Find the smallest missing positive integer in O(n) time O(1) space using in-place cyclic sort to place each number at its correct index.
Read →
dsa2 min read
Largest Rectangle in Histogram [Hard] — Monotonic Stack
Find the largest rectangle in a histogram in O(n) using a monotonic increasing stack that computes area when a shorter bar is encountered.
Read →
dsa2 min read
Minimum Window Substring [Hard] — Sliding Window with Frequency Map
Find the minimum window in s that contains all characters of t using a shrinkable sliding window with a character frequency counter.
Read →
dsa2 min read
Count of Smaller Numbers After Self [Hard] — Merge Sort
Count elements smaller than each element to its right using a modified merge sort that counts inversions during the merge step.
Read →
dsa2 min read
Median of Two Sorted Arrays [Hard] — Binary Search on Partition
Find the median of two sorted arrays in O(log(min(m,n))) by binary searching for the correct partition point.
Read →
dsa2 min read
Maximal Rectangle [Hard] — Histogram Stack per Row
Find the largest rectangle of 1s in a binary matrix by treating each row as a histogram and applying the Largest Rectangle in Histogram algorithm.
Read →
dsa2 min read
Reverse Pairs [Hard] — Merge Sort with Cross-Half Counting
Count pairs (i,j) where i<j and nums[i]>2*nums[j] using modified merge sort to count cross-half pairs before merging.
Read →
dsa1 min read
Split Array Largest Sum [Hard] — Binary Search on Answer
Minimize the largest sum among m subarrays by binary searching on the answer and greedy checking feasibility.
Read →
dsa1 min read
Shortest Subarray with Sum ≥ K [Hard] — Deque on Prefix Sums
Find the shortest subarray with sum >= K using a monotonic deque on prefix sums, handling negative numbers correctly.
Read →
dsa2 min read
Count of Range Sum [Hard] — Merge Sort on Prefix Sums
Count the number of range sums that lie in [lower, upper] using a merge sort approach on prefix sums.
Read →
dsa2 min read
Maximum Sum of 3 Non-Overlapping Subarrays [Hard] — Sliding Window + DP
Find three non-overlapping subarrays of length k with maximum sum using sliding window sums and left/right best index arrays.
Read →
dsa2 min read
Minimum Number of Refueling Stops [Hard] — Greedy Max-Heap
Find the minimum refueling stops to reach target by greedily picking the largest fuel station passed so far whenever we run out.
Read →
dsa1 min read
Max Points on a Line [Hard] — Slope HashMap
Find the maximum number of points on the same line using a slope-as-fraction HashMap for each anchor point.
Read →
dsa1 min read
Longest Valid Parentheses [Hard] — Stack / DP
Find the longest valid parentheses substring using a stack that tracks the last unmatched index as a base.
Read →
dsa1 min read
Subarrays with K Different Integers [Hard] — Sliding Window Subtract
Count subarrays with exactly K distinct integers using the formula: atMost(K) - atMost(K-1).
Read →
dsa1 min read
Stamping the Sequence [Hard] — Reverse Greedy
Reconstruct the stamp sequence in reverse by greedily finding where the stamp can overwrite current characters in the target string.
Read →
dsa2 min read
Longest Duplicate Substring [Hard] — Binary Search + Rolling Hash
Find the longest substring that appears at least twice using binary search on length and Rabin-Karp rolling hash for O(n log n) average time.
Read →
dsa2 min read
Maximum Frequency Stack [Hard] — Frequency + Group Stacks
Design a stack that pops the most frequent element (breaking ties by recency) using frequency and group-stacks mapping.
Read →
dsa1 min read
Find Minimum in Rotated Sorted Array II — Duplicates Handling
Find the minimum in a rotated array with duplicates by shrinking hi-- when nums[mid]==nums[hi].
Read →
dsa2 min read
Median of Two Sorted Arrays — Binary Search on Partition
Find the median of two sorted arrays in O(log(min(m,n))) by binary searching for the correct partition point.
Read →
dsa1 min read
Count Smaller Numbers After Self — Merge Sort or Binary Indexed Tree
Count smaller elements to the right of each element using merge sort with position tracking in O(n log n).
Read →
dsa1 min read
Russian Doll Envelopes — Sort + LIS Binary Search
Find the maximum number of nested envelopes by sorting by width ascending then height descending, then applying LIS.
Read →
dsa1 min read
Cutting Ribbons — Binary Search on Answer (Length)
Find the maximum length to cut k ribbons from given ribbons using binary search on the ribbon length.
Read →
dsa1 min read
Aggressive Cows — Binary Search on Minimum Distance
Place c cows in stalls to maximize the minimum distance between any two cows using binary search on the answer.
Read →
dsa1 min read
Count of Range Sum — Merge Sort on Prefix Sums
Count subarrays with sum in [lower, upper] using merge sort on prefix sums for O(n log n) complexity.
Read →
dsa1 min read
K-th Smallest Prime Fraction — Binary Search on Value
Find the kth smallest prime fraction from an array using binary search on the fraction value with a counting function.
Read →
dsa1 min read
Kth Element of Two Sorted Arrays — Binary Search Elimination
Find the kth smallest element from two sorted arrays in O(log(m+n)) using binary elimination of k/2 elements per step.
Read →
dsa1 min read
Minimum XOR Sum of Two Arrays — Bitmask DP
Assign each element of nums1 to exactly one element of nums2 to minimize XOR sum. Classic assignment bitmask DP: dp[mask] = min XOR sum.
Read →
dsa1 min read
Number of Valid Words for Each Puzzle — Bitmask Subset
Count words that contain puzzle[0] and only letters from puzzle. Encode words as bitmasks, for each puzzle enumerate its subsets containing puzzle[0].
Read →
dsa1 min read
Russian Doll Envelopes — 2D LIS
Maximum envelopes you can nest. Sort by width ascending and height descending, then LIS on heights. Descending heights prevents using same-width twice.
Read →
dsa1 min read
Edit Distance — Wagner-Fischer DP
Minimum operations (insert, delete, replace) to transform word1 to word2. Classic Wagner-Fischer 2D DP with O(n) space optimization.
Read →
dsa1 min read
Shortest Common Supersequence — LCS + Reconstruct
Find shortest string containing both strings as subsequences. Length = len(s1)+len(s2)-LCS. Reconstruct by tracing DP table.
Read →
dsa1 min read
Burst Balloons — Interval DP
Maximize coins by bursting balloons. Key insight: think of last balloon burst in interval [i,j]. dp[i][j] = max coins from interval with k as last balloon.
Read →
dsa1 min read
Best Time Buy/Sell Stock III — At Most 2 Transactions
Maximize profit with at most 2 transactions. Track 4 states: buy1, sell1, buy2, sell2. State machine DP.
Read →
dsa1 min read
Best Time Buy/Sell Stock IV — At Most k Transactions
At most k transactions. dp[t][i] = max profit using t transactions up to day i. If k >= n/2, unlimited transactions.
Read →
dsa1 min read
Regular Expression Matching — 2D DP
Match string s against pattern p with . and *. dp[i][j] = does s[:i] match p[:j]. Handle * by matching zero or more of preceding char.
Read →
dsa1 min read
Wildcard Matching — 2D DP
Match string with wildcard pattern: ? matches any char, * matches any sequence. Similar to regex but * matches any sequence (not zero/more of preceding).
Read →
dsa1 min read
Dungeon Game — Reverse Grid DP
Find minimum initial health to reach bottom-right dungeon cell. Solve backwards: dp[i][j] = min health needed at (i,j) to survive.
Read →
dsa1 min read
Strange Printer — Interval DP
Minimum turns to print string where each turn prints a contiguous run of same char. Interval DP: dp[i][j] = min turns for s[i..j].
Read →
dsa1 min read
Making a Large Island — DFS Color Map + Merge
Find the largest island after flipping exactly one 0 to 1. Color each island with DFS, store sizes, then check each 0 cell's unique neighbour islands.
Read →
dsa1 min read
Shortest Bridge — DFS Find + BFS Expand
Find minimum flips to connect two islands. DFS to find and color first island, then BFS outward until reaching second island.
Read →
dsa2 min read
Minimum Effort Path — Dijkstra / Binary Search + BFS
Find path from top-left to bottom-right minimizing maximum absolute difference between consecutive cells. Use Dijkstra or binary search + BFS.
Read →
dsa2 min read
Number of Islands II — Union-Find Online Queries
Count islands after each addLand operation. Online version requires Union-Find: add each land cell and union with adjacent land cells.
Read →
dsa1 min read
Word Ladder II — BFS Shortest Paths + DFS Reconstruct
Find ALL shortest transformation sequences. BFS builds layer map, DFS reconstructs all paths backwards from endWord to beginWord.
Read →
dsa1 min read
Bus Routes — BFS on Route Graph
Find minimum buses to get from source to target stop. BFS where nodes are routes (buses), not stops. Jump to all stops of a route, then to all routes passing through each stop.
Read →
dsa1 min read
Reachable Nodes in Subdivided Graph — Dijkstra
Count total reachable nodes in a subdivided graph within M moves. Dijkstra from node 0 gives max remaining moves at each node; use those to count subdivisions.
Read →
dsa1 min read
Candy — Two-Pass Greedy
Distribute minimum candies with higher-rated children getting more than neighbors. Two-pass: left-to-right for ascending, right-to-left for descending.
Read →
dsa1 min read
Largest Rectangle in Histogram — Monotonic Stack
Find the area of the largest rectangle in a histogram. Monotonic increasing stack: when a shorter bar is found, pop and compute rectangle area using popped height and current width.
Read →
dsa1 min read
Trapping Rain Water — Two Pointer O(1) Space
Calculate water trapped between bars. Two-pointer approach: maintain max_left and max_right; water at each position = min(max_left, max_right) - height.
Read →
dsa1 min read
Maximal Rectangle — Histogram per Row
Find the largest rectangle in a binary matrix. Build histogram row by row (reset to 0 on '0'), apply Largest Rectangle in Histogram each row.
Read →
dsa2 min read
LFU Cache — HashMap + Frequency Buckets + DLL
Implement an LFU cache with O(1) get/put using three hash maps: key→val, key→freq, freq→OrderedDict.
Read →
dsa2 min read
All O'one Data Structure — DLL of Buckets + HashMap
Design a data structure supporting inc/dec and getMaxKey/getMinKey in O(1) using a doubly linked list of frequency buckets.
Read →
dsa2 min read
Design Twitter — HashMap + Heap for News Feed
Design Twitter with follow/unfollow and getNewsFeed using per-user tweet lists and a min-heap merge.
Read →
dsa2 min read
Palindrome Pairs — HashMap + Palindrome Check
Find all index pairs forming palindromes by checking prefix/suffix splits against a reverse-word map.
Read →
dsa2 min read
Find Median from Data Stream
Maintain a dynamic median using two heaps: a max-heap for the lower half and a min-heap for the upper half.
Read →
dsa3 min read
Sliding Window Median
Compute medians of all sliding windows using two heaps with lazy deletion for element removal.
Read →
dsa2 min read
Merge K Sorted Lists
Merge K sorted linked lists into one sorted list using a min-heap to always extract the globally smallest node.
Read →
dsa2 min read
Course Schedule III
Maximize courses taken within deadlines by greedily scheduling and swapping out the longest past course.
Read →
dsa2 min read
IPO
Maximize capital after k IPO investments by greedily picking the highest profit project among affordable ones.
Read →
dsa3 min read
Trapping Rain Water II
Calculate trapped water in a 3D height map using BFS with a min-heap to process cells from shortest boundary inward.
Read →
dsa3 min read
Swim in Rising Water
Find minimum time to swim from top-left to bottom-right in a grid where time = max elevation on the path.
Read →
dsa3 min read
Smallest Range Covering Elements from K Lists
Find the smallest range that contains at least one element from each of K sorted lists using a sliding K-way merge.
Read →
dsa2 min read
Minimum Number of Refueling Stops
Find minimum fuel stops to reach the target by greedily selecting the largest available fuel stations when running low.
Read →
dsa2 min read
Maximum Performance of a Team
Maximize team performance (sum of speeds * min efficiency) by sorting by efficiency and using a min-heap on speeds.
Read →
dsa2 min read
Maximum Frequency Stack
Design a stack that pops the most frequent element, breaking ties by most recently pushed, using frequency-bucket stacks.
Read →
dsa2 min read
Minimize Deviation in Array
Minimize max-min of an array by doubling odd numbers and repeatedly halving the max using a max-heap.
Read →
dsa2 min read
Median of K Sliding Windows (Extended Practice)
Extended practice: compute median for each window in a stream using two-heap with lazy deletion pattern.
Read →
dsa2 min read
Minimum Interval to Include Each Query
For each query point, find the smallest interval containing it by sorting both intervals and queries, using a min-heap.
Read →
dsa2 min read
Reverse Nodes in k-Group — Recursive Group Reversal
Reverse every k nodes of a linked list recursively: check k nodes exist, reverse them, recurse on the rest.
Read →
dsa2 min read
Merge K Sorted Lists — Min-Heap or Divide and Conquer
Merge k sorted linked lists into one sorted list using a min-heap for O(n log k) time complexity.
Read →
dsa2 min read
Sort List Bottom-Up — O(1) Space Merge Sort
Sort a linked list in O(n log n) time and O(1) space using bottom-up merge sort with doubling sublist sizes.
Read →
dsa2 min read
Convert Sorted List to BST — In-Order O(n) Build
Build a balanced BST from a sorted list in O(n) by counting nodes, building in-order, and consuming list nodes.
Read →
dsa2 min read
LRU Cache — Doubly Linked List + HashMap Implementation
Implement LRU Cache from scratch using a doubly linked list with sentinel nodes and a hash map for O(1) operations.
Read →
dsa2 min read
Design Browser History — Doubly Linked List Implementation
Design a browser history with visit, back, and forward operations using a doubly linked list for O(1) navigation.
Read →
dsa1 min read
Count of Smaller Numbers After Self — BIT + Coordinate Compress
Count smaller elements to the right of each element. Process from right to left; BIT tracks seen elements. Coordinate compress values to BIT indices.
Read →
dsa1 min read
Reverse Pairs — Merge Sort / BIT
Count pairs (i,j) where i<j and nums[i] > 2*nums[j]. Modified merge sort: during merge, count pairs across left/right halves.
Read →
dsa1 min read
Range Module — Segment Tree / SortedDict
Track coverage of half-open intervals. addRange, removeRange, queryRange. Sorted dictionary of disjoint intervals with merge/split logic.
Read →
dsa1 min read
Falling Squares — Coordinate Compress + Segment Tree
Simulate falling squares, track tallest stack height. Coordinate compress x-coordinates, use segment tree with lazy propagation for range max.
Read →
dsa1 min read
Count of Range Sum — Merge Sort / BIT
Count subarray sums within [lower, upper]. Use prefix sums and merge sort: during merge count pairs of prefix sums with difference in range.
Read →
dsa1 min read
My Calendar III — Difference Array / Seg Tree
Track maximum booking overlaps at any time. Difference array: +1 at start, -1 at end; running max of prefix sum. Lazy segment tree for dynamic range.
Read →
dsa1 min read
Max Sum Rectangle No Larger than K — BIT + Prefix
Find max rectangle sum <= k in 2D matrix. Fix row boundaries, compress to 1D array, use prefix sums + BIT/sorted set to find best subarray sum <= k.
Read →
dsa1 min read
Shortest Subarray with Sum at Least K — Deque + Prefix Sum
Find the shortest subarray with sum >= k using a monotonic deque on prefix sums for O(n) time.
Read →
dsa1 min read
Design Hit Counter — Queue with Timestamp Expiry
Design a hit counter that returns hits in the past 5 minutes using a queue to expire old timestamps.
Read →
dsa1 min read
Largest Rectangle in Histogram — Monotonic Increasing Stack
Find the largest rectangle in a histogram by computing left and right boundaries using a monotonic increasing stack.
Read →
dsa1 min read
Maximal Rectangle — Histogram Stack on Each Row
Find the maximal rectangle in a binary matrix by building histogram heights row by row and applying largest rectangle.
Read →
dsa2 min read
Basic Calculator I — Stack for Sign and Parentheses
Evaluate a basic expression with +, -, and parentheses using a stack to save and restore sign context.
Read →
dsa2 min read
Maximum Frequency Stack — Bucket-per-Frequency Design
Design a frequency stack with O(1) push and pop-max-frequency using a map of frequency to stack of elements.
Read →
dsa2 min read
Find Median from Data Stream — Two Heaps
Find the median dynamically as numbers are added using two heaps: a max-heap for the lower half and min-heap for upper.
Read →
dsa1 min read
Serialize and Deserialize Binary Tree — BFS Level Order
Serialize a binary tree to a string using BFS level-order and deserialize back using a queue for reconstruction.
Read →
dsa2 min read
Trapping Rain Water — Monotonic Stack Horizontal Layer
Calculate trapped rainwater volume using a monotonic stack that computes water in horizontal layers as bars are processed.
Read →
dsa2 min read
Binary Tree Cameras
Find minimum cameras to monitor all nodes using greedy bottom-up: prefer placing cameras at parents of uncovered leaves.
Read →
dsa2 min read
Binary Tree Maximum Path Sum
Find the maximum path sum in a binary tree where the path can start and end at any node.
Read →
dsa2 min read
Serialize and Deserialize Binary Tree
Serialize a binary tree to string and back using BFS level-order or DFS preorder with null markers.
Read →
dsa2 min read
Maximum Sum BST in Binary Tree
Find the maximum sum of any BST subtree within a binary tree using post-order DFS returning subtree metadata.
Read →
dsa3 min read
Sum of Distances in Tree
Compute sum of distances from every node to all others in O(n) using two DFS passes with rerooting technique.
Read →
dsa2 min read
Path Sum IV
Sum all root-to-leaf path sums in a tree encoded as 3-digit integers using a hashmap to decode tree structure.
Read →
dsa2 min read
Closest Binary Search Tree Value II
Find k values closest to target in a BST using two in-order iterators (forward and reverse) with a two-pointer merge.
Read →
dsa2 min read
Word Search II — Trie + Grid DFS Pruning
Find all words from a list in a grid. Build trie from words, DFS on grid while traversing trie simultaneously to prune early.
Read →
dsa1 min read
Palindrome Pairs — Trie + Palindrome Check
Find pairs (i,j) where words[i]+words[j] is a palindrome. Insert reversed words into trie, for each word check palindromic suffix/prefix conditions.
Read →
dsa1 min read
Stream of Characters — Reverse Suffix Trie
Query if any word ends at the current stream position. Insert reversed words into trie; maintain suffix deque to match from current position backwards.
Read →
dsa1 min read
Prefix and Suffix Search — Combined Key Trie
Find word with given prefix AND suffix. Insert 'suffix#word' for each suffix of each word into trie; query combines prefix+suffix search.
Read →
dsa1 min read
Sum of Prefix Scores of Strings — Trie Count
For each word, sum up how many other words share each of its prefixes. Trie with prefix count at each node; query each word's prefix sum.
Read →
dsa1 min read
Concatenated Words — Trie + Word Break
Find all words that can be formed by concatenating two or more words from the same list. Build trie, then run word break DP on each word.
Read →
dsa1 min read
Maximum XOR With an Element — Offline Trie
For each query (xi, mi), find max xi XOR with element ≤ mi. Offline: sort queries and elements by value, add elements up to mi, query trie.
Read →
dsa1 min read
Subarrays with K Different Integers [Hard] — atMost(K)−atMost(K−1)
Count subarrays with exactly K distinct integers using the mathematical trick: exactly(K) = atMost(K) - atMost(K-1).
Read →
dsa1 min read
Count Subarrays With Fixed Bounds [Hard] — One-Pass Window
Count subarrays where min=minK and max=maxK using a single pass tracking the last invalid position and last positions of minK and maxK.
Read →
dsa2 min read
Minimum Window Subsequence [Hard] — Forward + Backward Two Ptr
Find the minimum window in s that contains t as a subsequence by using a forward pass to find a valid window then backward pass to minimize it.
Read →
dsa2 min read
Count Subarrays Where Median Equals K [Hard] — Prefix Balance
Count subarrays where the median is exactly k by converting the problem to counting balanced prefix sequences around k.
Read →
dsa2 min read
Sliding Window Median [Hard] — Two Heaps with Lazy Deletion
Find the median of each sliding window of size k using two heaps (max-heap for lower half, min-heap for upper half) with lazy deletion.
Read →
dsa2 min read
Substring with Concatenation of All Words [Hard] — Multi-Start Window
Find all starting indices of substrings that are concatenations of all given words using a sliding window for each possible word-aligned start.
Read →
dsa1 min read
Count Subarrays with Score Less Than K [Hard] — Shrinkable Window
Count subarrays where score = sum × length is less than k using a shrinkable sliding window with running sum.
Read →
dsa2 min read
Minimum Window Substring [Hard] — have/need Frequency Counter
Find the smallest window in s containing all characters of t using a have/need counter to track when the window is valid.
Read →
dsa1 min read
Sliding Window Maximum [Hard] — Monotonic Decreasing Deque
Find the maximum in every sliding window of size k in O(n) using a monotonic decreasing deque of indices.
Read →
dsa1 min read
Shortest Subarray with Sum ≥ K [Hard] — Monotonic Deque on Prefix
Find the shortest subarray with sum >= k, handling negative numbers correctly using a monotonic deque on prefix sums.
Read →
dsa1 min read
Longest Substring with At Most Two Distinct Characters [Hard]
Find the longest substring containing at most 2 distinct characters using a variable sliding window with a character count map.
Read →
dsa1 min read
Trapping Rain Water [Hard] — Two Pointer Classic
Calculate trapped rainwater using optimal two-pointer approach that tracks left and right maximums without extra space.
Read →
dsa3 min read
Mock Week 3 — Hard Problems Under Time Pressure
Week 3 mock focuses on hard problems. Strategy: get a working solution in 35 minutes, optimize in remaining 15. Includes triage framework for when you're stuck on a hard problem.
Read →