LeetCode 75 · Medium · Part 1 of 2

Medium Problems — Part 1

Sliding window, binary search, graph BFS/DFS, two pointers, DP, and matrix problems. These are the core patterns that appear in the majority of real interviews.

Problems: 25
Difficulty: Medium
Topics: Arrays · Graphs · DP · Linked Lists · Binary Search
Tip: For Medium problems, the brute force usually exists — but interviewers want the optimal approach. Always ask yourself: "What if n were 10 million? Would my approach still work?" That question usually points you toward the right data structure or algorithm.
M 01 Medium Design Linked Lists Hash Map
LRU Cache
Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement get(key) returning the value (-1 if not found) and put(key, value) inserting or updating. Both must be O(1). When capacity is exceeded, evict the least recently used item.
Test Cases
cache = LRUCache(2) cache.put(1, 1) # cache: {1:1} cache.put(2, 2) # cache: {1:1, 2:2} cache.get(1) # → 1, cache: {2:2, 1:1} (1 is now MRU) cache.put(3, 3) # evicts key 2 (LRU), cache: {1:1, 3:3} cache.get(2) # → -1 (evicted) cache.get(3) # → 3
OrderedDictmove_to_end popitem(last=False)O(1) all ops
You need O(1) lookup (hash map) and O(1) eviction of the LRU item (ordered sequence). Python's OrderedDict is a doubly-linked list + hash map combined. It has a move_to_end(key) method — what would "most recently used" mean in terms of the order?
Solution
from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = OrderedDict() # maintains insertion/access order def get(self, key: int) -> int: if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.move_to_end(key) # update moves to MRU position self.cache[key] = value if len(self.cache) > self.capacity: self.cache.popitem(last=False) # pop LRU (front of ordered dict)
Key idea: OrderedDict is a doubly-linked list under the hood. We keep the "least recently used" item at the front (left) and the "most recently used" at the back (right). move_to_end(key) is O(1). popitem(last=False) evicts from the front — O(1). Both get and put are O(1).
Complexity
Time: O(1) for both get and put — hash map lookup + linked list pointer updates.
Space: O(capacity) — stores at most capacity items.
Alternative Approach
Manual doubly linked list + dict: Build your own DLL with prev/next pointers. Same complexity, more code — but demonstrates deeper understanding. Preferred in Java/C++ interviews where LinkedHashMap might not be "obvious". In Python, OrderedDict is the clean answer.
M 02 Medium Arrays Sorting
Merge Intervals
Given an array of intervals [[start, end], ...], merge all overlapping intervals and return a list of non-overlapping intervals that cover all intervals in the input.
Test Cases
merge([[1,3],[2,6],[8,10],[15,18]]) → [[1,6],[8,10],[15,18]] merge([[1,4],[4,5]]) → [[1,5]] # touching counts as overlapping merge([[1,4],[2,3]]) → [[1,4]] # fully contained merge([[1,2]]) → [[1,2]]
sort by startextend vs append interval overlap check
Sort intervals by start time. Then walk through: for each interval, does it overlap with the last merged interval? Two intervals overlap when the new one's start ≤ the last one's end. When they overlap, you merge by extending the end.
Solution
from typing import List def merge(intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) # sort by start time merged = [intervals[0]] for start, end in intervals[1:]: if start <= merged[-1][1]: # overlaps with last merged merged[-1][1] = max(merged[-1][1], end) # extend end else: merged.append([start, end]) # no overlap — add new interval return merged
Complexity
Time: O(n log n) — dominated by sorting. The merge pass is O(n).
Space: O(n) — output list can be up to n intervals.
Alternative Approach
If the input is already sorted, the sort step is skippable and you get O(n). This is worth mentioning in interviews when the input arrives in sorted order.
M 03 Medium Strings Sliding Window
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Test Cases
lengthOfLongestSubstring("abcabcbb") → 3 # "abc" lengthOfLongestSubstring("bbbbb") → 1 # "b" lengthOfLongestSubstring("pwwkew") → 3 # "wke" lengthOfLongestSubstring("") → 0
sliding windowhash map for last index left pointer jump
Use a sliding window [left, right]. Expand right one character at a time. When you hit a duplicate, where should left jump to? Not just +1 from where it is — you should jump it to just past the previous occurrence of the duplicate character.
Solution
def lengthOfLongestSubstring(s: str) -> int: char_idx = {} # maps char → most recent index seen left = 0 max_len = 0 for right, ch in enumerate(s): # If char seen and its last index is inside our current window if ch in char_idx and char_idx[ch] >= left: left = char_idx[ch] + 1 # jump left past the old occurrence char_idx[ch] = right max_len = max(max_len, right - left + 1) return max_len
Key idea: The hash map stores the most recent index of each character. When we see a duplicate inside our window, we move the left pointer past it. The check char_idx[ch] >= left prevents us from jumping left backward when the duplicate is outside the window.
Complexity
Time: O(n) — right pointer visits each character once; left only moves right.
Space: O(min(m, n)) where m is the charset size (26 for lowercase, 128 for ASCII). Effectively O(1) for fixed charsets.
M 04 Medium Graphs DFS BFS
Number of Islands
Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.
Test Cases
grid1 = [["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]] numIslands(grid1) → 1 grid2 = [["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]] numIslands(grid2) → 3
DFS flood fillmark visited by mutation 4-directional search
Scan the grid. Every time you find a '1' that hasn't been visited, you found a new island — increment the count. Then "sink" the entire island using DFS: recursively mark all connected '1's as '0' (visited). That way they won't be counted again.
Solution
from typing import List def numIslands(grid: List[List[str]]) -> int: if not grid: return 0 rows, cols = len(grid), len(grid[0]) count = 0 def dfs(r: int, c: int) -> None: # Out of bounds or water — stop if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0': return grid[r][c] = '0' # sink this land cell (mark visited) dfs(r + 1, c); dfs(r - 1, c) dfs(r, c + 1); dfs(r, c - 1) for r in range(rows): for c in range(cols): if grid[r][c] == '1': dfs(r, c) # sink the whole island count += 1 # this was a new island return count
Key idea: "Flood fill" — when we find land, we immediately sink the entire island by marking all connected cells as water ('0'). This avoids a separate visited set. Note: this mutates the input grid. If the input must be preserved, use a separate visited set.
Complexity
Time: O(m × n) — each cell is visited at most twice (once in the scan, once in DFS).
Space: O(m × n) — recursion stack depth in the worst case (one giant island).
Alternative Approach
BFS: Use a queue instead of recursion — avoids Python's recursion limit for huge grids. Same complexity, but iterative.
Union-Find: Connect adjacent '1' cells using disjoint sets. Count distinct components. Elegant for dynamic grids.
M 05 Medium Arrays Strings Hash Map
Group Anagrams
Given an array of strings strs, group the anagrams together. Return the groups in any order.
Test Cases
groupAnagrams(["eat","tea","tan","ate","nat","bat"]) → [["bat"],["nat","tan"],["ate","eat","tea"]] groupAnagrams([""]) → [[""]] groupAnagrams(["a"]) → [["a"]]
defaultdict(list)sorted string as key grouping pattern
Anagrams have the same characters with the same counts. What's a way to get a consistent "fingerprint" for a string that all its anagrams share? (Sorted characters work — all anagrams sort to the same string.)
Solution
from collections import defaultdict from typing import List def groupAnagrams(strs: List[str]) -> List[List[str]]: groups: dict = defaultdict(list) for s in strs: key = tuple(sorted(s)) # anagram fingerprint: sorted chars groups[key].append(s) return list(groups.values())
Key idea: Sorting the characters of a string produces a canonical form — all anagrams produce the same sorted string. We use this as the hash map key. We use tuple(sorted(s)) because lists are not hashable.
Complexity
Time: O(n × k log k) where n = number of strings, k = max string length (sorting each string).
Space: O(n × k) — storing all strings in the groups.
Alternative Approach
Character count key: Instead of sorting, build a tuple of 26 character counts. Key computation becomes O(k) instead of O(k log k) — faster for long strings. key = tuple(Counter(s)[c] for c in 'abcdefghijklmnopqrstuvwxyz')
M 06 Medium Strings Expand Around Center
Longest Palindromic Substring
Given a string s, return the longest substring that is a palindrome.
Test Cases
longestPalindrome("babad") → "bab" or "aba" (both valid) longestPalindrome("cbbd") → "bb" longestPalindrome("a") → "a" longestPalindrome("racecar") → "racecar"
expand around centerodd/even palindromes two-pointer expansion
Every palindrome has a center. Odd-length palindromes have a single center character; even-length palindromes have two center characters. Try expanding outward from every possible center. How many possible centers are there in a string of length n?
Solution
def longestPalindrome(s: str) -> str: result = "" def expand(l: int, r: int) -> str: # Expand outward while characters match while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1; r += 1 return s[l + 1:r] # l+1 and r because we went one step too far for i in range(len(s)): odd = expand(i, i) # odd-length: single center even = expand(i, i + 1) # even-length: two center chars if len(odd) > len(result): result = odd if len(even) > len(result): result = even return result
Complexity
Time: O(n²) — n centers × O(n) expansion per center.
Space: O(1) — no extra data structures (string slicing for return only).
Alternative Approach
Manacher's Algorithm: O(n) time using the symmetry of palindromes. Quite complex to implement — worth knowing exists but rarely required in interviews. The expand-around-center O(n²) approach is always accepted.
M 07 Medium Arrays Heap
Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. Order of results doesn't matter.
Test Cases
topKFrequent([1,1,1,2,2,3], k=2) → [1, 2] topKFrequent([1], k=1) → [1] topKFrequent([4,1,1,2,2,3], k=2) → [1, 2]
Counterheapq.nlargest bucket sort alternative
First count frequencies (Counter). Then you need the k largest frequencies. heapq.nlargest does this in O(n log k) — better than sorting all n elements.
Solution
import heapq from collections import Counter from typing import List def topKFrequent(nums: List[int], k: int) -> List[int]: count = Counter(nums) # nlargest picks the k keys with the largest count.get values return heapq.nlargest(k, count.keys(), key=count.get) # --- Bucket sort approach: O(n) time --- def topKFrequentBucket(nums: List[int], k: int) -> List[int]: count = Counter(nums) # Bucket index = frequency. Max frequency ≤ n. buckets = [[] for _ in range(len(nums) + 1)] for num, freq in count.items(): buckets[freq].append(num) # Collect from highest-frequency buckets result = [] for freq in range(len(buckets) - 1, -1, -1): result.extend(buckets[freq]) if len(result) >= k: return result[:k]
Complexity
Heap approach: Time O(n log k), Space O(n)
Bucket sort: Time O(n), Space O(n) — optimal, but uses more memory on sparse frequencies.
M 08 Medium Arrays Two Pointers
3Sum
Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.
Test Cases
threeSum([-1,0,1,2,-1,-4]) → [[-1,-1,2],[-1,0,1]] threeSum([0,1,1]) → [] threeSum([0,0,0]) → [[0,0,0]] threeSum([-2,0,0,2,2]) → [[-2,0,2]]
sort firstfix one + two pointers duplicate skipping
Sort the array first. Fix the first element (nums[i]), then use two pointers on the rest to find pairs that sum to -nums[i]. The sorted order makes it easy to skip duplicate values and avoid duplicate triplets.
Solution
from typing import List def threeSum(nums: List[int]) -> List[List[int]]: nums.sort() result = [] for i in range(len(nums) - 2): if i > 0 and nums[i] == nums[i - 1]: continue # skip duplicate first elements if nums[i] > 0: break # sorted: all remaining sums will be positive left, right = i + 1, len(nums) - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s == 0: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1; right -= 1 elif s < 0: left += 1 else: right -= 1 return result
Complexity
Time: O(n²) — outer loop O(n) × inner two-pointer scan O(n).
Space: O(n) — sorting is in-place; output list is O(n) in the worst case.
Alternative Approach
Hash set approach: For each pair (i,j), look up -(nums[i]+nums[j]) in a set — O(n²) time, O(n) space. Harder to de-duplicate results. The sort + two-pointer approach handles duplicates more cleanly.
M 09 Medium Arrays Prefix Sum
Subarray Sum Equals K
Given an array nums and an integer k, return the total number of subarrays whose elements sum to k. The array may contain negative numbers.
Test Cases
subarraySum([1,1,1], k=2) → 2 # [1,1] at [0,1] and [1,2] subarraySum([1,2,3], k=3) → 2 # [3] and [1,2] subarraySum([1,-1,1], k=1) → 3 # [1], [1,-1,1], [1] at index 2 subarraySum([-1,-1,1], k=-1) → 2
prefix sumhash map for count complement trick
A subarray sum from i to j equals prefix_sum[j] - prefix_sum[i-1]. So "does a subarray ending at j sum to k?" is equivalent to "does prefix_sum[j] - k appear earlier in the prefix sums?" Use a hash map to count how many times each prefix sum has been seen.
Solution
from collections import defaultdict from typing import List def subarraySum(nums: List[int], k: int) -> int: prefix_count: dict = defaultdict(int) prefix_count[0] = 1 # empty prefix (sum=0) has been seen once prefix_sum = 0 total = 0 for num in nums: prefix_sum += num # How many earlier prefix sums satisfy: prefix_sum - earlier = k? total += prefix_count[prefix_sum - k] prefix_count[prefix_sum] += 1 return total
Key idea: If prefix_sum[j] - prefix_sum[i] == k, then the subarray nums[i+1..j] sums to k. Rearranging: prefix_sum[i] == prefix_sum[j] - k. So for each j, count how many previous prefix sums equal prefix_sum[j] - k. Initializing with prefix_count[0] = 1 handles subarrays starting from index 0.
Complexity
Time: O(n) — one pass through the array.
Space: O(n) — hash map can hold up to n distinct prefix sums.
Alternative Approach
Brute force: O(n²) with nested loops computing all subarray sums. Note: sliding window does NOT work here because of negative numbers — the window can't expand/shrink monotonically. Prefix sum + hash map is the correct O(n) approach for negative numbers.
M 10 Medium Arrays Binary Search
Search in Rotated Sorted Array
Given an integer array nums sorted in ascending order then rotated at some pivot, and a target value, return the index of target or -1 if not present. Solve in O(log n).
Test Cases
search([4,5,6,7,0,1,2], 0) → 4 search([4,5,6,7,0,1,2], 3) → -1 search([1], 0) → -1 search([3,1], 1) → 1
binary searchidentify sorted half rotation logic
Even after rotation, one of the two halves is always sorted. If nums[left] ≤ nums[mid], the left half is sorted. Otherwise the right half is sorted. Check if the target falls within the sorted half. If yes, search there. Otherwise search the other half.
Solution
from typing import List def search(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # Left half is sorted if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 # target in sorted left half else: left = mid + 1 # target in right half # Right half is sorted else: if nums[mid] < target <= nums[right]: left = mid + 1 # target in sorted right half else: right = mid - 1 # target in left half return -1
Complexity
Time: O(log n) — standard binary search, halving the search space each step.
Space: O(1) — no extra storage.
M 11 Medium Arrays Dynamic Programming
Maximum Subarray (Kadane's Algorithm)
Given an integer array nums, find the subarray with the largest sum and return its sum. The subarray must contain at least one element.
Test Cases
maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) → 6 # [4,-1,2,1] maxSubArray([1]) → 1 maxSubArray([5,4,-1,7,8]) → 23 # entire array maxSubArray([-1,-2,-3]) → -1 # must pick at least one
Kadane's algorithmrunning sum reset when negative
For each element, ask: "Is it better to extend the previous subarray, or start fresh from here?" If the running sum becomes negative, drop it and start fresh — a negative prefix only hurts future sums.
Solution
from typing import List def maxSubArray(nums: List[int]) -> int: max_sum = nums[0] curr_sum = nums[0] for num in nums[1:]: # Either extend the current subarray, or start fresh from num curr_sum = max(num, curr_sum + num) max_sum = max(max_sum, curr_sum) return max_sum
Complexity
Time: O(n) — single pass, O(1) work per element.
Space: O(1) — just two variables.
Alternative Approach
DP array: dp[i] = max(nums[i], dp[i-1] + nums[i]) — same logic but O(n) space. No benefit.
Divide and Conquer: O(n log n) time — elegant but slower than Kadane's. Know it exists.
M 12 Medium Arrays Matrix
Rotate Image
Given an n×n matrix, rotate it 90 degrees clockwise in-place.
Test Cases
matrix = [[1,2,3],[4,5,6],[7,8,9]] rotate(matrix) → [[7,4,1],[8,5,2],[9,6,3]] matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] rotate(matrix) → [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
transposereverse rows in-place matrix manipulation
A 90° clockwise rotation = transpose + then reverse each row. Transpose means flipping across the diagonal: matrix[i][j] ↔ matrix[j][i]. Try it on a 3×3 example mentally first.
Solution
from typing import List def rotate(matrix: List[List[int]]) -> None: n = len(matrix) # Step 1: Transpose — swap matrix[i][j] with matrix[j][i] for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Step 2: Reverse each row for row in matrix: row.reverse()
Complexity
Time: O(n²) — visit every cell once for transpose, once for reverse.
Space: O(1) — all operations in-place.
Alternative Approach
Counter-clockwise (90° CCW): Transpose then reverse each column (or reverse rows then transpose).
4-cell cycle rotation: Rotate 4 corners at a time in a cycle — more complex but also O(1) space.
M 13 Medium Arrays Matrix
Spiral Matrix
Given an m×n matrix, return all elements in spiral order (clockwise from top-left).
Test Cases
spiralOrder([[1,2,3],[4,5,6],[7,8,9]]) → [1,2,3,6,9,8,7,4,5] spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]]) → [1,2,3,4,8,12,11,10,9,5,6,7]
boundary shrinking4-direction traversal top/bottom/left/right pointers
Track four boundaries: top, bottom, left, right. Each full loop of the spiral shrinks all four boundaries by 1. Walk: left→right (top row), top→bottom (right col), right→left (bottom row), bottom→top (left col). Don't forget to shrink each boundary after processing it.
Solution
from typing import List def spiralOrder(matrix: List[List[int]]) -> List[int]: result = [] top, bottom = 0, len(matrix) - 1 left, right = 0, len(matrix[0]) - 1 while top <= bottom and left <= right: # → top row: left to right for c in range(left, right + 1): result.append(matrix[top][c]) top += 1 # ↓ right col: top to bottom for r in range(top, bottom + 1): result.append(matrix[r][right]) right -= 1 if top <= bottom: # guard: might have exhausted rows # ← bottom row: right to left for c in range(right, left - 1, -1): result.append(matrix[bottom][c]) bottom -= 1 if left <= right: # guard: might have exhausted cols # ↑ left col: bottom to top for r in range(bottom, top - 1, -1): result.append(matrix[r][left]) left += 1 return result
Complexity
Time: O(m × n) — every cell is visited exactly once.
Space: O(1) — excluding the output array.
M 14 Medium Linked Lists Math
Add Two Numbers
Two non-empty linked lists represent two non-negative integers stored in reverse order. Each node contains a single digit. Add the two numbers and return the sum as a linked list.
Test Cases
l1 = 2→4→3 (represents 342) l2 = 5→6→4 (represents 465) addTwoNumbers(l1, l2) → 7→0→8 (represents 807) l1 = 0, l2 = 0 → 0 l1 = 9→9→9→9→9→9→9, l2 = 9→9→9→9 → 8→9→9→9→0→0→0→1
carry propagationdummy head divmod()linked list construction
Simulate grade-school addition digit by digit. Track the carry. The loop should continue as long as either list has digits OR there's a carry remaining. Use divmod(val, 10) to get the carry and the digit to store.
Solution
from typing import Optional class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0) curr = dummy carry = 0 while l1 or l2 or carry: val = carry if l1: val += l1.val; l1 = l1.next if l2: val += l2.val; l2 = l2.next carry, digit = divmod(val, 10) # carry = val//10, digit = val%10 curr.next = ListNode(digit) curr = curr.next return dummy.next
Complexity
Time: O(max(m, n)) where m and n are the lengths of the two lists.
Space: O(max(m, n)) — the result list can be at most max(m,n)+1 nodes long.
M 15 Medium Arrays Heap
Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element. Note: kth largest is not kth distinct.
Test Cases
findKthLargest([3,2,1,5,6,4], k=2) → 5 findKthLargest([3,2,3,1,2,4,5,5,6], k=4) → 4
min-heap of size kheapq Quickselect alternative
Maintain a min-heap of size k. If the heap has k elements and you see something larger than the minimum, replace it. The top of the heap (the minimum of the k largest elements) is your answer.
Solution
import heapq from typing import List def findKthLargest(nums: List[int], k: int) -> int: # Min-heap of size k — the heap top is always the kth largest seen so far heap = nums[:k] heapq.heapify(heap) for num in nums[k:]: if num > heap[0]: heapq.heapreplace(heap, num) # pop min, push num in O(log k) return heap[0] # smallest of the k largest = kth largest overall
Complexity
Time: O(n log k) — each element processed in O(log k) heap ops.
Space: O(k) — only the heap of size k.
Alternative Approach
Sort: sorted(nums)[-k] — O(n log n), clean one-liner. Accepted in interviews.
Quickselect: Average O(n), worst case O(n²). Partition around a pivot like Quicksort but only recurse into one half. Best theoretical average, but the heap approach is more predictable and simpler to code correctly.
M 16 Medium Recursion Backtracking
Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Test Cases
generateParenthesis(1) → ["()"] generateParenthesis(2) → ["(())", "()()"] generateParenthesis(3) → ["((()))", "(()())", "(())()", "()(())", "()()()"]
backtrackingopen/close count tracking constraint-based recursion
At each step, you can add '(' if you have open parens remaining. You can add ')' only if the number of open parens placed so far exceeds the number of close parens placed. Base case: when the string has length 2n, add it to results.
Solution
from typing import List def generateParenthesis(n: int) -> List[str]: result = [] def backtrack(s: str, open_cnt: int, close_cnt: int) -> None: if len(s) == 2 * n: result.append(s) return if open_cnt < n: backtrack(s + '(', open_cnt + 1, close_cnt) if close_cnt < open_cnt: backtrack(s + ')', open_cnt, close_cnt + 1) backtrack('', 0, 0) return result
Complexity
Time: O(4ⁿ / √n) — this is the nth Catalan number. Each valid sequence is O(n) to construct.
Space: O(n) — recursion depth is at most 2n (the length of the string being built).
M 17 Medium Arrays BFS
Rotting Oranges
In a grid, 0 = empty, 1 = fresh orange, 2 = rotten orange. Every minute, any fresh orange adjacent (4-directional) to a rotten one becomes rotten. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.
Test Cases
grid = [[2,1,1],[1,1,0],[0,1,1]] → 4 grid = [[2,1,1],[0,1,1],[1,0,1]] → -1 (bottom-left fresh is isolated) grid = [[0,2]] → 0 (no fresh oranges)
BFS multi-sourcedeque layer-by-layer traversal
Start BFS from ALL rotten oranges simultaneously (multi-source BFS). Each BFS level = one minute. Track how many fresh oranges remain. If any are left when BFS ends, return -1.
Solution
from collections import deque from typing import List def orangesRotting(grid: List[List[int]]) -> int: rows, cols = len(grid), len(grid[0]) queue = deque() fresh = 0 # Seed queue with all initially rotten oranges; count fresh ones for r in range(rows): for c in range(cols): if grid[r][c] == 2: queue.append((r, c, 0)) elif grid[r][c] == 1: fresh += 1 if fresh == 0: return 0 minutes = 0 while queue: r, c, minutes = queue.popleft() for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1: grid[nr][nc] = 2 fresh -= 1 queue.append((nr, nc, minutes + 1)) return minutes if fresh == 0 else -1
Complexity
Time: O(m × n) — each cell is enqueued/processed at most once.
Space: O(m × n) — queue can hold all cells in the worst case.
M 18 Medium Arrays Binary Search
Find First and Last Position of Element in Sorted Array
Given a sorted integer array nums and a target, return the starting and ending positions of target. Return [-1, -1] if target is not found. Solve in O(log n).
Test Cases
searchRange([5,7,7,8,8,10], 8) → [3, 4] searchRange([5,7,7,8,8,10], 6) → [-1, -1] searchRange([], 0) → [-1, -1] searchRange([1], 1) → [0, 0]
bisect_leftbisect_right two binary searches
Run binary search twice: once to find the leftmost position of target, once to find the rightmost. Python's bisect module does exactly this. bisect_left gives the first position, bisect_right gives one past the last.
Solution
import bisect from typing import List def searchRange(nums: List[int], target: int) -> List[int]: left = bisect.bisect_left(nums, target) # Check if target actually exists at this position if left == len(nums) or nums[left] != target: return [-1, -1] right = bisect.bisect_right(nums, target) - 1 return [left, right]
Complexity
Time: O(log n) — two binary searches, each O(log n).
Space: O(1).
M 19 Medium Arrays Dynamic Programming
House Robber
Given an array of non-negative integers nums representing the amount of money in each house, return the maximum amount you can rob without robbing two adjacent houses.
Test Cases
rob([1,2,3,1]) → 4 # rob house 1 (1) + house 3 (3) = 4 rob([2,7,9,3,1]) → 12 # rob house 1 (2) + house 3 (9) + house 5 (1) = 12 rob([0]) → 0 rob([1,2]) → 2
DP rolling variablesno adjacent constraint max(skip, take)
At each house, you decide: rob it (get its value + what you had 2 houses ago) or skip it (keep what you had 1 house ago). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Do you really need an array, or just two variables?
Solution
from typing import List def rob(nums: List[int]) -> int: # prev2 = dp[i-2], prev1 = dp[i-1] prev2, prev1 = 0, 0 for num in nums: curr = max(prev1, prev2 + num) # skip or rob current house prev2 = prev1 prev1 = curr return prev1
Complexity
Time: O(n) — one pass.
Space: O(1) — only two variables needed, not an array.
M 20 Medium Arrays Two Pointers
Container With Most Water
Given an array height where height[i] is the height of a vertical line at position i, find two lines that form a container holding the most water. Return the maximum area.
Test Cases
maxArea([1,8,6,2,5,4,8,3,7]) → 49 # lines at index 1 (h=8) and 8 (h=7) maxArea([1,1]) → 1 maxArea([4,3,2,1,4]) → 16
two pointers from endsmove shorter side greedy observation
Start with left at 0 and right at the end — this maximizes width. Area = min(height[left], height[right]) × (right - left). Which pointer should you move? Moving the taller one can only decrease area (width decreases, height can only stay or decrease). So always move the shorter one.
Solution
from typing import List def maxArea(height: List[int]) -> int: left, right = 0, len(height) - 1 max_water = 0 while left < right: water = min(height[left], height[right]) * (right - left) max_water = max(max_water, water) # Move the shorter line inward — moving the taller can't improve the area if height[left] < height[right]: left += 1 else: right -= 1 return max_water
Complexity
Time: O(n) — each pointer moves at most n steps total.
Space: O(1).
M 21 Medium Arrays Greedy Heap
Meeting Rooms II
Given a list of meeting time intervals [start, end], find the minimum number of conference rooms required.
Test Cases
minMeetingRooms([[0,30],[5,10],[15,20]]) → 2 minMeetingRooms([[7,10],[2,4]]) → 1 minMeetingRooms([[0,5],[5,10]]) → 1 # back-to-back, not overlapping
sort by startmin-heap of end times heapreplace for reuse
Sort meetings by start time. Use a min-heap where each entry is the end time of an active meeting. For each new meeting: if the earliest-ending meeting finishes before this one starts, we can reuse that room (pop and push new end time). Otherwise, we need a new room (push to heap).
Solution
import heapq from typing import List def minMeetingRooms(intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: x[0]) heap = [] # min-heap of meeting end times for start, end in intervals: if heap and heap[0] <= start: heapq.heapreplace(heap, end) # reuse the room that freed up else: heapq.heappush(heap, end) # need a new room return len(heap) # number of rooms in use
Complexity
Time: O(n log n) — sorting + heap operations.
Space: O(n) — heap holds at most n end times.
Alternative Approach
Event sweep: Create events (+1 for start, -1 for end), sort by time, track running max. O(n log n) time. Cleaner to understand for some people.
M 22 Medium Dynamic Programming
Coin Change
Given an array of coin denominations coins and an integer amount, return the fewest number of coins needed to make up that amount. Return -1 if it cannot be done.
Test Cases
coinChange([1,5,11], 15) → 3 # 5+5+5 (NOT 1+1+...) — greedy fails here coinChange([1,2,5], 11) → 3 # 5+5+1 coinChange([2], 3) → -1 (can't make 3 with only 2s) coinChange([1], 0) → 0
bottom-up DPdp[amount] table unbounded knapsack
dp[i] = minimum coins to make amount i. Start: dp[0]=0, dp[1..amount]=inf. For each coin, for each amount from coin to amount: dp[x] = min(dp[x], dp[x-coin] + 1). Why does greedy fail here? Try coins=[1,5,11], amount=15 — greedy picks 11+1+1+1+1=5 coins, but 5+5+5=3 is optimal.
Solution
from typing import List def coinChange(coins: List[int], amount: int) -> int: # dp[i] = min coins to make exactly amount i dp = [float('inf')] * (amount + 1) dp[0] = 0 # 0 coins needed to make amount 0 for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1
Key insight: This is the unbounded knapsack problem — each coin can be used any number of times. The inner loop goes from coin to amount (not the reverse), allowing coins to be reused.
Complexity
Time: O(amount × len(coins)) — two nested loops.
Space: O(amount) — the dp array.
M 23 Medium Arrays
Product of Array Except Self
Given an integer array nums, return an array output where output[i] equals the product of all elements of nums except nums[i]. Solve without using division and in O(n).
Test Cases
productExceptSelf([1,2,3,4]) → [24,12,8,6] productExceptSelf([-1,1,0,-3,3]) → [0,0,9,0,0] productExceptSelf([0,0]) → [0,0]
prefix productssuffix products two-pass O(1) space
output[i] = (product of all elements to the left of i) × (product of all elements to the right of i). Can you compute the left products and right products separately, then combine them?
Solution
from typing import List def productExceptSelf(nums: List[int]) -> List[int]: n = len(nums) result = [1] * n # Pass 1 (left→right): result[i] = product of all nums[0..i-1] prefix = 1 for i in range(n): result[i] = prefix prefix *= nums[i] # Pass 2 (right→left): multiply in product of all nums[i+1..n-1] suffix = 1 for i in range(n - 1, -1, -1): result[i] *= suffix suffix *= nums[i] return result
Complexity
Time: O(n) — two linear passes.
Space: O(1) — excluding the output array (we reuse it for prefix products).
M 24 Medium Arrays Hash Set
Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Solve in O(n) time.
Test Cases
longestConsecutive([100,4,200,1,3,2]) → 4 # [1,2,3,4] longestConsecutive([0,3,7,2,5,8,4,6,0,1]) → 9 longestConsecutive([]) → 0
hash setsequence start detection O(n) amortized
Put all numbers in a set (O(1) lookup). For each number, only start counting a sequence if it's the START of a sequence — i.e., num-1 is NOT in the set. This ensures each sequence is counted exactly once, giving O(n) total.
Solution
from typing import List def longestConsecutive(nums: List[int]) -> int: num_set = set(nums) best = 0 for num in num_set: # Only start counting from the beginning of a sequence if num - 1 not in num_set: curr = num streak = 1 while curr + 1 in num_set: curr += 1 streak += 1 best = max(best, streak) return best
Key insight: The "only start from the beginning" check is what makes this O(n). Without it, we'd re-count subsequences. With it, each number is traversed at most twice (once in the outer loop, once in the inner while).
Complexity
Time: O(n) — each number is visited at most twice total across all iterations.
Space: O(n) — the set stores all n numbers.
M 25 Medium Arrays Binary Search
Koko Eating Bananas
Koko has piles of bananas piles[i] and h hours. She eats at rate k bananas/hour (finishing a pile or just eating k from it each hour). Find the minimum k such that she can eat all bananas within h hours.
Test Cases
minEatingSpeed([3,6,7,11], h=8) → 4 minEatingSpeed([30,11,23,4,20], h=5) → 30 # must finish each pile in 1 hour minEatingSpeed([1,1,1,999999999], h=10) → 999999999
binary search on answermath.ceil feasibility check function
The answer k is somewhere between 1 and max(piles). For a given k, you can check feasibility in O(n): sum up ceil(pile/k) for all piles and see if total ≤ h. Binary search on k.
Solution
import math from typing import List def minEatingSpeed(piles: List[int], h: int) -> int: left, right = 1, max(piles) while left < right: mid = (left + right) // 2 hours = sum(math.ceil(p / mid) for p in piles) if hours <= h: right = mid # mid works — try smaller else: left = mid + 1 # mid too slow — try faster return left
Key pattern — "binary search on the answer": Whenever you need to minimize/maximize a value subject to a feasibility condition that is monotone (if k works, all k' > k also work), binary search on the answer space. Here the feasibility check is O(n), giving total O(n log m) where m = max(piles).
Complexity
Time: O(n log m) where m = max(piles). Binary search runs log(m) iterations; each feasibility check is O(n).
Space: O(1).
← Easy Problems Medium Part 2 →