Core building blocks. Master these patterns and Medium problems become much easier.
Each problem tests one clear idea — recognize the pattern, apply it.
Problems: 16
Difficulty: Easy
Topics: Arrays · Strings · DP · Linked Lists
Learning approach: Read the problem. Try to solve it using the test cases.
Click Hint if you're stuck — it gives you a guiding question, not the answer.
Only reveal the solution after you've made a real attempt.
Given an array of integers nums and a target integer target,
return the indices of the two numbers that add up to target.
Assume exactly one solution exists. You may not use the same element twice.
Before scanning the whole array — what if, for each number, you could check in O(1) whether its "complement" (target - num) has already been seen?
What data structure gives you O(1) lookup?
Solution
from typing import List
deftwoSum(nums: List[int], target: int) -> List[int]:
seen = {} # maps value → indexfor i, num inenumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i # store AFTER checking, so we don't use same index twicereturn [] # problem guarantees a solution exists
Key idea: For each number, compute complement = target - num.
If the complement is already in the hash map, we found our pair.
We store the index after the check to avoid accidentally pairing an element with itself
(e.g., twoSum([3,3], 6) — we don't want index 0 paired with index 0).
Complexity
Time: O(n) — one pass through the array. Each lookup and insert is O(1). Space: O(n) — the hash map can hold up to n entries.
Alternative Approach
Brute force: Nested loops checking all pairs — O(n²) time, O(1) space.
Fine for tiny inputs but fails at scale.
Sort + two pointers: Sort the array, then use left/right pointers.
O(n log n) time, O(1) space — but you lose the original indices, so you'd need to store them with the values.
Hash map approach is simpler and faster here.
E 02EasyArraysGreedy
Best Time to Buy and Sell Stock
Given an array prices where prices[i] is the price on day i,
find the maximum profit from one buy and one sell (buy before sell).
Return 0 if no profit is possible.
Test Cases
maxProfit([7, 1, 5, 3, 6, 4]) → 5 # buy day 2 (1), sell day 5 (6)
maxProfit([7, 6, 4, 3, 1]) → 0 # prices only fall, no profit
maxProfit([2, 4, 1]) → 2 # buy day 1 (2), sell day 2 (4)
greedy one-passtrack running minimumO(n) time O(1) space
You always want to buy at the lowest price seen so far.
At each day, ask two things: (1) is today a new minimum? (2) if I sell today, what's my profit vs the current minimum?
Can you track both of these in a single pass?
Solution
from typing import List
defmaxProfit(prices: List[int]) -> int:
min_price = float('inf') # lowest buy price seen so far
max_profit = 0for price in prices:
# Update the minimum we could have bought at
min_price = min(min_price, price)
# Check if selling today beats our best profit
max_profit = max(max_profit, price - min_price)
return max_profit
Key idea: Greedily track the lowest price seen so far.
At each step, the best profit if we sell today is price - min_price.
We never need to look back — the minimum from the past is already tracked.
Complexity
Time: O(n) — single pass through prices. Space: O(1) — just two variables.
Alternative Approach
Brute force: Try every pair (i, j) where i < j — O(n²). Too slow.
DP framing:dp[i] = max profit on day i, but the greedy one-pass is equivalent and simpler.
No need for an array.
E 03EasyStringsStack
Valid Parentheses
Given a string s containing only '(', ')', '{', '}', '[', ']',
determine if the string is valid. A string is valid if every opening bracket is closed in the correct order.
Think about what happens when you see a closing bracket like ).
You need to check whether the most recently opened bracket matches it.
Which data structure lets you access the "most recent" thing?
Solution
defisValid(s: str) -> bool:
stack = []
# Map each closing bracket to its matching opener
pairs = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in'([{':
stack.append(ch) # push opener onto stackelifnot stack or stack[-1] != pairs[ch]:
returnFalse# no matching opener, or wrong openerelse:
stack.pop() # matched — remove openerreturnlen(stack) == 0# valid only if all openers were matched
Key idea: A stack is perfect here — it naturally tracks the "most recent unmatched opener".
On a closer, we peek at the top: if it matches, pop it. Otherwise, the string is invalid.
At the end, the stack must be empty (no unmatched openers remain).
Complexity
Time: O(n) — one pass, each character is pushed/popped at most once. Space: O(n) — stack can hold up to n/2 openers in worst case e.g. "(((((".
Alternative Approach
No meaningfully better alternative. The stack solution is already optimal.
A common mistake is trying to use a counter — that fails for mixed bracket types (e.g., "([)]" would pass a counter but fails the stack check).
E 04EasyArraysStrings
Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
str.startswithprefix shrinkingedge cases: empty list, one string
Start by assuming the first string is the common prefix.
Then for each other string, shrink the prefix until it matches.
When does the prefix become empty? That's your base case.
Solution
from typing import List
deflongestCommonPrefix(strs: List[str]) -> str:
if not strs:
return""
prefix = strs[0] # optimistically start with the full first stringfor s in strs[1:]:
# Shrink prefix until s starts with itwhile not s.startswith(prefix):
prefix = prefix[:-1] # drop the last characterif not prefix:
return""return prefix
Key idea: Take the first string as your candidate prefix.
For every subsequent string, trim the candidate until it's a prefix of that string.
The while not s.startswith(prefix) loop does this trimming.
If we trim down to empty, we immediately return "".
Complexity
Time: O(S) where S = total number of characters across all strings.
In the worst case (all strings are identical), we compare every character once. Space: O(1) — prefix is just a string slice, no extra data structures.
Alternative Approach
Sort and compare endpoints: Sort the array. The common prefix of the
first and last strings (lexicographically) is the answer — they are the "most different" pair.
O(n log n) for sorting + O(m) for comparison. Clever but sorting is unnecessary overhead.
E 05EasyArraysTwo Pointers
Merge Sorted Array
Given two sorted integer arrays nums1 (size m+n, first m elements valid) and nums2 (size n),
merge nums2 into nums1 in-place so that the result is sorted.
Test Cases
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
merge(nums1, m, nums2, n) → nums1 = [1,2,2,3,5,6]
nums1 = [1], m = 1, nums2 = [], n = 0
→ nums1 = [1]
nums1 = [0], m = 0, nums2 = [1], n = 1
→ nums1 = [1]
two pointersmerge from backin-place modification
If you merge from the front, you'd overwrite elements still needed.
What if you merge from the back instead? The back of nums1 is empty space — you can safely fill it from the end without disturbing anything.
Solution
from typing import List
defmerge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# Three pointers: end of valid nums1, end of nums2, end of total array
p1, p2, p = m - 1, n - 1, m + n - 1while p1 >= 0and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1# If nums2 has leftover elements, copy them (nums1 leftovers are already in place)
nums1[:p2 + 1] = nums2[:p2 + 1]
Key idea: Merge from the back. Place the largest element at position m+n-1, then work inwards.
This avoids overwriting elements we still need. If nums2 has remaining elements when p1 runs out,
copy them — nums1 elements are already in the right place.
Complexity
Time: O(m + n) — each element is placed exactly once. Space: O(1) — done in-place, no extra arrays.
Alternative Approach
Copy and sort: Append nums2 to nums1 and call sort() — O((m+n) log(m+n)).
Simpler to write but wastes the fact that both arrays are already sorted.
The two-pointer merge is the "correct" interview answer.
E 06EasyStringsHash Map
Roman to Integer
Given a Roman numeral string s, convert it to an integer.
Roman numerals use subtraction when a smaller value appears before a larger one
(e.g., IV = 4, IX = 9, XL = 40).
Test Cases
romanToInt("III") → 3
romanToInt("IV") → 4 # I before V means subtract
romanToInt("IX") → 9
romanToInt("LVIII") → 58 # L=50, V=5, III=3
romanToInt("MCMXCIV") → 1994
hash map lookupleft-to-right scansubtraction rule
For each character, compare its value with the next character's value.
If the current value is less than the next one — subtract it.
Otherwise — add it. That single rule handles all subtraction cases.
Solution
defromanToInt(s: str) -> int:
values = {
'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000
}
result = 0for i inrange(len(s)):
curr = values[s[i]]
nxt = values[s[i + 1]] if i + 1 < len(s) else0if curr < nxt:
result -= curr # subtraction case: e.g. I before Velse:
result += curr # normal additionreturn result
Complexity
Time: O(n) where n is the length of the string. Space: O(1) — the values dict is fixed size (7 entries), not input-dependent.
Alternative Approach
Replace subtraction pairs first: Replace "IV"→"IIII", "IX"→"VIIII", etc., then sum all values.
Works but ugly and harder to extend. The comparison approach above is cleaner and general.
E 07EasyMath
Palindrome Number
Given an integer x, return True if it reads the same forwards and backwards.
Negative numbers are not palindromes.
string conversiontwo-pointer comparisonnegative edge case
Negatives are always False. For non-negatives — what's the simplest way to check if a number reads the same in both directions?
Converting to a string lets you use Python's string comparison directly.
Solution
# --- Approach 1: String reversal (simple) ---defisPalindrome(x: int) -> bool:
if x < 0:
returnFalse
s = str(x)
return s == s[::-1]
# --- Approach 2: Math reversal (no string conversion) ---defisPalindromeMath(x: int) -> bool:
if x < 0or (x % 10 == 0and x != 0):
returnFalse# trailing zero means it can't be a palindrome
reversed_half = 0while x > reversed_half:
reversed_half = reversed_half * 10 + x % 10
x //= 10# For even length: x == reversed_half. For odd: x == reversed_half // 10return x == reversed_half or x == reversed_half // 10
String approach: Convert to string, compare with its reverse using slice [::-1]. Dead simple.
Math approach: Reverse only the second half of the number and compare with the first half.
This avoids overflow (unnecessary in Python but shows deeper understanding).
Only reverse until reversed_half >= x — that's the halfway point.
Complexity
String: Time O(log x), Space O(log x) — number of digits = log₁₀(x). Math: Time O(log x), Space O(1) — no string allocation.
E 08EasyArraysTwo Pointers
Move Zeroes
Given an integer array nums, move all zeroes to the end while maintaining
the relative order of non-zero elements. Do it in-place.
two pointersin-place partitionrelative order preservation
Think of a "write pointer" that only advances when it writes a non-zero value.
Walk through the array with a read pointer. When you see a non-zero, write it at the write position.
What do you fill in at the end?
Solution
from typing import List
defmoveZeroes(nums: List[int]) -> None:
insert_pos = 0# next position to write a non-zero value# Step 1: compact all non-zero values to the frontfor num in nums:
if num != 0:
nums[insert_pos] = num
insert_pos += 1# Step 2: fill the rest with zeroeswhile insert_pos < len(nums):
nums[insert_pos] = 0
insert_pos += 1
Key idea: Two-phase approach — first compact non-zeros to the front
(preserving order), then overwrite the tail with zeros.
The insert_pos pointer acts as a partition boundary.
Complexity
Time: O(n) — two passes but both are O(n). Space: O(1) — in-place.
Alternative Approach
Swap approach: Swap each non-zero element with the element at insert_pos.
This does the same thing in one pass, but generates more swaps when there are many non-zeros close together.
The two-step approach above minimizes writes.
E 09EasyStringsHash Map
Valid Anagram
Given two strings s and t, return True if t is an anagram of s.
An anagram uses all the same characters with the same frequencies.
Two strings are anagrams if and only if they have the same character frequency map.
Python's Counter builds exactly that. What does comparing two Counters look like?
Solution
from collections import Counter
# --- Clean one-liner using Counter ---defisAnagram(s: str, t: str) -> bool:
returnCounter(s) == Counter(t)
# --- Alternative: manual frequency array (26 letters, slightly faster) ---defisAnagramManual(s: str, t: str) -> bool:
iflen(s) != len(t):
returnFalse
freq = [0] * 26for c in s:
freq[ord(c) - ord('a')] += 1for c in t:
freq[ord(c) - ord('a')] -= 1returnall(f == 0for f in freq)
Complexity
Time: O(n) — Counter builds the map in one pass per string. Space: O(1) — at most 26 unique lowercase letters in the Counter (bounded, not input-size dependent).
Alternative Approach
Sort both strings:sorted(s) == sorted(t) — clean and readable.
Time O(n log n), Space O(n) for the sorted copies. Slower, but acceptable for short strings.
For unicode/non-ASCII characters, Counter handles them naturally while the frequency array doesn't.
E 10EasyLinked Lists
Reverse Linked List
Given the head of a singly linked list, reverse the list and return the new head.
linked list traversalthree pointersin-place reversal
At each node, you need to redirect its next pointer backward.
But before you do that, you need to save what next currently points to (otherwise you lose the rest of the list).
You need three pointers: prev, curr, and next_node.
Solution
from typing import Optional
classListNode:
def__init__(self, val=0, next=None):
self.val = val
self.next = next
defreverseList(head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
next_node = curr.next # 1. save next before we overwrite it
curr.next = prev # 2. reverse the pointer
prev = curr # 3. advance prev
curr = next_node # 4. advance currreturn prev # prev is now the new head
Key idea: Three pointers march through the list.
At each step: save next, flip pointer, advance both prev and curr.
When curr is None, prev is the last node processed — the new head.
Complexity
Time: O(n) — visit each node once. Space: O(1) — only three pointer variables.
Alternative Approach
Recursive:reverseList(head.next) then make head.next.next = head and head.next = None.
Elegant but uses O(n) call stack space. Iterative approach is preferred in production.
E 11EasyLinked Lists
Merge Two Sorted Lists
Merge two sorted linked lists and return the head of the merged list.
The merged list should also be sorted.
dummy head nodetwo-pointer mergelinked list building
Use a dummy head node so you don't have to special-case the result's head.
At each step, pick the smaller of the two current nodes and attach it to the result.
After the loop, what do you do with leftover nodes in one of the lists?
Solution
defmergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0) # sentinel — avoids special-casing the head
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
# Attach the remaining non-exhausted list directly
curr.next = l1 or l2
return dummy.next
Key idea: The dummy head eliminates the need to special-case inserting the first node.
When one list is exhausted, attach the entire remaining other list in O(1) — no need to loop.
curr.next = l1 or l2 picks whichever list is non-None.
Complexity
Time: O(m + n) — each node is visited exactly once. Space: O(1) — no new nodes created, just rearranging pointers.
Alternative Approach
Recursive: If l1.val ≤ l2.val, set l1.next = mergeTwoLists(l1.next, l2) and return l1.
Elegant but O(m+n) call stack. Iterative is preferred.
E 12EasyStringsTwo Pointers
Valid Palindrome
Given a string s, determine if it is a palindrome, considering only
alphanumeric characters and ignoring case.
Test Cases
isPalindrome("A man, a plan, a canal: Panama") → True
isPalindrome("race a car") → False
isPalindrome(" ") → True # empty after filtering
First clean the string: keep only alphanumeric characters and lowercase everything.
Then check if that cleaned string equals its reverse. Or use two pointers to avoid creating a new string.
Solution
# --- Approach 1: Clean then compare (simple) ---defisPalindrome(s: str) -> bool:
cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]
# --- Approach 2: Two pointers (O(1) space) ---defisPalindromePointers(s: str) -> bool:
left, right = 0, len(s) - 1while left < right:
while left < right and not s[left].isalnum():
left += 1while left < right and not s[right].isalnum():
right -= 1if s[left].lower() != s[right].lower():
returnFalse
left += 1; right -= 1returnTrue
Complexity
Clean+compare: Time O(n), Space O(n) — new string of length up to n. Two pointers: Time O(n), Space O(1) — no new string, same time complexity but better space.
E 13EasyArraysTwo Pointers
Remove Duplicates from Sorted Array
Given a sorted integer array nums, remove duplicates in-place so each unique value appears once.
Return the count k of unique elements. The first k elements of nums should hold the result.
Use a "write" pointer starting at 1. Walk through with a "read" pointer.
When does a value deserve to be written to the write position?
(Hint: the array is already sorted, so comparing adjacent elements tells you if something is new.)
Solution
from typing import List
defremoveDuplicates(nums: List[int]) -> int:
if not nums:
return0
k = 1# first element is always unique, start write pointer at 1for i inrange(1, len(nums)):
if nums[i] != nums[i - 1]: # new unique value found
nums[k] = nums[i] # write it to the next slot
k += 1return k
Complexity
Time: O(n) — single pass through the array. Space: O(1) — in-place, no extra storage.
Alternative Approach
This exact pattern (two-pointer compaction) also solves related problems like
"Remove Duplicates II" (allow at most 2 occurrences) by checking nums[i] != nums[k-2] instead.
The pattern generalizes cleanly.
E 14EasyArraysHash Set
Contains Duplicate
Given an integer array nums, return True if any value appears at least twice.
A set automatically removes duplicates. What happens to the length of a set vs the original list if there are duplicates?
Solution
from typing import List
# --- One-liner: compare lengths ---defcontainsDuplicate(nums: List[int]) -> bool:
returnlen(nums) != len(set(nums))
# --- Early-exit variant (stops as soon as a dup is found) ---defcontainsDuplicateEarly(nums: List[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
returnTrue
seen.add(num)
returnFalse
Complexity
Time: O(n) — building a set is O(n). Space: O(n) — the set can hold up to n elements.
The early-exit variant has the same worst-case but is faster when a duplicate appears early in the list.
Alternative Approach
Sort first: Sort the array and check adjacent elements — O(n log n) time, O(1) space.
Better memory usage but slower. The set approach is the standard answer.
E 15EasyDynamic Programming
Climbing Stairs
You are climbing a staircase of n steps. Each time you can climb 1 or 2 steps.
In how many distinct ways can you reach the top?
To reach step n, you came from either step n-1 (took 1 step) or step n-2 (took 2 steps).
So ways(n) = ways(n-1) + ways(n-2).
Does this formula remind you of a famous number sequence?
Solution
defclimbStairs(n: int) -> int:
if n <= 2:
return n
# a = ways(i-2), b = ways(i-1)# This is just the Fibonacci sequence with different base cases
a, b = 1, 2for _ inrange(3, n + 1):
a, b = b, a + b # advance: new b is old a + old breturn b
Key idea: This is exactly Fibonacci: f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2).
We only need the last two values, so we use two variables instead of an array.
Complexity
Time: O(n) — one loop from 3 to n. Space: O(1) — only two variables, no array.
Alternative Approaches
DP array:dp[i] = dp[i-1] + dp[i-2] — same logic but O(n) space. Unnecessary. Memoized recursion: Top-down with @functools.lru_cache — O(n) time and space. Matrix exponentiation: O(log n) time — overkill for this problem, but impressive to mention.
E 16EasyArrays
Majority Element
Given an array nums of size n, return the majority element — the element that appears
more than n/2 times. The majority element always exists.
Boyer-Moore Votingcandidate + countO(n) time O(1) space
The easiest solution is Counter — but that's O(n) space.
The trick question: can you find the majority element in O(1) space?
Think about it this way: if you "cancel out" pairs of different elements, what's left at the end must be the majority (since it appears more than half the time).
Solution
from typing import List
# Boyer-Moore Voting Algorithm — the elegant O(1) space solutiondefmajorityElement(nums: List[int]) -> int:
count = 0
candidate = Nonefor num in nums:
if count == 0:
candidate = num # start fresh with new candidate
count += 1if num == candidate else -1return candidate # guaranteed to be the majority
Key idea (Boyer-Moore Voting): Think of each non-majority element "cancelling out" one majority element.
Since the majority appears > n/2 times, there aren't enough non-majority elements to cancel all of them.
The surviving candidate at the end must be the majority.
When count hits 0, we start fresh — the previous candidate got fully cancelled.
Complexity
Time: O(n) — single pass. Space: O(1) — just two variables. This is the optimal solution.
Alternative Approaches
Counter:Counter(nums).most_common(1)[0][0] — O(n) time, O(n) space. Clean but wastes memory. Sort: The middle element nums[n//2] after sorting is always the majority — O(n log n), O(1) space. Bit manipulation: For each bit position, count which bit value appears more — O(32n) = O(n), O(1) space.