Questions for Learning¶

Table of Contents

Arrays
Strings
- Prefix
- Rolling Hash
Trees
Graphs
Streaming
- Counts
- States
- Search
- Misc

Arrays¶

Unordered Explicit Range - Search¶

Ordered Explicit Range - Binary Search¶

Ordered Implicit Range - Binary Search¶

[Easy] Arranging Coins
[Medium] Koko Eating Bananas
[Medium] Capacity To Ship Packages Within D Days
[Medium] Minimum Number of Days to Make m Bouquets
[Medium] Minimize Constrained Sum (House Robber IV)
[Medium] Median of Row Wise Sorted Matrix
[Hard] Median of 2 Sorted Arrays

Find Global Optima - Convex/Mountain Structure¶

Find Local Optima - Unordered¶

Consecutive Values¶

[Medium] If Entire Array Made of Consecutive Numbers
[Hard] If not, Minimum Replacement Operations to Make it
[Hard] Can Array be Partitioned into K Subarrays of Consecutive Numbers?
[Hard] Can Sorted Array be Partitioned into Consecutive Subsequences?
[Medium] Longest Harmonious Subsequence
[Medium] Longest Sequence Containing Consecutive Numbers
[Medium] Longest Sequence Containing Consecutive Numbers in Tree
[Medium] Maximum Gap Between Values in Sorted Order

Contiguous Segments of Same Value¶

[Easy] Find Maximum Number of Consecutive Ones
[Medium] Check if Longest Consecutive 1s is Longer Than Longst Consecutive 0s
[Medium] Find Maximal Square in a Binary Matrix
[Hard] Find Maximal Rectangle in a Binary Matrix
[Medium] Maximum Number of Consecutive Ones If We Can Flip 1 Zero
[Medium] Maximum Number of Consecutive Ones If We Can Delete 1 Zero
[Medium] Maximum Number of Consecutive Ones If We Can Flip k Zeros, Variant
[Medium] Minimum Adjacent Swaps to Make All Ones Consecutive
[Hard] Minimum Adjacent Swaps for K Consecutive Ones

Inversions¶

[Medium] Count Adjacent Swaps To Move Min Left Max Right
[Hard] Count Inversions

Order Statistics¶

[Medium] Kth Largest Element in Array
[Easy] Kth Largest Element in Stream
[Hard] Max in Fixed Range
[Hard] Median in Stream
[Hard] K-th Maximum for K-th Query
[Hard] Mean of Last m excluding smallest & largest k of them

MEX (Minimal Excluded Element)¶

[Hard] Find First Missing Positive
[Hard] Find Kth Missing Positive
[Medium] Find All Missing Positives
[Medium] Add First K Missing Positives
[Medium] [MEX without duplicates] Design Streamer with PopSmallest & AddBack
- Think of it as if we’re creating an array by calling the streamer.
- In absence of an addback feature, we’d just need to keep track of last streamed element.
- Streamed numbers form a contiguous region. Addback feature creates holes in that region.
- If holes are kept in a sorted container, we can find MEX easily.
[Medium] MEX After Add/Sub Value Any Number of Times

Range Missing¶

[Medium] Find Missing from Array Size n in Range [0,n]
[Medium] Find Repeated from Array Size n+1 in Range [1,n]

Missing Ranges¶

[Easy] Given array, find shortest list of missing ranges
[Easy] Given range, find all missing sub ranges
[Medium] Given list of sub ranges, find missing ranges between [0,n-1]
[Hard] Data stream as disjointed intervals

Find Optimal Range/Count - Constrainted Order/Span Query¶

[Easy] Find Longest Strictly Increasing Subarray
[Easy] Find Longest Strict Monotonic Subarray
[Medium] Find Minimum Removals to Make Rest Sorted
[Medium] Find Shortest Chunk to Sort to Make Entire Array Sorted
- Note: Cannot be removed. Have to keep in the Cartesian tree. Two pointers to find span of largest inverted range.
[Medium] Find Shortest Chunk Removal to Make Remaining Array Sorted
- Note: Can be removed. Cartesian tree building dynamics would change. Two pointers to simulate.
[Hard] Count Chunks to Remove to Make Rest Monotonic Sorted
[Medium] Find Longest NonDecreasing Subarray Formed By Merging 2 Unsorted Arrays
[Medium] Find LIS
[Medium] Find Number of LIS
[Hard] Find LIS With Consecutive Diff <= k
[Hard] Find Range With Given Array as a Subsequence
[Medium] Next Greater Element
[Medium] Next Greater Element in a Linked List
[Medium] Next Greater Element Streaming
[Medium] Container with Most Water
[Hard] Trapping Rain Water
[Hard] Trapping Rain Water 2d

Find Optimal Range - Max Aggregate Query¶

[Medium] Find Subarray with Max Sum
[Medium] Find Submatrix with Max Sum
[Medium] Find Subarray with Max Sum of Len At Least K
[Hard] Find Max Sum Rectangle With Sum <= k
[Medium] Find Subarray with Max Product
[Easy] Find Subarray of Fixed Size with Max Average
[Hard] Find Subarray of Size >= K with Max Average
[Medium] Find Subarray with Max Abs Sum
[Hard] Find Subarray with Max Sum After Removing One Value Everywhere
[Medium] Find Subarray with Max Sum After Squaring One Element
[Hard] Find Subarray with Max Score = MinVal * Len (Largest Rectangle in Histogram)
[Hard] Find Subarray with Max Score = MinVal * Len Covering One Given Point
[Medium] Find Maximal Submatrix With Columns Reordering Allowed

Find Optimal Length Range - Constrained Aggregate Query¶

[Medium] (Positives) Shortest Subarray with Sum >= k
[Medium] (Positives) Shortest Rotated Subarray (Positives) with Sum >= k
[Medium] Shortest Subarray with Sum = k
[Hard] Shortest Subarray with Sum >= k
[Medium] (NonNeg) Shortet Subarray with Bitwise OR = k
[Medium] Longest Subarray With Sum = k
[Medium] Largest Submatrix with Sum = 0
[Medium] (Positives) Smallest Subarray To Remove to Make k | Sum

Find Range Count - Constrained Aggregate Query¶

[Medium] (Binary) Count Subarrays with Sum = k
[Medium] Count Subarrays with Sum = k
[Medium] Count Submatrices with Sum = k
[Medium] Count Subarrays with Product < k
[Hard] Count Subarrays With Sum in Given Range
[Hard] (Positives) Count Subarrays with Sum*Len <= k
[Medium] (NonNeg) Exists NonTrivial Subarray with k | Sum
[Medium] Count Subarrays with k | Sum

Find Range Count - Constrained Value Query¶

[Medium] Count Subarrays Containing k Odd Numbers
[Medium] Count Subarrays with k | Value and k | Len
[Medium] Count Subarrays with p | Value for at most k of them
[Medium] Count Subarrays with Values at max K Apart
[Medium] Count Subarrays with Max Value in Given Range
[Hard] Count Subarrays with Given Fixed Bound
[Hard] Count Subarrays Bounded by Max on Either End
[Medium] 2D - Adjacent Values within K

Find Optimal Length Range - Constrainted Frequency Query¶

[Medium] Longest Subarray with Equal 1s and 0s
[Medium] Longest Subarray with All Distinct
[Medium] Longest Subarray with At Most K Distinct
[Hard] [Fixed Vocab] Longest Subarray with Each Repeating >= k times
- Note: Cannot be solved directly. Map it to ‘at most m distinct with each repeating >= k times’, vary over all possible m.
[Hard] Longest Equal Subarray After <=k Replacements
- Let’s consider a window from the start which contains some character n times (max_freq).
- For longest valid window, at most k other characters can be added.
- Once such a condition is breached, we can MOVE THE WINDOW BY 1 TO THE RIGHT and keep track of frequencies.
- IT’S NOT NECESSARY UPDATE n TO MATCH THE MAX FREQUENCY OF THE CURRENT WINDOW.
- The ans would only change if another window is found with some character with > n frequency.
- Since the increment happens by 1, the length comparison `r-l+1 - max_freq == k+1: works once a larger frequency is found even though left has moved.
- Decreasing count from the left ensures that we won’t be increasing max_freq incorrectly.
[Hard] Longest Equal Subarray After <=k Removals
- SAME AS ABOVE, EXCEPT THE ANSWER IS THE MAX FREQUENCY ITSELF.
[Medium] Longest Equal Subarray If We Can Replace Value within K

Find Range Count - Constrainted Frequency Query¶

[Medium] Count Subarrays with More 1s Than 0s
[Hard] Count Subarrays with K Distinct Values

Given Range - Sum Query¶

[Easy] Immutable - 1D
[Medium] Immutable - 2D
[Medium] Mutable - 1D
[Medium] Mutable - 2D

Given Range - Frequency Query¶

[Medium] Find Majority Element In Entire Array, Variant
[Medium] Value Frequency in Given Range

Given Range - Min/Max/Avg/Median Query¶

[Hard] Mutable - Range Min Query
[Hard] Query Max for All Subarrays of Fixed Size K
[Hard] Query Median for All Subarrays of Fixed Size K
[Hard] Exists Max-Min-Max Partition So that Max=Min=Max
[Hard] Count Subarrays with Median = K

QuickSort Partitioning¶

[Medium] Sort Binary Array
[Medium] Dutch National Flag
[Medium] Alternate Positive Negative Partition
[Medium] Even Odd Partitioning
[Medium] Odd Even Index Paritioning
[Medium] List Partitioning
[Medium] Partition with External Key
[Medium] Kth Largest Element in Array

Optimal Partitioning¶

[Medium] Partition Array into 2 Equal Sum Subsets
[Medium] Partition to K Equal Sum Subsets
[Hard] Partition Array into K Parts Minimising Largest Subarray Sum

Optimal Cost - DP¶

[Medium] Paint House
[Medium] Minimum Path Sum
[Medium] Rod Cutting

Optimal Choice (0-1 Knapsack) - DP¶

[Medium] Bounded
[Medium] Unbounded
[Medium] Maximal Square

Counting - DP¶

[Medium] Unique Paths
[Medium] Unique Paths with Obstacles
[Hard] Unique Paths with Obstacles and Arbitrary Start/End
[Medium] Number of Ways to Reach a Position After Exactly k Steps

Permutation¶

[Medium] Find Next Permutation
[Medium] Find Max from 1 Swap
[Hard] Min Swaps To Make All Pairs Consecutives
[Medium] Check if 1 Swap Can Make Array Equal
[Medium] Check if Adjacent Swaps Can Make Array Equal
[Hard] Check if Any Number of Swaps Can Make Array Equal
[Hard] Last Substring in Lexicographical Order

Selection¶

[Medium] Subsequence of Len K Starting with Smallest
[Easy] Drop 1 Digit to Form Max Number
[Medium] Drop K Digits to Form Min Number
[Hard] Select Digits Sequentially From 2 Arrays to Form Max Number of Len <= k

Greedy Search¶

[Medium] Find Sup of a Given Number with Monotonic Digits

Intervals/Activity Selection¶

[Easy] Exists Overlapping Intervals
[Medium] Exists Overlapping Intervals
[Medium] Merge Overlapping Intervals
[Medium] Remove to Make Non Overlapping
[Medium] Count Overlapping Segments
[Medium] Number of Running Job at Any Given Time
[Medium] Shortest Running Job at Any Given Time
[Medium] Fixed Schedule with Capacity Requirement
[Hard] Max Utilized Resource for Droppable Jobs
[Medium] Max Events That Can Be Attended Partially
[Hard] Max Events That Can Be Attended Fully

Job Scheduling¶

[Medium] Rearrage to Make Same Characters 1 Distance Apart
[Hard] Rearrage to Make Same Characters K Distance Apart
[Medium] Unordered Single CPU Scheduler with Repeat Constraint
[Medium] Ordered Single CPU Scheduler with Repeat Constraint
[Medium] Optimal Job Allocation with Fixed Burst Time
[Hard] Optimal Job Allocation Among K Workers
[Hard] Optimal Job Allocation With Neighbourhood Contraint (Candy)
[Medium] Optimal Job Allocation Among K Workers of Varying Capability
[Medium] Max Utilized Resource for Flexi Schedule Jobs

Combinatorics¶

[Medium] Generate All Permutations of Given Array of Uniques
[Medium] Generate All Permutations of Given Array Containing Duplicates
[Hard] Generate Kth Permutation
[Medium] Generate Palindrome Permutations of Given Array
[Medium] Generate Combinations
[Medium] Combinations Sum = K (With Replacement)
[Medium] Combinations Sum = K (Without Replacement)
[Medium] Combinations of K Digits With Sum = N (Without Replacement)

Paranthesis¶

[Medium] Generate All Valid Paranthesis of Given Size
[Medium] Check Valid Paranthesis With Wildcard
[Medium] Min Remove to Make Valid Paranthesis
[Medium] Can Make Valid Paranthesis Flipping At Certain Allowed Position

Palindromes¶

[Easy] Can Be Made Palindrome With 1 Removal
[Medium] Can Be Made Palindrome With 1 Replacement
[Medium] Can be Made Palindrome With K Removal
[Medium] Longest Palindromic Subsequence
[Medium] Longest Palindromic Subsequence With Constraints
[Medium] Longest Palindromic Subarray
[Medium] Count Palindromic Subarrays
[Hard] Count Distinct Palindromic Subsequences
[Medium] Count Distinct Length 3 Palindromic Subsequences
[Hard] Count Palindromic Subsequences of Given Length
[Hard] Longest Palindrome Merging Subsequences from 2 Arrays

Misc¶

[Medium] Construct Array Free of Arithmatic Subsequences
[Hard] Reconstruct Array from Given Condition
[Hard] Reconstruct Array from All Subcollection Sums

Strings¶

Prefix¶

[Medium] Longest Common Prefix

Rolling Hash¶

Trees¶

Traversal¶

Construction¶

LCA¶

Path Constraints¶

Graphs¶

Traversal¶

Connectivity¶

Topological Sort¶

LCA¶

Minimum Spanning Tree¶

Shortest Path¶

Bipartite Matching¶

Eulerian Tour¶

Streaming¶

Counts¶

States¶

[Easy] Design Parking System
[Easy] Design Ordered Stream
[Medium] Insert Delete GetRandom in O(1)
[Medium] Design Browser History
[Medium] LRU Cache
[Hard] LFU Cache
[Hard] Data Stream as Disjointed Intervals
[Medium] Design File System
[Hard] In Memory File System
[Medium] File Sharing System
[Medium] Log Storage System

Search¶

[Easy] Two Sum Streaming
[Hard] Online Majority Element In Subarray
[Medium] Add and Search Words
[Medium] Search Autocomplete System Lexicographical
[Hard] Search Autocomplete System Hitcount + Lexicographical
[Hard] Stream of Characters

Misc¶

[Medium] Range Frequency Queries
[Medium] Find Consecutive Integers from a Data Stream
[Hard] Range Module
[Hard] Design Statistics Tracker