LeetCode: 50 Medium-Hard Problems

with Solutions

Questions Asked in
1. Merge k Sorted Lists

Problem:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe the complexity.

Solution:
Approach:Use a min-heap (priority queue) with k heads. Push the head of each list into the heap keyed by node
value. Repeatedly pop the smallest node, append to result, and push its next node if exists. Pseudocode: 1.
Create a min-heap. For each list head, if not null push (value, node). 2. dummy = Node(0); tail = dummy 3.
while heap not empty: val, node = heap.pop() tail.next = node tail = tail.next if
node.next: heap.push((node.next.val, node.next)) 4. return dummy.next Time Complexity: O(N log k) where N is
total number of nodes, k is number of lists. Space Complexity: O(k) for the heap. Notes: Consider divide-and-
conquer merging for large k.

2. Median of Two Sorted Arrays

Problem:

Find the median of two sorted arrays of sizes m and n in O(log(min(m,n))) time.

Solution:
Approach:Binary search on the smaller array to find a partition so that left halves contain exactly half of
total elements and max(left) <= min(right). Pseudocode: 1. Ensure A is smaller array. Let m=len(A), n=len(B).
low=0, high=m 2. while low<=high: i=(low+high)//2 j=(m+n+1)//2 - i Aleft = -inf if i==0 else
A[i-1] Aright = +inf if i==m else A[i] Bleft = -inf if j==0 else B[j-1] Bright = +inf if j==n else
B[j] if Aleft<=Bright and Bleft<=Aright: compute median from max(Aleft,Bleft) and min(Aright,Bright)
elif Aleft>Bright: high=i-1 else: low=i+1 Time Complexity: O(log min(m,n)).
3. Longest Consecutive Sequence

Problem:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Must run in
O(n).

Solution:
Approach:Use a hash set. For each number, check if it's the start of a sequence (num-1 not in set). If so,
expand forward counting consecutive numbers. Pseudocode: 1. s = set(nums) 2. best = 0 3. for num in s: if
num-1 not in s: length=1; cur=num while cur+1 in s: cur+=1; length+=1 best = max(best,
length) 4. return best Time Complexity: O(n) average. Space: O(n).

4. Minimum Window Substring

Problem:

Given strings S and T, find the minimum window in S which will contain all the characters in T.

Solution:
Approach: Sliding window with two pointers and frequency maps. Expand right to include required chars, then
contract left to minimize while keeping validity. Pseudocode: 1. need = Counter(T); missing = len(T) 2.

left=0; start=0; best_len=inf 3. for right, ch in enumerate(S): if need[ch]>0: missing -=1 need[ch]-=1
while missing==0: if right-left+1 < best_len: update best need[S[left]] +=1 if
need[S[left]]>0: missing+=1 left+=1 4. return substring or empty Time Complexity: O(n).

5. Sliding Window Maximum

Problem:

Given an array, find the maximum for each sliding window of size k.

Solution:
Approach:Use a deque storing indices of candidates in decreasing order of value. Pop from back while new
element larger; pop from front if out of window. Pseudocode: 1. dq = deque() 2. for i in range(n): while
dq and nums[dq[-1]] < nums[i]: dq.pop() dq.append(i) if dq[0] == i-k: dq.popleft() if i>=k-1:
output nums[dq[0]] Time Complexity: O(n).
6. Trapping Rain Water

Problem:

Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.

Solution:
Approach:Two-pointer technique keeping track of left_max and right_max. Move pointers inward from lower side
and accumulate trapped water. Pseudocode: 1. left=0; right=n-1; left_max=0; right_max=0; ans=0 2. while
left<right: if height[left] < height[right]: if height[left]>=left_max: left_max=height[left]
else: ans += left_max - height[left] left+=1 else: if height[right]>=right_max:
right_max=height[right] else: ans += right_max - height[right] right-=1 3. return ans Time
Complexity: O(n).

7. Word Ladder (Shortest Transformation)

Problem:

Given beginWord, endWord, and a dictionary, find the length of shortest transformation sequence.

Solution:
Approach:BFS on words; precompute generic states mapping to words. Use bidirectional BFS to optimize.
Pseudocode: Preprocess patterns, BFS from both ends until meet.

10. Top K Frequent Elements

Problem:

Given a non-empty array of integers, return the k most frequent elements.

Solution:
Approach:Frequency map + bucket sort (O(n)) or heap (O(n log k)).

11. Course Schedule (Topological Sort)

Problem:

Given numCourses and prerequisites, return if you can finish all courses.

Solution:
Approach:Build graph; use Kahn's algorithm with in-degree BFS. If processed count != numCourses, cycle
exists.
12. Number of Islands

Problem:

Given a 2D grid of '1's and '0's, count islands.

Solution:
Approach:DFS/BFS to mark connected lands; increment count per DFS start.

13. Subarray Sum Equals K

Problem:

Find total number of continuous subarrays with sum equals k.

Solution:
Approach:Prefix-sum + hashmap of counts of prefix sums; count occurrences of s-k.

14. Find Median from Data Stream

Problem:

Design a data structure that supports addNum and findMedian efficiently.

Solution:
Approach:Two heaps: max-heap for lower half, min-heap for upper half; balance sizes.

15. Binary Tree Maximum Path Sum

Find maximum path sum in binary tree (path can start/end anywhere).

Solution:
Approach:DFS postorder computing max gain from children, update global max with node.val+left+right.
 16. LRU Cache

Problem:

Design an LRU cache with get and put in O(1).

Solution:
Approach:Hashmap + doubly-linked list to maintain recency order; evict tail on capacity overflow.

17. Design Search Autocomplete System

Problem:

Autocomplete returns top-k historical sentences for a typed prefix.

Solution:
Approach: Trie with top-k lists per node or inverted index + ranking. For scale, use caching and offline
frequency aggregation.

18. Find Peak Element

Problem:

Find any peak element in an array using O(log n) time.

Solution:
Approach:Binary search comparing mid and mid+1 to determine direction of slope; converge to a peak.

19. Number of Connected Components in Undirected Graph

Problem:

Given n and edges, return number of connected components.

Solution:
Approach:Union-Find with path compression or DFS/BFS; count distinct parents after unions.
20. Serialize/Deserialize N-ary Tree

Problem:

Serialize and deserialize an N-ary tree preserving structure.

Solution:
Approach:Preorder with child counts (value, num_children), then recursively serialize children.

21. Word Search II

Problem:

Given a board and list of words, find all words on board. Words formed by adjacent cells.

Solution:
Approach:Build a Trie of words and do DFS from each cell, pruning branches not in Trie; mark found words.

22. Edit Distance (Levenshtein Distance)

Problem:

Given two strings, compute minimum operations to convert one to another (insert, delete, replace).

Solution:
Approach: DP with matrix dp[i][j] representing cost to convert prefixes. dp base cases for empty strings,
recurrence with min of insert/delete/replace.
23. Merge Intervals
Problem:

Given intervals, merge all overlapping intervals.

Solution:
Approach:Sort by start time, iterate merging overlapping intervals by updating end = max(end, current_end).

24. Insert Interval

Insert a new interval into sorted non-overlapping intervals and merge if necessary.

Solution:
Approach:Add all intervals before new, merge overlapping with new, then add remaining; maintain result list.

25. Maximum Sum Rectangle in 2D Matrix

Problem:

Find submatrix with maximum sum in a 2D matrix.

Solution:
Approach: Fix left and right columns, collapse rows into 1D sums, run Kadane's algorithm on rows for each pair
of columns. Complexity O(cols^2 * rows).

26. Sliding Window Median

Problem:

Find median for each sliding window of size k in an array.

Solution:
Approach:Two heaps supporting lazy deletion or use balanced BST; maintain window size balance and report
median.
27. Binary Indexed Tree / Fenwick Tree (Range Sum)

Problem:

Support prefix sum and point update efficiently.

Solution:
Approach:Fenwick tree with update and query both O(log n); use bit manipulation idx += idx & -idx.

28. Count of Smaller Numbers After Self

Problem:

For each element, count numbers to its right that are smaller.

Solution:
Approach:Use Fenwick tree with coordinate compression or BST with counts; iterate from right to left.

29. K Closest Points to Origin

Problem:

Return k points closest to origin.

Solution:
Approach:Use max-heap of size k or Quickselect based on distance squared to achieve average O(n).
30. Minimum Cost to Connect Sticks
Problem:

Given lengths, combine sticks with minimal cost where cost is sum of two sticks each combine.

Solution:
Approach:Min-heap; repeatedly pop two smallest, sum cost, push back combined length. Time O(n log n).

31. Alien Dictionary

Given sorted dictionary of an alien language, derive order of characters.

Solution:
Approach:Build graph from adjacent word comparisons, then topological sort. Handle invalid cases like prefix
issues.

32. Course Schedule II (Topological Order)

Problem:

Return an ordering of courses you should take to finish all courses.

Solution:
Approach:Kahn's algorithm to produce topological ordering; if cycle detected return empty list.

33. Sliding Window Maximum (Variant with Updates)

Problem:

Support sliding window max with updates in stream.

Solution:
Approach:Use segment tree or indexed max-heap with lazy removals; maintain structure for range queries and
point updates.
34. Distinct Subsequences (DP)

Problem:

Count how many distinct ways S can form T by deleting chars.

Solution:
Approach: DP where dp[i][j] = ways S[:i] forms T[:j]; recurrence accounting match/mismatch. Optimize to 1D
from right to left.

35. Minimum Window Subsequence

Problem:

Find minimum window in S that has T as a subsequence (not necessarily contiguous).

Solution:
Approach:Two-pointer with DP/backtracking start positions; iterate target pointer and then expand/contract to
find minimal starts.

36. Longest Increasing Path in a Matrix

Problem:

Find length of longest increasing path in matrix moving 4 directions.

Solution:
Approach: DFS with memoization (DP) per cell; compute longest path using neighbors with greater values.
Complexity O(mn).

37. Trapping Rain Water II (3D)

Problem:

Given 2D elevation map, compute trapped water volume.

Solution:
Approach:Use min-heap of boundary cells and BFS inward; keep track of max boundary height and accumulate
trapped water.
38. Substring with Concatenation of All Words

Problem:

Find starting indices of substrings that are concatenation of each word exactly once.

Solution:
Approach:Sliding window with hashmap of counts of words; iterate offsets by word length and check counts.

39. Count of Range Sum

Problem:

Given array and lower/upper bounds, count range sums within [lower,upper].
Solution:
Approach:Use prefix sums and modified merge sort to count valid pairs in O(n log n).
40. The Skyline Problem
Problem:

Given buildings, compute skyline outline.

Solution:
Approach:Sweep line using max-heap of active heights; process sorted critical points, add/remove heights and
record changes.

41. Maximum Product Subarray

Problem:

Find maximum product of a contiguous subarray.

Solution:
Approach:Track current max and min because negative numbers flip sign; update via multiplication and reset
when zero.

42. Word Break II (All sentences)

Problem:

Return all possible sentences by splitting string into dictionary words.

Solution:
Approach:DFS with memoization to build sentences; prune using reachable DP precheck (wordBreak boolean DP).

43. Cheapest Flights Within K Stops

Problem:

Find cheapest flight within K stops between src and dst.

Solution:
Approach:Modified Dijkstra or Bellman-Ford relaxation for up to K+1 edges; DP on stops limit or BFS on
layers.
44. Minimum Effort Path

Problem:
Path in grid minimizing maximum absolute difference between cells along path.

Solution:
Approach: Binary search on effort threshold + BFS/DFS to check connectivity, or Dijkstra variant minimizing
max-edge metric.

45. Number of Ways to Paint N x 3 Grid

Problem:
Count ways with coloring constraints (example combinatorics/dp).

Solution:
Approach:Use state compression and DP per column with transitions based on valid colorings; optimize with
recurrence.

46.Reconstruct Itinerary
Problem:

Given flight tickets, reconstruct itinerary in lexical order using all tickets once.

Solution:
Approach:Hierholzer's algorithm for Eulerian path using DFS with sorted adjacency stacks; append in reverse
order.

47. Minimum Window Substring (Advanced with weights)

Find min window with weighted character requirements.

Solution:
Approach:Sliding window but track weighted deficits; similar contraction/expansion with cumulative weights.
48. Design TinyURL / Encode-Decode Strings
Problem:

Design encode and decode methods for TinyURL-like service.

Solution:
Approach:Use incremental id with base62 encoding or hash + collision handling; store mapping in DB/cache.

49. Find Kth Smallest Pair Distance

Given array, find k-th smallest absolute difference between any two elements.

Solution:
Approach:Binary search on distance + two-pointer count method to count pairs <= mid; complexity O(n log W).

50. Design a Rate Limiter

Design token-bucket or leaky-bucket rate limiter supporting distributed clients.

Approach:Token bucket algorithm with centralized counters or distributed using Redis with atomic scripts;
handle bursts.