Given a list of products and a search word, return 3 lexicographically smallest products that start with each prefix of search word.

### Sample Inputs & Outputs
Ex1: products=['mobile','mouse','moneypot','monitor','mousepad'], word='mouse' → [['mobile','moneypot','monitor'],['mobile','moneypot','monitor'],['mouse','mousepad'],['mouse','mousepad'],['mouse','mousepad']]
Ex2: word='a' with no matching products → [[]]

### Edge Cases
1. No products start with prefix → []
2. Fewer than 3 products match → return all
3. Products with duplicate prefixes
4. Single character search word
5. Search word not in products

Search Suggestions System

You are given an array prices[i] = price on day i. Find the maximum profit from buying once and selling on a later day. Return 0 if no profit possible.

### Sample Inputs & Outputs
Ex1: [7,1,5,3,6,4] → 5  (buy@1, sell@6)
Ex2: [7,6,4,3,1] → 0  (prices only fall)
Ex3: [2,4,1,7] → 6  (buy@1, sell@7)

### Edge Cases
1. Strictly decreasing → 0
2. Two elements [1,2] → 1
3. All same prices → 0
4. Min price is at last index (no valid sell after)
5. Large plateau then spike

Best Time to Buy & Sell Stock

Given an integer array, find all elements appearing more than once. Return duplicates in any order.

### Sample Inputs & Outputs
Ex1: [4,3,2,7,8,2,3,1] → [2,3]
Ex2: [1,1,2] → [1]
Ex3: [1,2,3] → []

### Edge Cases
1. No duplicates → []
2. All same [2,2,2] → [2]
3. Single element → []
4. Multiple distinct duplicates
5. Duplicates appear 3+ times (still return once)

Find Duplicates in Array

Given array of n distinct numbers from [0,n], find the one missing number. E.g. n=3, numbers should be [0,1,2,3] and one is absent.

### Sample Inputs & Outputs
Ex1: [3,0,1] → 2
Ex2: [0,1] → 2
Ex3: [9,6,4,2,3,5,7,0,1] → 8
Ex4: [0] → 1

### Edge Cases
1. Missing 0 (first element)
2. Missing n (last element)
3. Single element [1] → 0 or [0] → 1
4. Sorted input with gap
5. Large n: use long to avoid overflow in expected sum

Find the Missing Number

Find the contiguous subarray with the largest sum (at least one element) and return its sum. This is the classic Kadane's algorithm problem.

### Sample Inputs & Outputs
Ex1: [-2,1,-3,4,-1,2,1,-5,4] → 6  (subarray [4,-1,2,1])
Ex2: [1] → 1
Ex3: [5,4,-1,7,8] → 23  (entire array)

### Edge Cases
1. All negative [-3,-1,-2] → -1 (must pick at least one)
2. Single element
3. All same positive [2,2,2] → 6
4. Alternating pos/neg
5. One large negative in middle breaks subarray

Maximum Subarray (Kadane's)

Move all zeros to the end of the array while maintaining relative order of non-zero elements. Modify in-place with O(1) extra memory.

### Sample Inputs & Outputs
Ex1: [0,1,0,3,12] → [1,3,12,0,0]
Ex2: [0] → [0]
Ex3: [0,0,1] → [1,0,0]
Ex4: [1,2,3] → [1,2,3]  (no change)

### Edge Cases
1. All zeros [0,0,0] → [0,0,0]
2. No zeros [1,2,3] → [1,2,3]
3. Single element [0]
4. Zero already at end [1,2,0]
5. Multiple consecutive zeros in middle

Move Zeroes to End

Rotate integer array to the right by k steps. k may be larger than array length.

### Sample Inputs & Outputs
Ex1: [1,2,3,4,5,6,7], k=3 → [5,6,7,1,2,3,4]
Ex2: [-1,-100,3,99], k=2 → [3,99,-1,-100]
Ex3: [1,2], k=3 → [2,1]  (k%2=1)

### Edge Cases
1. k >= n: use k = k%n
2. k=0: no change
3. Single element
4. k equals n: no change
5. Negative numbers in array

Rotate Array by K Steps

Given an array of integers and a target value, return the indices of the two numbers that add up to the target. Exactly one solution exists; you cannot use the same element twice.

### Sample Inputs & Outputs
Ex1: nums=[2,7,11,15], target=9 → [0,1]  (2+7=9)
Ex2: nums=[3,2,4], target=6 → [1,2]  (2+4=6)
Ex3: nums=[3,3], target=6 → [0,1]  (same value, different indices)

### Edge Cases
1. Two equal values summing to target [3,3] t=6
2. Negative numbers [-1,-2,-3,-4] t=-7
3. Large array 10K+ elements (O(n²) TLEs)
4. Target zero [0,0] → [0,1]
5. Min input: two elements only

Two Sum

Find the median of two sorted arrays. O(log(m+n)) required.

### Sample Inputs & Outputs
Ex1: [1,3],[2] → 2.0
Ex2: [1,2],[3,4] → 2.5
Ex3: [],[1] → 1.0

### Edge Cases
1. One empty array
2. Both single elements
3. Non-overlapping ranges
4. Arrays of different lengths
5. Even vs odd total length

Find Median of Two Sorted Arrays

Given elevation map as array, compute total rainwater trapped between bars after raining.

### Sample Inputs & Outputs
Ex1: [0,1,0,2,1,0,1,3,2,1,2,1] → 6
Ex2: [4,2,0,3,2,5] → 9
Ex3: [3,0,3] → 3

### Edge Cases
1. Empty array → 0
2. All same height → 0
3. Strictly increasing → 0
4. Strictly decreasing → 0
5. Single or two bars → 0

Trapping Rainwater

Find all unique triplets [a,b,c] in the array such that a+b+c=0. Solution set must not contain duplicate triplets.

### Sample Inputs & Outputs
Ex1: [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]
Ex2: [0,1,1] → []
Ex3: [0,0,0] → [[0,0,0]]

### Edge Cases
1. Length < 3 → []
2. All zeros → [[0,0,0]]
3. All positives → []
4. Duplicates causing duplicate triplets
5. Large array with many dupes

3Sum (Find All Triplets)

Given heights array, find two lines forming a container holding the most water. Return max area.

### Sample Inputs & Outputs
Ex1: [1,8,6,2,5,4,8,3,7] → 49  (indices 1&8, width=7, min-height=7)
Ex2: [1,1] → 1
Ex3: [4,3,2,1,4] → 16

### Edge Cases
1. Two elements only
2. All same heights
3. Strictly increasing — max at ends
4. Strictly decreasing
5. One very tall surrounded by tiny ones

Container With Most Water

Find the kth largest element in an unsorted array. It's the kth largest in sorted order (not kth distinct).

### Sample Inputs & Outputs
Ex1: [3,2,1,5,6,4], k=2 → 5
Ex2: [3,2,3,1,2,4,5,5,6], k=4 → 4
Ex3: [1], k=1 → 1

### Edge Cases
1. k=1 → maximum element
2. k=n → minimum element
3. Duplicates in array
4. All same elements
5. Large n, small k (min-heap optimal)

Kth Largest Element

Find length of longest sequence of consecutive integers in an unsorted array. Must be O(n).

### Sample Inputs & Outputs
Ex1: [100,4,200,1,3,2] → 4  (sequence 1,2,3,4)
Ex2: [0,3,7,2,5,8,4,6,0,1] → 9  (0-8)
Ex3: [1] → 1

### Edge Cases
1. Empty array → 0
2. All same elements → 1
3. No consecutive pairs → 1
4. Entire array is consecutive
5. Duplicates (e.g. [1,1,2,3]) — use set

Longest Consecutive Sequence

Find the contiguous subarray with the largest product. Array can contain negative numbers and zeros.

### Sample Inputs & Outputs
Ex1: [2,3,-2,4] → 6  ([2,3])
Ex2: [-2,0,-1] → 0
Ex3: [-2,3,-4] → 24  (entire array: -2×3×-4=24)

### Edge Cases
1. Single element
2. All negatives (even count → positive product)
3. Array with zeros (resets product)
4. Two negatives surrounding positives
5. Single zero in array

Maximum Product Subarray

Merge all overlapping intervals. Return array of non-overlapping intervals covering all input intervals.

### Sample Inputs & Outputs
Ex1: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
Ex2: [[1,4],[4,5]] → [[1,5]]  (touching merges)
Ex3: [[1,4],[0,4]] → [[0,4]]

### Edge Cases
1. Single interval → return as-is
2. All overlap → one merged
3. None overlap → return sorted original
4. Touching intervals [1,4],[4,5] → [1,5]
5. One completely inside another [1,10],[2,5] → [1,10]

Merge Intervals

Rearrange array to the lexicographically next greater permutation. If largest permutation, rearrange to smallest (sorted ascending). In-place O(1) space.

### Sample Inputs & Outputs
Ex1: [1,2,3] → [1,3,2]
Ex2: [3,2,1] → [1,2,3]  (wrap around)
Ex3: [1,1,5] → [1,5,1]

### Edge Cases
1. Descending array → reverse to ascending
2. Single element → unchanged
3. Two elements → swap if first < second
4. Duplicate elements
5. Array already in largest permutation

Next Permutation

Return array where answer[i] = product of all elements except nums[i]. O(n) time, no division operator.

### Sample Inputs & Outputs
Ex1: [1,2,3,4] → [24,12,8,6]
Ex2: [-1,1,0,-3,3] → [0,-3,0,9,0]
Ex3: [2,3] → [3,2]

### Edge Cases
1. One zero: all zeros except at zero's position
2. Two zeros: all zeros
3. Negative numbers
4. Large values causing overflow → use long
5. Min two elements

Product of Array Except Self

Set entire row and column to 0 if any element is 0. Do it in-place with O(1) extra space.

### Sample Inputs & Outputs
Ex1: [[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]]
Ex2: [[0,1,2,0],[3,4,5,2],[1,3,1,5]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

### Edge Cases
1. Multiple zeros
2. Zero in first row/column (edge case)
3. All zeros
4. Single element zero
5. No zeros → unchanged

Set Matrix Zeroes

Return all elements of an m×n matrix in spiral order (clockwise from top-left).

### Sample Inputs & Outputs
Ex1: [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]
Ex2: [[1,2,3,4],[5,6,7,8],[9,10,11,12]] → [1,2,3,4,8,12,11,10,9,5,6,7]

### Edge Cases
1. Single row matrix
2. Single column matrix
3. Single element
4. Square matrix
5. Non-square (more rows than cols)

Spiral Matrix Traversal

Find the total number of continuous subarrays whose sum equals k.

### Sample Inputs & Outputs
Ex1: nums=[1,1,1], k=2 → 2
Ex2: nums=[1,2,3], k=3 → 2  ([1,2] and [3])
Ex3: nums=[1], k=0 → 0

### Edge Cases
1. k=0 — subarrays of all zeros
2. Negative numbers in array
3. Single element equal to k
4. Entire array sums to k
5. No subarray sums to k → 0

Subarray Sum Equals K

Find target in sorted array. Return index if found, -1 if not. Must be O(log n).

### Sample Inputs & Outputs
Ex1: [-1,0,3,5,9,12], target=9 → 4
Ex2: [-1,0,3,5,9,12], target=2 → -1
Ex3: [1], target=1 → 0
Ex4: [1,3], target=3 → 1

### Edge Cases
1. Target not in array → -1
2. Single element: matches or not
3. Target is first element
4. Target is last element
5. Integer overflow: use mid=left+(right-left)/2

Binary Search

Find kth smallest element in n×n matrix where each row and column is sorted.

### Sample Inputs & Outputs
Ex1: [[1,5,9],[10,11,13],[12,13,15]], k=8 → 13
Ex2: [[-5]], k=1 → -5
Ex3: [[1,2],[1,3]], k=2 → 1

### Edge Cases
1. k=1 → min element
2. k=n² → max element
3. Duplicate values
4. Single element matrix
5. k in middle of duplicates

Kth Smallest in Sorted Matrix

Place C cows in N stalls so minimum distance between any two cows is maximized. Return this maximum minimum distance.

### Sample Inputs & Outputs
Ex1: stalls=[1,2,8,4,9], C=3 → 3  (place at 1,4,9: min dist=3)
Ex2: stalls=[1,2,3], C=2 → 2  (place at 1,3)
Ex3: stalls=[1,2,3,4,5], C=5 → 1

### Edge Cases
1. C=2 → distance between first and last stall
2. C=number of stalls → min adjacent gap
3. Unsorted stalls → sort first
4. Large stall values
5. Many stalls few cows

Aggressive Cows (Binary Search on Answer)

Allocate M books among K students such that maximum number of pages assigned to any student is minimized. Books must be allocated in contiguous order.

### Sample Inputs & Outputs
Ex1: books=[12,34,67,90], K=2 → 113  (split as [12,34,67] and [90]: max=113 or [12,34] and [67,90]: max=157, so min max=113)
Ex2: books=[10,20,30,40], K=2 → 60
Ex3: books=[15,17,20], K=2 → 32

### Edge Cases
1. K > number of books → impossible (-1)
2. K = 1 → sum of all books
3. K = n → max single book
4. All same page counts
5. Single book single student

Book Allocation Problem

Find the minimum element in a sorted array that has been rotated at some unknown pivot.

### Sample Inputs & Outputs
Ex1: [3,4,5,1,2] → 1
Ex2: [4,5,6,7,0,1,2] → 0
Ex3: [11,13,15,17] → 11  (not rotated)

### Edge Cases
1. Not rotated (sorted) → first element
2. Rotated by 1
3. Single element → it is minimum
4. Two elements
5. Array values wrap around (e.g. 100,200,1,50)

Find Minimum in Rotated Array

Find a peak element — element greater than its neighbors. Array has no two adjacent equal elements. Return any peak index. O(log n) required.

### Sample Inputs & Outputs
Ex1: [1,2,3,1] → 2  (index of 3)
Ex2: [1,2,1,3,5,6,4] → 5 or 1  (either valid)
Ex3: [1] → 0

### Edge Cases
1. Single element → index 0 (always peak)
2. Peak at beginning or end
3. Multiple peaks — return any
4. Monotonically increasing → last element
5. Monotonically decreasing → first element

Find Peak Element

Search for a target in an m×n matrix where each row is sorted and first integer of each row is greater than last of previous row.

### Sample Inputs & Outputs
Ex1: matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3 → True
Ex2: same matrix, target=13 → False
Ex3: [[1]], target=1 → True

### Edge Cases
1. Target smaller than first element → False
2. Target larger than last element → False
3. Single element matrix
4. Single row or column
5. Target at corner positions

Search in 2D Matrix

Search for target in a sorted array that has been rotated at an unknown pivot. Return index or -1. Must be O(log n).

### Sample Inputs & Outputs
Ex1: [4,5,6,7,0,1,2], target=0 → 4
Ex2: [4,5,6,7,0,1,2], target=3 → -1
Ex3: [1], target=0 → -1

### Edge Cases
1. Target not in array → -1
2. No rotation (pivot=0)
3. Single element
4. Target equals pivot element
5. Rotated by 1 or n-1

Search in Rotated Sorted Array

Count distinct ways to climb n stairs where you can take 1 or 2 steps at a time.

### Sample Inputs & Outputs
Ex1: n=2 → 2  (1+1 or 2)
Ex2: n=3 → 3  (1+1+1, 1+2, 2+1)
Ex3: n=5 → 8
Ex4: n=1 → 1

### Edge Cases
1. n=1 → 1
2. n=2 → 2
3. Large n=45 — must be O(n)
4. n=0 → 1 (trivially)
5. Long overflow for very large n

Climbing Stairs

Compute nth Fibonacci number using dynamic programming. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Implement memoization and tabulation.

### Sample Inputs & Outputs
Ex1: n=0 → 0
Ex2: n=1 → 1
Ex3: n=10 → 55
Ex4: n=20 → 6765

### Edge Cases
1. n=0 → 0 (base case)
2. n=1 → 1 (base case)
3. n=2 → 1
4. Large n (50+) — naive recursion O(2^n) times out
5. Negative n — undefined, assume n>=0

Fibonacci (Memoization + Tabulation)

Implement Burst balloons to maximize coins collected. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Burst Balloons

Find the minimum number of operations (insert, delete, replace) to convert string s into string t.

### Sample Inputs & Outputs
Ex1: s='horse', t='ros' → 3  (horse→rorse→rose→ros)
Ex2: s='intention', t='execution' → 5
Ex3: s='', t='abc' → 3  (3 inserts)

### Edge Cases
1. One string empty → length of other
2. Both empty → 0
3. Same strings → 0
4. Single char difference
5. Very different long strings

Edit Distance (Levenshtein)

Find minimum number of scalar multiplications to multiply a chain of matrices. matrices[i] has dimensions p[i-1]×p[i].

### Sample Inputs & Outputs
Ex1: p=[1,2,3,4] → 18  (optimal: (A1×A2)×A3 or A1×(A2×A3) — try both)
Ex2: p=[40,20,30,10,30] → 26000
Ex3: p=[10,30,5,60] → 4500

### Edge Cases
1. Single matrix → 0 multiplications
2. Two matrices → one multiplication: p[0]*p[1]*p[2]
3. All same dimensions
4. Optimal ordering saves significantly over naive
5. Very large dimensions

Matrix Chain Multiplication

Partition string s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings.

### Sample Inputs & Outputs
Ex1: s='aab' → [['a','a','b'],['aa','b']]
Ex2: s='a' → [['a']]
Ex3: s='aba' → [['a','b','a'],['aba']]

### Edge Cases
1. Single char → one partition [['c']]
2. All same chars 'aaa' → multiple valid
3. No palindrome > length 1 → all single chars
4. Entire string is palindrome → include it
5. Odd vs even length palindromes

Palindrome Partitioning

Implement regex matching with '.' (matches any single char) and '*' (matches zero or more of the preceding element).

### Sample Inputs & Outputs
Ex1: s='aa', p='a*' → True  (a* matches 'aa')
Ex2: s='ab', p='.*' → True  (.* matches anything)
Ex3: s='aab', p='c*a*b' → True  (c*=empty, a*='aa', b='b')

### Edge Cases
1. Empty pattern → only matches empty string
2. 'a*' can match empty (zero occurrences)
3. '.*' matches anything
4. Multiple consecutive x* patterns
5. Pattern longer than string

Regular Expression Matching

Implement wildcard pattern matching where '?' matches any single char and '*' matches any sequence (including empty).

### Sample Inputs & Outputs
Ex1: s='aa', p='a' → False
Ex2: s='aa', p='*' → True
Ex3: s='cb', p='?a' → False
Ex4: s='adceb', p='*a*b' → True

### Edge Cases
1. Both empty → True
2. Pattern is all '*' → True
3. '?' matches exactly one char
4. '*' can match empty string
5. Multiple consecutive '*' (equivalent to one)

Wildcard Pattern Matching

Given n items with weights and values, and capacity W, find max value fitting in knapsack. Each item used at most once.

### Sample Inputs & Outputs
Ex1: w=[1,3,4,5], v=[1,4,5,7], W=7 → 9  (items 2+3: 3+4=7, value=9)
Ex2: w=[1,2,3], v=[6,10,12], W=5 → 22  (items 2+3)
Ex3: w=[5], v=[10], W=3 → 0

### Edge Cases
1. W=0 → 0
2. All items heavier than W → 0
3. Single item that fits exactly
4. All items fit within W
5. Large W and many items O(nW)

0/1 Knapsack

Find minimum number of coins needed to make up amount. You have infinite supply of each coin denomination. Return -1 if not possible.

### Sample Inputs & Outputs
Ex1: coins=[1,5,11], amount=15 → 3  (5+5+5)
Ex2: coins=[2], amount=3 → -1
Ex3: coins=[1], amount=0 → 0

### Edge Cases
1. Amount = 0 → 0 coins
2. No valid combination → -1
3. Single coin type that divides evenly
4. Greedy fails (coins=[1,3,4], amount=6 → greedy gives 4+1+1=3, DP gives 3+3=2)
5. Large amount with small coins

Coin Change (Minimum Coins)

Rob houses along a street. No two adjacent houses can be robbed. Find maximum money you can rob.

### Sample Inputs & Outputs
Ex1: [1,2,3,1] → 4  (house 1+3)
Ex2: [2,7,9,3,1] → 12  (house 1+3+5: 2+9+1)
Ex3: [1] → 1

### Edge Cases
1. Single house → rob it
2. Two houses → take max of two
3. All same amounts
4. Alternating high-low values
5. All zeros → 0

House Robber

Given array where nums[i] is max jump from index i, determine if you can reach the last index starting from index 0.

### Sample Inputs & Outputs
Ex1: [2,3,1,1,4] → True  (0→1→4)
Ex2: [3,2,1,0,4] → False  (stuck at index 3)
Ex3: [0] → True  (already at end)

### Edge Cases
1. Single element → True
2. First element is 0 and n>1 → False
3. All zeros except last → depends on position
4. Large first jump covers all
5. nums[i] can be 0 (no jump from there)

Jump Game

Find the length of the longest common subsequence (LCS) of two strings. A subsequence maintains relative order but need not be contiguous.

### Sample Inputs & Outputs
Ex1: s1='abcde', s2='ace' → 3  (LCS='ace')
Ex2: s1='abc', s2='abc' → 3  (entire string)
Ex3: s1='abc', s2='def' → 0  (no common chars)

### Edge Cases
1. One empty string → 0
2. Both identical → length of string
3. No common chars → 0
4. One string is subsequence of other
5. Long strings with similar chars

Longest Common Subsequence

Find the length of the longest strictly increasing subsequence in an array.

### Sample Inputs & Outputs
Ex1: [10,9,2,5,3,7,101,18] → 4  (2,3,7,101 or 2,5,7,101)
Ex2: [0,1,0,3,2,3] → 4  (0,1,2,3)
Ex3: [7,7,7,7] → 1

### Edge Cases
1. All same → 1
2. Strictly decreasing → 1
3. Strictly increasing → n
4. Single element → 1
5. Alternating up-down

Longest Increasing Subsequence

Given a rod of length n and prices for each length 1..n, find maximum revenue by cutting rod into pieces.

### Sample Inputs & Outputs
Ex1: length=8, prices=[1,5,8,9,10,17,17,20] → 22  (cut into length 2+6=5+17=22)
Ex2: length=4, prices=[2,5,7,8] → 10  (two pieces of length 2: 5+5=10)
Ex3: length=1, prices=[1] → 1

### Edge Cases
1. No cuts needed (optimal is full rod)
2. All equal prices → no benefit to cutting
3. Price for full length is optimal
4. Single unit cuts best
5. Very uneven price distribution

Minimum Cost to Cut a Rod

Find path from top-left to bottom-right of grid with minimum sum. Can only move right or down.

### Sample Inputs & Outputs
Ex1: [[1,3,1],[1,5,1],[4,2,1]] → 7  (1→3→1→1→1)
Ex2: [[1,2,3],[4,5,6]] → 12
Ex3: [[1]] → 1

### Edge Cases
1. 1×1 grid → single element
2. 1×n or m×1 → sum of only path
3. All zeros → 0
4. Large values → use long
5. Grid with very large numbers

Minimum Path Sum in Grid

Determine if you can partition array into two subsets with equal sum.

### Sample Inputs & Outputs
Ex1: [1,5,11,5] → True  ([1,5,5] and [11])
Ex2: [1,2,3,5] → False
Ex3: [1,1] → True

### Edge Cases
1. Odd total sum → False immediately
2. Single element → False (unless 0)
3. All zeros → True
4. Two elements that are equal → True
5. Target = sum/2

Partition Equal Subset Sum

Determine if there exists a subset of the array that sums to a given target value.

### Sample Inputs & Outputs
Ex1: [3,34,4,12,5,2], target=9 → True  (4+5 or 2+3+4)
Ex2: [3,34,4,12,5,2], target=30 → False
Ex3: [1,1,1,1], target=2 → True

### Edge Cases
1. Target 0 → True (empty subset)
2. All elements exceed target → False
3. Single element equals target → True
4. Target larger than sum of all → False
5. Negative numbers not allowed (define constraints)

Subset Sum Problem

Count distinct paths from top-left to bottom-right of m×n grid. Can only move right or down.

### Sample Inputs & Outputs
Ex1: m=3, n=7 → 28
Ex2: m=3, n=2 → 3
Ex3: m=1, n=1 → 1

### Edge Cases
1. 1×n or m×1 grid → 1 path only
2. 1×1 grid → 1
3. Large m,n — answer can be huge
4. m=n (square grid)
5. Very small grid 2×2 → 2

Unique Paths in Grid

Given a string s and a dictionary of words, determine if s can be segmented into space-separated sequence of dictionary words.

### Sample Inputs & Outputs
Ex1: s='leetcode', wordDict=['leet','code'] → True
Ex2: s='applepenapple', wordDict=['apple','pen'] → True
Ex3: s='catsandog', wordDict=['cats','dog','sand','and','cat'] → False

### Edge Cases
1. Empty string → True
2. Dictionary contains entire string → True
3. String with repeated segments
4. No valid segmentation → False
5. Single-char dictionary words

Word Break Problem

Implement BFS traversal of a graph given as adjacency list starting from a source vertex.

### Sample Inputs & Outputs
Ex1: graph={0:[1,2],1:[0,3],2:[0,4]}, start=0 → [0,1,2,3,4]
Ex2: linear 0→1→2→3 → [0,1,2,3]
Ex3: no edges → [start]

### Edge Cases
1. Disconnected graph — only visits reachable
2. Cycle in graph — visited prevents infinite loop
3. Single vertex no edges
4. Large dense graph
5. Start vertex isolated

BFS Traversal

Implement DFS traversal of a graph given as adjacency list starting from a source vertex.

### Sample Inputs & Outputs
Ex1: graph={0:[1,2],1:[0,3],2:[0]}, start=0 → [0,1,3,2]
Ex2: linear 0→1→2→3 → [0,1,2,3]
Ex3: no edges → [start]

### Edge Cases
1. Disconnected graph — only visits reachable
2. Graph with back edges (cycles)
3. Single vertex
4. Very deep graph — recursive may stack overflow
5. Multiple valid DFS orderings exist

DFS Traversal

Given an image (2D grid), a starting pixel, and a new color, perform flood fill. Change the starting pixel and all 4-directionally connected pixels of the same original color to the new color.

### Sample Inputs & Outputs
Ex1: image=[[1,1,1],[1,1,0],[1,0,1]], sr=1,sc=1, color=2 → [[2,2,2],[2,2,0],[2,0,1]]
Ex2: image=[[0,0,0],[0,0,0]], sr=0,sc=0, color=0 → [[0,0,0],[0,0,0]] (same color)

### Edge Cases
1. New color == original color → return as-is (avoid infinite loop)
2. Single pixel grid
3. Pixel at corner/edge
4. Entire grid same color
5. Color 0 (valid color value)

Flood Fill Algorithm

Implement Find all bridges in undirected graph using Tarjan. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Find Bridges in Graph

Implement Word Ladder shortest transformation sequence. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Word Ladder

Implement Clone an undirected graph using BFS. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Clone Graph

There are numCourses courses 0..n-1. prerequisites[i]=[a,b] means must take b before a. Return true if you can finish all courses.

### Sample Inputs & Outputs
Ex1: n=2, prerequisites=[[1,0]] → True
Ex2: n=2, prerequisites=[[1,0],[0,1]] → False (cycle)
Ex3: n=1, prerequisites=[] → True

### Edge Cases
1. No prerequisites → True
2. Self-prerequisite [[0,0]] → False
3. Large cycle in the middle
4. Multiple disconnected components
5. All courses form a chain

Course Schedule (Cycle Detection)

Detect if a directed graph has a cycle using DFS and coloring (white=0, gray=1, black=2).

### Sample Inputs & Outputs
Ex1: 0→1→2→0 (cycle) → True
Ex2: 0→1→2, 0→2 (no cycle) → False
Ex3: single vertex self-loop 0→0 → True

### Edge Cases
1. Self-loop → True
2. DAG (no cycle) → False
3. Multiple components — check all
4. Disconnected vertex → False
5. Graph with 2 cycles

Detect Cycle in Directed Graph

Detect if an undirected graph has a cycle using DFS or Union-Find.

### Sample Inputs & Outputs
Ex1: 0-1-2-0 (triangle) → True
Ex2: 0-1-2-3 (path) → False
Ex3: single edge 0-1 → False

### Edge Cases
1. Self-loop → True
2. Linear chain → False
3. Disconnected components — must check all
4. Single vertex → False
5. Two vertices with multiple edges → True

Detect Cycle in Undirected Graph

Count the number of islands in an m×n grid of '1's (land) and '0's (water). Islands are formed by connecting adjacent land horizontally/vertically.

### Sample Inputs & Outputs
Ex1: [[1,1,1],[0,1,0],[1,1,1]] → 1
Ex2: [[1,1,0],[0,0,0],[0,0,1]] → 2
Ex3: [[1,0],[0,1]] → 2

### Edge Cases
1. All water → 0
2. All land → 1
3. Single cell grid
4. Diagonal connections don't count
5. 1×n or n×1 grid

Number of Islands

Find shortest path from source to all vertices in a weighted graph using Dijkstra's algorithm. Edges are non-negative.

### Sample Inputs & Outputs
Ex1: graph: 0→1(4), 0→2(1), 2→1(2), 1→3(1) from 0 → [0,3,1,4]
Ex2: Single vertex → [0]
Ex3: Disconnected vertex → infinity/unreachable

### Edge Cases
1. Single vertex
2. Disconnected graph — unreachable node stays infinity
3. Multiple shortest paths (same length)
4. Dense graph (use matrix) vs sparse (use adj list)
5. Large weight values — use long

Shortest Path Dijkstra

Return topological ordering of vertices in a DAG (Directed Acyclic Graph). Vertex u comes before v if there is edge u→v.

### Sample Inputs & Outputs
Ex1: 6 nodes, edges: 5→2,5→0,4→0,4→1,2→3,3→1 → [5,4,2,3,1,0] (one valid order)
Ex2: Linear chain 0→1→2→3 → [0,1,2,3]
Ex3: Graph with cycle → impossible (return [] or detect)

### Edge Cases
1. Graph with cycle → no valid topological order
2. Multiple valid orderings exist
3. Isolated vertices
4. Single vertex
5. Already ordered input

Topological Sort

Given a ransom note string and a magazine string, return if you can construct the ransom note from the magazine letters. Each letter can only be used once.

### Sample Inputs & Outputs
Ex1: note='a', mag='b' → False
Ex2: note='aa', mag='ab' → False
Ex3: note='aa', mag='aab' → True

### Edge Cases
1. Empty note → True
2. Note longer than magazine → False
3. All same letters in both
4. Case sensitivity
5. Note has letters not in magazine

Ransom Note Check

Find two indices where values sum to target using a HashMap for O(n) time. Explain why this beats O(n²) brute force.

### Sample Inputs & Outputs
Ex1: [2,7,11,15], t=9 → [0,1]
Ex2: [3,2,4], t=6 → [1,2]
Ex3: [0,4,3,0], t=0 → [0,3]

### Edge Cases
1. Same values [3,3] target=6 → [0,1]
2. Negative numbers [-1,-2,-3] t=-7
3. Zero in array [0,1] t=1
4. Two elements only
5. Target = first + last element

Two Sum using HashMap

Find all unique quadruplets [a,b,c,d] such that a+b+c+d=target.

### Sample Inputs & Outputs
Ex1: nums=[1,0,-1,0,-2,2], target=0 → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Ex2: nums=[2,2,2,2,2], target=8 → [[2,2,2,2]]
Ex3: nums=[1,2,3,4], target=100 → []

### Edge Cases
1. Fewer than 4 elements → []
2. All same values
3. Target very large → may need long
4. Negative target
5. Duplicate quadruplets must be avoided

Four Sum Problem

Count distinct elements in every window of size k in an array.

### Sample Inputs & Outputs
Ex1: arr=[1,2,1,3,4,2,3], k=4 → [3,4,4,3]
Ex2: arr=[1,2,3,4,5], k=3 → [3,3,3]
Ex3: arr=[1,1,1,1], k=2 → [1,1,1]

### Edge Cases
1. k=1 → every element is 1 distinct
2. k=n → count distinct in full array
3. All same → always 1
4. All distinct → always k
5. k > n → undefined or single window

Count Distinct Elements in Window

Find the length of the longest subarray with sum equal to 0.

### Sample Inputs & Outputs
Ex1: [15,-2,2,-8,1,7,10,23] → 5  (subarray [-2,2,-8,1,7])
Ex2: [1,2,3] → 0
Ex3: [0] → 1

### Edge Cases
1. All positive — no zero-sum subarray
2. Array with zero element → at least 1
3. Entire array sums to 0
4. Multiple subarrays of different lengths
5. Negative numbers only

Largest Subarray with Sum 0

Using a HashSet, find the longest sequence of consecutive integers in O(n).

### Sample Inputs & Outputs
Ex1: [100,4,200,1,3,2] → 4  (1,2,3,4)
Ex2: [0,3,7,2,5,8,4,6,0,1] → 9  (0-8)
Ex3: [1] → 1

### Edge Cases
1. Single element → 1
2. All same → 1
3. No consecutive → 1
4. Entire array consecutive
5. Duplicates (use set, count once)

Longest Consecutive Subsequence

Find the k most frequent elements in an array. Return them in any order.

### Sample Inputs & Outputs
Ex1: nums=[1,1,1,2,2,3], k=2 → [1,2]
Ex2: nums=[1], k=1 → [1]
Ex3: nums=[4,1,2,4,2,1,1], k=2 → [1,4]

### Edge Cases
1. k=1 → return most frequent
2. k=n → return all unique elements
3. Multiple elements with same frequency
4. Single element repeated
5. All distinct elements (frequency=1 each)

Top K Frequent Elements

Detect if a linked list has a cycle using Floyd two-pointer fast-slow algorithm. Return true if cycle exists.

### Sample Inputs & Outputs
Ex1: 3->2->0->-4->(back to 2) -> True
Ex2: 1->2->(back to 1) -> True
Ex3: 1->null -> False

### Edge Cases
1. Empty list -> False
2. Single node self-loop -> True
3. Single node no loop -> False
4. Cycle at very end of long list
5. Two nodes pointing to each other

Detect Cycle in Linked List

Return the middle node of a singly linked list. For even length, return the second middle node.

### Sample Inputs & Outputs
Ex1: 1->2->3->4->5 -> Node 3
Ex2: 1->2->3->4->5->6 -> Node 4
Ex3: [1] -> Node 1
Ex4: 1->2 -> Node 2

### Edge Cases
1. Single node -> return it
2. Two nodes -> return second
3. Even length -> second of two middles
4. Odd length -> exact middle
5. Very long list

Find Middle of Linked List

Merge two sorted linked lists into one sorted list by splicing nodes together. Return the merged head.

### Sample Inputs & Outputs
Ex1: 1->2->4 + 1->3->4 -> 1->1->2->3->4->4
Ex2: [] + [] -> []
Ex3: [] + [0] -> [0]
Ex4: 1->3->5 + 2->4->6 -> 1->2->3->4->5->6

### Edge Cases
1. Both lists empty
2. One list empty -> return the other
3. Lists of different lengths
4. All elements of one list smaller than other
5. Duplicate values across both lists

Merge Two Sorted Linked Lists

Determine if a linked list is a palindrome in O(n) time O(1) space.

### Sample Inputs & Outputs
Ex1: 1→2→2→1 → True
Ex2: 1→2 → False
Ex3: 1→2→3→2→1 → True

### Edge Cases
1. Single node → True
2. Two same nodes → True
3. Two different → False
4. Even length
5. Odd length (middle node skipped)

Palindrome Linked List

Reverse a singly linked list in-place and return the new head node. Must reverse actual links between nodes.

### Sample Inputs & Outputs
Ex1: 1->2->3->4->5 -> 5->4->3->2->1
Ex2: 1->2 -> 2->1
Ex3: [] -> []
Ex4: [1] -> [1]

### Edge Cases
1. Empty list -> null
2. Single node -> return same
3. Two nodes
4. Long list: iterative avoids stack overflow
5. List with all same values

Reverse Linked List

Design an LRU Cache supporting get and put both in O(1) time. Evict least recently used when capacity exceeded.

### Sample Inputs & Outputs
Ex1: cap=2,put(1,1),put(2,2),get(1)=1,put(3,3) evicts 2,get(2)=-1
Ex2: cap=1,put(1,1),put(2,2) evicts 1,get(1)=-1
Ex3: get non-existent key returns -1

### Edge Cases
1. get non-existent key -> -1
2. put existing key -> update value AND mark most recent
3. Capacity of 1
4. Multiple gets maintain recency order
5. put then immediate get -> still accessible

LRU Cache Implementation

Add two numbers represented as reversed linked lists. Return sum as reversed linked list.

### Sample Inputs & Outputs
Ex1: 2→4→3 + 5→6→4 → 7→0→8  (342+465=807)
Ex2: 0 + 0 → 0
Ex3: 9→9→9 + 9→9→9→9 → 8→9→9→0→1  (999+9999=10998)

### Edge Cases
1. Both single digit
2. Different lengths — shorter runs out first
3. Final carry produces extra node
4. Sum is zero (0+0)
5. Very long lists

Add Two Numbers as Linked Lists

Implement Copy linked list with random pointer. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Copy List with Random Pointer

Implement Flatten multilevel doubly linked list. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Flatten Multilevel Doubly Linked List

Find the node at which two singly linked lists intersect. Return None if no intersection.

### Sample Inputs & Outputs
Ex1: A=4→1→8→4→5, B=5→6→1→8→4→5 → Node with val 8
Ex2: A=[2,6,4], B=[1,5] → None
Ex3: A=[1], B=[1] same node → Node 1

### Edge Cases
1. Both lists are null
2. Lists of different lengths
3. Lists intersect at first node
4. Lists intersect at last node
5. No intersection

Intersection of Two Linked Lists

Remove the nth node from the end of a linked list. Return the head of the modified list.

### Sample Inputs & Outputs
Ex1: 1→2→3→4→5, n=2 → 1→2→3→5
Ex2: [1], n=1 → []
Ex3: 1→2, n=1 → [1]

### Edge Cases
1. Remove head (n=length)
2. Remove tail (n=1)
3. List with one node
4. n equals list length
5. List with two nodes

Remove Nth Node From End

Implement Reorder list L0→Ln→L1→Ln-1.... Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Reorder Linked List

Implement Rotate linked list by k places to right. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Rotate Linked List by K

Implement Sort linked list using merge sort. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Sort Linked List (Merge Sort)

Implement Swap adjacent nodes in linked list pairs. Return the expected result as described.

### Sample Inputs & Outputs
Ex1: See problem description for sample input/output.
Ex2: Edge case: empty or single element input.

### Edge Cases
1. Empty input
2. Single element
3. All same values
4. Already in desired state
5. Maximum constraints

Swap Nodes in Pairs

Compute nth Fibonacci using pure recursion. Understand the recursive call tree and identify repeated sub-problems. Optionally add memoization.

### Sample Inputs & Outputs
Ex1: n=5 → 5
Ex2: n=10 → 55
Ex3: n=0 → 0
Ex4: n=1 → 1

### Edge Cases
1. n=0 → 0 (base case)
2. n=1 → 1 (base case)
3. n=2 → F(1)+F(0)=1
4. Large n without memo → TLE
5. Negative n — undefined, handle

Fibonacci using Recursion

Move n disks from source peg to destination peg using auxiliary peg. Smaller disk must always be on top. Print each move.

### Sample Inputs & Outputs
Ex1: n=1 → 'Move disk 1: A→C'
Ex2: n=2 → 3 moves: A→B, A→C, B→C
Ex3: n=3 → 7 moves printed

### Edge Cases
1. n=0 → no moves
2. n=1 → single move
3. Large n: 2^n-1 moves (warn for n>20)
4. Different peg names
5. n=10 → 1023 moves

Tower of Hanoi

Place n queens on an n×n chessboard so no two attack each other. Return all valid board configurations.

### Sample Inputs & Outputs
Ex1: n=4 → 2 solutions: ['.Q..','...Q','Q...','..Q.'] and ['..Q.','Q...','...Q','.Q..']
Ex2: n=1 → [['Q']]
Ex3: n=2 or n=3 → [] (no solution)

### Edge Cases
1. n=1 → trivial solution
2. n=2, n=3 → no solution
3. n=4 → 2 solutions
4. n=8 → 92 solutions (classic)
5. Large n — exponential: use pruning

N-Queens Problem

Solve a 9×9 Sudoku puzzle in-place. Each digit 1-9 must appear exactly once per row, column, and 3×3 box.

### Sample Inputs & Outputs
Ex1: Standard sudoku puzzle → solved board
Ex2: Already solved → return as-is
Ex3: Minimal clues puzzle → unique solution

### Edge Cases
1. Already filled cell → skip
2. Row/column/box conflict → backtrack
3. Empty board → many solutions (any valid)
4. Multiple valid placements at some cell
5. No solution possible (invalid input)

Sudoku Solver

Given digits 2-9, return all possible letter combinations they could represent (like on phone keyboard).

### Sample Inputs & Outputs
Ex1: digits='23' → ['ad','ae','af','bd','be','bf','cd','ce','cf']
Ex2: digits='' → []
Ex3: digits='2' → ['a','b','c']

### Edge Cases
1. Empty input → []
2. Single digit → 3 or 4 letters
3. Long input → 4^n combinations
4. Digit '0' or '1' not on keyboard → handle if given
5. Digit 7 or 9 (4 letters)

Letter Combinations Phone Number

Generate all permutations of a given string. Handle duplicate characters by returning only unique permutations.

### Sample Inputs & Outputs
Ex1: s='abc' → ['abc','acb','bac','bca','cab','cba']
Ex2: s='aa' → ['aa']  (only unique)
Ex3: s='a' → ['a']

### Edge Cases
1. Single char → one permutation
2. All same chars 'aaa' → ['aaa']
3. String with duplicates 'aab'
4. Empty string → ['']
5. Long strings (6! = 720 permutations)

Permutations of a String

Find all paths for a rat to travel from top-left to bottom-right of n×n grid. Can move in 4 directions (U,D,L,R). Cell value 1=open, 0=blocked.

### Sample Inputs & Outputs
Ex1: [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]] → ['DDRDRR','DRDDRR']
Ex2: [[0]] → []
Ex3: [[1,1],[1,1]] → ['DR','RD']

### Edge Cases
1. Start or end is 0 → no paths
2. Single cell (n=1) → [''] if open
3. No valid path → []
4. Multiple paths — find all
5. Grid with isolated regions

Rat in a Maze

Generate all possible subsets (power set) of an array. Return all subsets including empty set. No duplicates.

### Sample Inputs & Outputs
Ex1: [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
Ex2: [0] → [[],[0]]
Ex3: [] → [[]]

### Edge Cases
1. Empty array → [[]] (only empty set)
2. Single element → [[],[element]]
3. Duplicates in input — sort and skip
4. Large arrays — 2^n subsets
5. Negative numbers work same

Subsets / Power Set

Sort an integer array using bubble sort — repeatedly compare adjacent elements and swap if in wrong order. Optimize with early exit if no swaps occur.

### Sample Inputs & Outputs
Ex1: [64,34,25,12,22,11,90] → [11,12,22,25,34,64,90]
Ex2: [5,1,4,2,8] → [1,2,4,5,8]
Ex3: [1,2,3] → [1,2,3]  (already sorted, 0 swaps)

### Edge Cases
1. Already sorted → 0 swaps (O(n) optimized)
2. Reverse sorted → worst case O(n²)
3. Single element unchanged
4. Two elements
5. All same [3,3,3]

Bubble Sort

Sort an array of non-negative integers using counting sort. Count occurrences, then reconstruct sorted array.

### Sample Inputs & Outputs
Ex1: [4,2,2,8,3,3,1] → [1,2,2,3,3,4,8]
Ex2: [1,4,1,2,7,5,2] → [1,1,2,2,4,5,7]
Ex3: [0] → [0]

### Edge Cases
1. All same values
2. Single element
3. Range much larger than n (inefficient)
4. Contains 0
5. Large values (determine max first)

Count Sort

Sort array using insertion sort: build sorted portion one element at a time by inserting each element into its correct position.

### Sample Inputs & Outputs
Ex1: [12,11,13,5,6] → [5,6,11,12,13]
Ex2: [1,2,3,4,5] → [1,2,3,4,5]  (already sorted, O(n))
Ex3: [5,4,3,2,1] → [1,2,3,4,5]  (worst case)

### Edge Cases
1. Already sorted → O(n) best case
2. Reverse sorted → worst case O(n²)
3. Single element
4. Two elements
5. All same values

Insertion Sort

Sort array using selection sort: repeatedly find the minimum element in the unsorted portion and place it at the beginning.

### Sample Inputs & Outputs
Ex1: [64,25,12,22,11] → [11,12,22,25,64]
Ex2: [5,1,4,2,8] → [1,2,4,5,8]
Ex3: [1] → [1]

### Edge Cases
1. Already sorted → O(n²) swaps still happen (unlike bubble sort)
2. Single element
3. All same values
4. Two elements
5. Reverse sorted → worst case

Selection Sort

Count the number of inversions in an array — pairs (i,j) where i<j but arr[i]>arr[j].

### Sample Inputs & Outputs
Ex1: [2,4,1,3,5] → 3  (pairs: (2,1),(4,1),(4,3))
Ex2: [1,2,3,4,5] → 0  (sorted)
Ex3: [5,4,3,2,1] → 10  (reverse sorted: n*(n-1)/2)

### Edge Cases
1. Sorted array → 0
2. Reverse sorted → n*(n-1)/2
3. Single or two elements
4. All same values → 0
5. Large array — O(n logn) required

Count Inversions in Array

Sort array using heap sort. Build a max-heap, then repeatedly extract maximum element to end of array.

### Sample Inputs & Outputs
Ex1: [12,11,13,5,6,7] → [5,6,7,11,12,13]
Ex2: [1] → [1]
Ex3: [3,1,2] → [1,2,3]

### Edge Cases
1. Single element
2. Already sorted
3. Reverse sorted
4. All same values
5. Two elements

Heap Sort

Sort an array using merge sort — divide into halves, recursively sort each, merge back in order. Stable O(n logn) algorithm.

### Sample Inputs & Outputs
Ex1: [38,27,43,3,9,82,10] → [3,9,10,27,38,43,82]
Ex2: [5,2,4,6,1,3] → [1,2,3,4,5,6]
Ex3: [1] → [1]  (base case)

### Edge Cases
1. Empty array → []
2. Single element → return as-is
3. Already sorted — still O(n logn)
4. All same [3,3,3]
5. Very large — check recursive depth

Merge Sort

Sort array using quicksort: pick a pivot, partition array so elements < pivot are left, > pivot are right, recurse on both sides.

### Sample Inputs & Outputs
Ex1: [10,7,8,9,1,5] → [1,5,7,8,9,10]
Ex2: [1,2,3,4,5] → [1,2,3,4,5]  (sorted — worst case with bad pivot)
Ex3: [3,6,8,10,1,2,1] → [1,1,2,3,6,8,10]

### Edge Cases
1. Already sorted with last-element pivot → O(n²) worst case
2. All same elements
3. Single element
4. Two elements
5. Very large array — check stack depth

Quick Sort

Sort an array of non-negative integers using radix sort — sort digit by digit from least significant to most significant using counting sort as subroutine.

### Sample Inputs & Outputs
Ex1: [170,45,75,90,802,24,2,66] → [2,24,45,66,75,90,170,802]
Ex2: [1,10,100] → [1,10,100]
Ex3: [5,4,3,2,1] → [1,2,3,4,5]

### Edge Cases
1. All same values
2. Numbers of different digit lengths
3. Single element
4. Array with 0s
5. Very large numbers (many digits)

Radix Sort

Sort array of 0s, 1s, 2s in-place in one pass without using sort library. Known as Dutch National Flag problem.

### Sample Inputs & Outputs
Ex1: [2,0,2,1,1,0] → [0,0,1,1,2,2]
Ex2: [2,0,1] → [0,1,2]
Ex3: [0] → [0]

### Edge Cases
1. All same color [2,2,2]
2. Already sorted
3. Single element
4. Two elements
5. All 0s and all 2s (no 1s)