Learn dsa, with practice after every lesson
8 lessons, about 136 minutes of reading, and 24 multiple-choice questions. Each lesson names the mistake that most often costs people the interview, because that is where the hours actually go. Part of the free coding course.
Big O, and why interviewers ask
BasicsBig O describes how the work a piece of code does grows as the input grows. O(n) means doubling the input roughly doubles the work; O(n²) means doubling it quadruples the work; O(1) means the input size does not matter at all. It is deliberately imprecise — constants and small terms are dropped — because the question it answers is what happens at scale, not how many milliseconds something takes.
Interviewers ask because it predicts a specific failure. Code that is fine on the hundred rows you tested with becomes unusable on the ten million rows in production, and the difference between a nested loop and a hash lookup is the difference between four minutes and four seconds. Being able to say 'this is O(n²) because of the inner loop, and a set makes it O(n)' is the single most useful sentence in a technical screen.
The practical skill is spotting it by reading rather than calculating. A loop inside a loop over the same data is usually O(n²). A single pass is O(n). Sorting is O(n log n) and is often the cheapest way to make a hard problem easy. A dictionary or set lookup is O(1), which is why converting a list to a set before repeated membership checks is the most common single optimisation in real code.
Syntax
# O(n^2) — for each item, scan the whole list again
def has_duplicate_slow(items):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
# 10,000 items -> ~50,000,000 comparisons
# O(n) — one pass, constant-time lookups
def has_duplicate(items):
seen = set()
for x in items:
if x in seen: # O(1), not a scan
return True
seen.add(x)
return False
# 10,000 items -> 10,000 operations. Same answer, ~5,000x less work.Key points
- A loop inside a loop over the same data is the O(n²) signature, and it is the most common performance bug in working code.
- Set and dict lookups are O(1). Converting a list to a set before repeated `in` checks is the highest-value one-line optimisation there is.
- Sorting costs O(n log n) and frequently turns a hard problem into an easy one — it is often worth paying deliberately.
Practice challenge
For each requirement, name the structure and its lookup complexity: (a) check whether an email has already registered, among 2 million, (b) serve customers strictly in arrival order, (c) undo the last action.
a) hash set - O(1)
b) queue - O(1) at the front
c) stack - O(1) at the topa) ______ O(______)
b) ______ O(______)
c) ______ O(______)Show a hint
- Scanning a list of 2 million for a membership check is the wrong answer and the common one
- Two of the three differ only in which end you take from
Check yourself
1. What does O(n²) usually look like in code?
Show answer
B. A loop nested inside another loop over the same data
2. What is the cost of a set membership check?
Show answer
B. O(1)
3. Why do interviewers ask about complexity?
Show answer
B. It predicts code that works on test data and fails at production scale
The four structures that dominate screens
Working levelThe overwhelming majority of screening questions use four structures: arrays, hash maps, strings and stacks. Trees and graphs appear at senior level and at the large product companies, but a candidate fluent in the first four clears far more first rounds than one who has read about all of them and is comfortable with none. Depth on the common ones beats breadth every time here.
Hash maps are the workhorse. The pattern that solves an enormous number of problems is: walk the data once, remember what you have seen in a dictionary, and check the dictionary rather than searching again. Two Sum, first non-repeating character, group anagrams, counting frequencies — all the same shape. If a question involves finding pairs or duplicates, reach for a map before anything else.
The second pattern worth drilling is two pointers, which applies to sorted arrays and to strings. One index at each end moving inwards, or a slow and fast pointer moving together, replaces a nested loop with a single pass. Recognising which of these two patterns a question wants — hash map or two pointers — solves most of what you will be asked in a forty-minute screen.
Syntax
# Pattern 1 — hash map: remember what you have seen
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen: # have I already seen the complement?
return [seen[target - n], i]
seen[n] = i
return []
# Pattern 2 — two pointers on sorted data: one pass instead of nested loops
def pair_sums_to(sorted_nums, target):
lo, hi = 0, len(sorted_nums) - 1
while lo < hi:
total = sorted_nums[lo] + sorted_nums[hi]
if total == target: return [lo, hi]
if total < target: lo += 1 # need bigger -> move left edge up
else: hi -= 1 # need smaller -> move right edge down
return []Key points
- Arrays, hash maps, strings and stacks cover most screening questions. Be fluent in those before touching trees and graphs.
- The hash-map pattern is: one pass, remember what you have seen, check the map instead of searching again.
- Two pointers turns a nested loop into a single pass on sorted data. Recognising when a problem is sorted, or can be, is half the trick.
Practice challenge
Given a list of numbers, find whether any two of them add to a target. The obvious solution compares every pair. State its complexity, then describe the O(n) approach and what it trades away.
Naive: O(n^2)
Better: walk once, keeping a hash set of values seen; for each x check whether target - x is already in the set - O(n)
Trade-off: O(n) extra memory for the setNaive: O(______)
Better approach: ______
Trade-off: ______Show a hint
- The trick is asking what you would need to have already seen, rather than comparing forwards
- Almost every drop from n^2 to n in interviews is bought with memory
Check yourself
1. Which four structures dominate screening questions?
Show answer
B. Arrays, hash maps, strings, stacks
2. What is the core hash-map pattern?
Show answer
B. One pass, remember what you have seen, check the map instead of searching
3. When does the two-pointer pattern apply?
Show answer
B. Sorted arrays and strings, replacing a nested loop with one pass
Solving a problem out loud
AdvancedIn a live interview the code is roughly half of what is being assessed. The other half is whether the interviewer can follow your reasoning, because that is a proxy for what working with you would be like. Silent correctness scores worse than audible thinking, and candidates who solve the problem without narrating frequently lose to candidates who narrate a slightly worse solution.
The sequence that works is the same every time. Restate the problem in your own words so a misunderstanding surfaces in the first minute rather than the fifteenth. Ask about the edge cases — empty input, duplicates, negative numbers, size of the data — because those questions demonstrate exactly the caution the role needs. State a brute-force approach and its complexity, then say why you are going to improve it. Only then write code.
When you get stuck, say what you are stuck on. An interviewer cannot help someone staring silently at a screen, and they are usually willing to nudge a candidate who says 'I want a way to look up the complement in constant time, so I think I need a map here — let me try that'. Being stuck is expected; being opaque about it is the thing that ends the interview.
Syntax
# The narration, in the order it should happen:
#
# 1. RESTATE "So given a list and a target, I return the indices of the two
# numbers that add to it. Exactly one solution, and I can't reuse
# the same element — have I got that right?"
#
# 2. EDGES "Can the list be empty? Are there duplicates? Negatives?
# Roughly how large — hundreds or millions?"
#
# 3. BRUTE "The obvious approach is every pair, which is O(n^2).
# Correct, but it'll be slow if the list is large."
#
# 4. IMPROVE "If I could check for the complement in constant time I'd only
# need one pass. A dictionary gives me that — O(n) time, O(n) space."
#
# 5. CODE ...write it, still talking...
#
# 6. TEST "Let me walk [2,7,11,15], target 9. i=0, need 7, not seen yet,
# store 2. i=1, need 2 — it's there, return [0,1]. And empty
# input returns [] rather than throwing."Key points
- Restate the problem first. A misunderstanding caught in minute one costs nothing; the same one caught in minute fifteen costs the interview.
- Say the brute-force approach and its complexity before optimising. It shows you can reach a correct answer, then improve it deliberately.
- Walk your finished code through a concrete example out loud. It catches off-by-one errors and demonstrates the habit of verifying rather than assuming.
Practice challenge
You have sorted the data (n log n) and then loop through it once (n). State the overall complexity and why, then say why binary search on the sorted data is O(log n) and what it required first.
Overall: O(n log n) - you keep the dominant term, and n log n grows faster than n
Binary search: each comparison discards half of what is left, so 1 million items take about 20 steps
Required first: the data must already be sorted, and that sort costs n log nOverall: O(______) because ______
Binary search: O(log n) because ______
Required first: ______Show a hint
- Big-O keeps only the fastest-growing term
- The sorting cost is why binary search is not free when you only search once
Check yourself
1. What should you do before writing any code?
Show answer
B. Restate the problem and ask about edge cases
2. Why state the brute-force approach first?
Show answer
B. It shows you can reach a correct answer, then improve it deliberately
3. What should you do when stuck?
Show answer
B. Say exactly what you are stuck on
The live coding interview
Job-readyKnowing the algorithm and passing the interview are different skills, and the second one is largely about being audible. An interviewer cannot score silent thinking. Candidates who solve the problem without narrating routinely lose to candidates who solve less of it while explaining where they are.
The sequence that works: restate the problem in your own words and confirm it, ask about the inputs that break things — empty, one element, duplicates, negatives, size — then say the brute-force approach out loud and give its complexity before writing anything. That last step is not wasted time. It banks a working answer, and it makes the optimisation a visible improvement rather than a lucky guess.
When you are stuck, say what you are stuck on. "I want to avoid the nested loop and I am trying to work out what to store as I go" invites a hint and is scored as collaboration. Silence for four minutes is scored as being stuck. And when the code is written, walk one small example through it by hand — that is where you find the off-by-one yourself rather than being told about it.
Syntax
// Say this out loud, in this order, before optimising:
//
// 1. "So: given an array and a target, return the two indices that
// sum to it. Should I assume exactly one answer? Can values repeat?"
// 2. "Edge cases: empty array, one element, duplicates, negatives."
// 3. "Brute force is every pair — O(n^2) time, O(1) space. Let me
// write that first so we have something that works."
// 4. "To do better I need to know what I've already seen, so a hash
// map of value -> index. One pass, O(n) time, O(n) space."
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
return [];
}
// 5. Walk it by hand: [2,7,11], target 9
// i=0 need 7 not seen -> store 2:0
// i=1 need 2 IS seen -> return [0,1] correctKey points
- State the brute force and its complexity before writing anything. It banks a correct answer and frames the optimisation as deliberate.
- Narrate while you are stuck. Naming the obstacle invites a hint; silence reads as having run out of ideas.
- Trace one small input by hand at the end. You will find your own off-by-one, which scores far better than the interviewer finding it.
Practice challenge
You are given: return the first non-repeating character in a string. Write what you would SAY, in order, before writing any code - the restatement, the edge cases, the brute force with its complexity, and the improvement with its trade-off.
Restate: return the first character that appears exactly once; if there is none, return null. Confirm: case-sensitive? Unicode or ASCII?
Edge cases: empty string, single character, all characters repeating, all unique.
Brute force: for each character, scan the rest of the string counting occurrences - O(n^2) time, O(1) space.
Better: one pass to count occurrences into a map, a second pass to find the first with count 1 - O(n) time, O(k) space where k is the alphabet size. Trade: extra memory for the counts.Restate: ______
Edge cases: ______
Brute force: ______ O(______)
Better: ______ O(______), trade: ______Show a hint
- Say the brute force out loud even though you can see the better answer - it banks a correct solution
- Every drop from n^2 to n here is paid for in memory; name the price
Check yourself
1. Why state the brute-force solution first?
Show answer
B. It banks a working answer and makes the optimisation deliberate
2. You are stuck for two minutes. Best move?
Show answer
B. Say what specifically you are stuck on
3. After writing the code you should:
Show answer
B. Trace a small example by hand
Arrays and strings: two pointers and the sliding window
BasicsA large share of screening questions are an array or a string with a nested loop as the obvious answer, and a linear answer available to anyone who recognises the shape. The first shape is two pointers. When the input is sorted, or when you are working inward from both ends, you place one index at each end and move whichever one the comparison tells you to. Checking a palindrome, or finding a pair summing to a target in a sorted array, both drop from quadratic to linear this way — and the reason is worth saying out loud in an interview, because moving a pointer eliminates a whole set of possibilities in one step rather than testing them.
The second shape is the sliding window, which applies to questions about a contiguous run: the longest substring without repeats, the maximum sum of any k consecutive elements, the smallest window containing a set of characters. Instead of recomputing each candidate window from scratch, you extend the right edge to include a new element and advance the left edge when the window becomes invalid, updating a running total or a count as you go. Each element is added once and removed once, which is what makes it linear.
Recognition is the actual skill, and there is a reliable tell. If a brute-force solution recomputes something for overlapping ranges, a window can usually carry that computation forward instead. If the array is sorted and you are searching for a pair or a triple, two pointers usually replaces the inner loop. And a third pattern is worth having ready: a prefix-sum array, built once, answers any range-sum query in constant time — which turns a large class of 'sum between i and j, many times' questions into a preprocessing step and a subtraction.
Syntax
# TWO POINTERS -- sorted input, work inward
def pair_sum(nums, target): # nums is sorted
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target: return (lo, hi)
if s < target: lo += 1 # need more; only lo can help
else: hi -= 1 # need less; only hi can help
return None
# O(n) instead of O(n^2). Each move eliminates a whole set of pairs.
# SLIDING WINDOW -- longest substring with no repeated character
def longest_unique(s):
seen, left, best = {}, 0, 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1 # shrink past the duplicate
seen[ch] = right
best = max(best, right - left + 1)
return best
# each character enters once and leaves once -> O(n)
# PREFIX SUMS -- build once, answer any range in O(1)
def build_prefix(nums):
out = [0]
for n in nums: out.append(out[-1] + n)
return out
def range_sum(prefix, i, j): # sum of nums[i..j] inclusive
return prefix[j + 1] - prefix[i]
# TELLS:
# recomputing over overlapping ranges -> sliding window
# sorted + looking for a pair/triple -> two pointers
# many range-sum queries -> prefix sumsKey points
- Two pointers works when the input is sorted or you can work inward from both ends. Each move eliminates a whole set of candidates rather than testing one.
- A sliding window turns overlapping recomputation into a running update. Every element is added once and removed once, so the whole pass is linear.
- A prefix-sum array costs one pass to build and answers any range-sum query with a single subtraction, which collapses a large family of repeated-query problems.
Practice challenge
For each problem name the pattern (two pointers, sliding window, prefix sums, or none) and state the complexity you would achieve: (a) pair summing to a target in a sorted array, (b) longest substring with no repeated character, (c) thousands of 'sum from index i to j' queries on a fixed array, (d) is this string a palindrome.
(a) Two pointers / O(n) - sorted input means a comparison tells you which pointer to move
(b) Sliding window / O(n) - each character enters and leaves the window once
(c) Prefix sums / O(n) once to build, then O(1) per query
(d) Two pointers / O(n) - one index at each end, working inward(a) ______ / ______
(b) ______ / ______
(c) ______ / ______
(d) ______ / ______Show a hint
- Sorted input plus a search for a pair is the strongest tell
- Overlapping recomputation over ranges points to one specific pattern
Check yourself
1. What does the two-pointer technique require of the input for pair-sum?
Show answer
B. It must be sorted, so a comparison says which pointer to move
2. Why is a sliding window linear?
Show answer
B. Each element is added once and removed once across the whole pass
3. You must answer thousands of 'sum from i to j' queries. Best approach?
Show answer
B. Build a prefix-sum array once, then subtract
The hash map, and turning O(n²) into O(n)
Working levelThe hash map is the single highest-return structure in interviews, because so many questions reduce to 'have I seen this before, and where'. Its power is constant-time average lookup by key, and the standard move is to trade memory for time: instead of scanning the array again to check whether a complement exists, you store what you have already seen and check membership in one step. That is the entire trick behind the classic two-sum on unsorted input, and it generalises far beyond it.
Three patterns cover most uses. Counting, where the map holds value to frequency, which answers 'most common element', 'is this an anagram', 'first non-repeating character'. Seen-before, where the map holds value to index, which answers two-sum and 'first duplicate'. And grouping, where the map holds a derived key to a list, which answers 'group these words into anagrams' by keying on the sorted letters. Recognising which of the three a question wants is usually the whole solution.
Two caveats belong in your answer when you use one. Constant time is average, not worst case: with adversarial keys or a poor hash everything collides into one bucket and lookups degrade to linear, which is why languages randomise hashing. And keys must be hashable and compared by value — in Python a list cannot be a key while a tuple can, and in Java an object used as a key must implement equals and hashCode consistently or two equal objects land in different buckets and the map appears to lose entries.
Syntax
# SEEN-BEFORE: two-sum on UNSORTED input, one pass
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen: # complement already passed?
return (seen[target - n], i)
seen[n] = i
return None
# O(n) time, O(n) space -- memory traded for time
# COUNTING: frequency map
from collections import Counter
def first_non_repeating(s):
counts = Counter(s)
for ch in s:
if counts[ch] == 1: return ch
return None
def is_anagram(a, b):
return Counter(a) == Counter(b)
# GROUPING: derived key -> list
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w) # sorted letters as key
return list(groups.values())
# CAVEATS TO SAY OUT LOUD
# O(1) is AVERAGE. Adversarial keys collide -> O(n) lookups.
# Keys must be hashable:
# d[[1,2]] = x # TypeError: list is unhashable
# d[(1,2)] = x # fine: tuples are immutable
# Java: equals() and hashCode() must agree, or equal objects
# land in different buckets and entries appear to vanish.Key points
- The core trade is memory for time: store what you have seen so a second scan becomes a single constant-time lookup.
- Three patterns cover most questions — counting frequencies, remembering what was seen and where, and grouping by a derived key.
- Constant time is average, not guaranteed. Mention collisions, and mention that keys must be immutable and that equals and hashCode must agree in Java.
Practice challenge
Write two-sum for an unsorted array using a hash map, in one pass. State the time and space complexity, say what is being traded, and give the caveat about O(1) that you should mention in an interview.
def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
if target - n in seen:
return (seen[target - n], i)
seen[n] = i
return None
Time: O(n) Space: O(n)
Trade: memory for time - storing what you have seen replaces a second scan
Caveat: hash lookup is O(1) on average, not worst case; with colliding keys it degrades toward O(n), which is why languages randomise hashingdef two_sum(nums, target):
______
Time: ______ Space: ______
Trade: ______
Caveat: ______Show a hint
- Check for the complement before inserting the current value, or a single element can match itself
- Say the average-versus-worst-case point unprompted
Check yourself
1. What does the hash-map solution to two-sum trade?
Show answer
B. Memory for time — one pass with stored lookups instead of a nested scan
2. Why can a Python list not be a dictionary key?
Show answer
B. Keys must be hashable, and lists are mutable
3. You mutate an object already used as a key. What happens?
Show answer
B. The entry becomes unfindable — its hash no longer matches its bucket
Recursion, trees and traversal
AdvancedRecursion is the natural way to describe anything defined in terms of smaller copies of itself, and a tree is exactly that: a node with subtrees that are themselves trees. Every recursive function needs two parts and interviews test whether you write both. A base case that returns without recursing — for a tree, almost always the empty node — and a recursive case that reduces the problem and combines the results. Missing base case means a stack overflow; a recursive case that does not shrink the input means the same.
For trees, three depth-first orders differ only in when you handle the current node relative to its children, and each is the right answer to different questions. In-order visits left, node, right, and on a binary search tree that yields the values in sorted order, which is why 'validate a BST' is usually an in-order walk checking that each value exceeds the last. Pre-order handles the node first and is what you want for copying or serialising a tree. Post-order handles children first and is what you need whenever a node's answer depends on its subtrees — computing height, summing a subtree, deleting.
Breadth-first is the fourth and it is not recursive: it uses a queue and visits level by level, which is what you want for 'the shortest path in an unweighted graph' or anything phrased in terms of levels. The complexity conversation matters as much as the code — visiting every node once is linear in the number of nodes, but the space is the depth of the recursion, which is the height of the tree. That is logarithmic when balanced and linear when the tree is a degenerate chain, and saying so unprompted is exactly the reasoning interviewers are listening for.
Syntax
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
# Every recursion: a base case, and a case that SHRINKS.
def height(node):
if node is None: return 0 # base
return 1 + max(height(node.left), height(node.right))
# IN-ORDER: left, node, right -> sorted output on a BST
def in_order(node, out):
if node is None: return
in_order(node.left, out)
out.append(node.val)
in_order(node.right, out)
# PRE-ORDER: node first -> copying, serialising
# POST-ORDER: children first -> when the node's answer
# depends on its subtrees (height, subtree sums, delete)
# validate a BST: in-order must be strictly increasing
def is_bst(root):
prev = None
stack, node = [], root
while stack or node:
while node: stack.append(node); node = node.left
node = stack.pop()
if prev is not None and node.val <= prev: return False
prev, node = node.val, node.right
return True
# BREADTH-FIRST: a queue, level by level, NOT recursive
from collections import deque
def level_order(root):
if not root: return []
out, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # one full level
n = q.popleft(); level.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
out.append(level)
return out
# Time O(n): every node once.
# Space O(h): h = height. log n balanced, n if it is a chain.Key points
- Every recursion needs a base case and a recursive case that provably shrinks the input. For trees the base case is the empty node.
- Pick the traversal from the question: in-order gives sorted output on a BST, pre-order suits copying and serialising, post-order is required when a node depends on its subtrees.
- Recursive space is the height of the tree, not the node count — log n balanced, n for a degenerate chain. Say this before being asked.
Practice challenge
Name the traversal for each and give the space complexity of a recursive traversal in the best and worst case: (a) output a BST's values in sorted order, (b) compute each node's height, (c) serialise a tree so it can be rebuilt, (d) find the shortest path in an unweighted graph.
(a) In-order - left, node, right yields sorted values on a BST
(b) Post-order - a node's height depends on its children, so children must be handled first
(c) Pre-order - handle the node before its children
(d) Breadth-first with a queue - not recursive, visits level by level
Space: O(log n) when balanced, O(n) worst case when the tree degenerates into a chain(a) ______
(b) ______
(c) ______
(d) ______
Space: best ______ worst ______Show a hint
- Whether the node is handled before or after its children is the whole difference
- Recursive space is the height, not the node count
Check yourself
1. Which traversal yields sorted values from a binary search tree?
Show answer
B. In-order
2. You need each node's height, which depends on its children. Which order?
Show answer
B. Post-order
3. What is the space complexity of a recursive traversal?
Show answer
B. O(h), the height — log n balanced, n if degenerate
Sorting, binary search, and using the order you have
Job-readyYou will rarely be asked to implement a sort, and you will constantly be asked to decide whether to sort. The trade is explicit: sorting costs n log n once, and afterwards binary search answers any membership or boundary question in log n, and duplicates, medians and ranges all become easy. For a single lookup, sorting first is a waste; for many lookups, or for a question about order at all, sorting first is usually the whole solution. Being able to say which case you are in, and why, is the answer the interviewer wants.
Binary search itself is short and famously easy to get subtly wrong. The invariant is that the answer, if it exists, is always inside the current range, and every iteration must strictly shrink that range or it loops forever. The variants matter more than the basic form: finding the first element not less than a target — lower bound — is what you actually need for 'insert position', 'count occurrences' and 'first date after X', and it is far more commonly useful than exact-match search.
The idea that pays off most is that binary search is not limited to arrays. Any time the answer is a number, and you can cheaply test whether a candidate is feasible, and feasibility is monotonic — true for everything above some threshold and false below it — you can binary search the answer itself. 'What is the smallest ship capacity that delivers all packages in D days' is not obviously a search problem, but capacity is monotonic, so you search the range of capacities and test each one. Recognising monotonicity is the transferable skill; the implementation is six lines.
Syntax
# SORT ONCE, THEN THE QUESTIONS BECOME EASY
# one lookup -> do NOT sort; a linear scan is O(n)
# many lookups -> sort n log n, then log n each
# median/duplicates/
# ranges/top-k -> sorting usually IS the answer
# BINARY SEARCH: the range must strictly shrink every iteration
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target: return mid
if a[mid] < target: lo = mid + 1 # +1 / -1 or it loops
else: hi = mid - 1
return -1
# LOWER BOUND -- first index with a[i] >= target.
# More useful than exact match: insert position, counting
# occurrences, "first date after X".
def lower_bound(a, target):
lo, hi = 0, len(a) # note: hi = len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target: lo = mid + 1
else: hi = mid
return lo
count = lower_bound(a, x + 1) - lower_bound(a, x) # occurrences of x
# BINARY SEARCH THE ANSWER -- when feasibility is MONOTONIC
# "smallest ship capacity to deliver all packages within D days"
def min_capacity(weights, days):
def feasible(cap):
d, cur = 1, 0
for w in weights:
if cur + w > cap: d += 1; cur = 0
cur += w
return d <= days
lo, hi = max(weights), sum(weights) # bounds of the answer
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid): hi = mid # try smaller
else: lo = mid + 1
return lo
# Sorting objects: sort by a key, and say whether ties must
# keep their original order (stability) -- it is often required.Key points
- Sorting costs n log n once and makes membership, ranges, medians and duplicates cheap afterwards. For a single lookup it is wasted; for many it is the solution.
- Lower bound — the first element not less than the target — answers insert position, occurrence counts and 'first after X', and comes up more than exact-match search.
- When the answer is a number and feasibility is monotonic, binary search the answer itself. Spotting monotonicity is the transferable skill.
Practice challenge
This loop hangs: while lo < hi: mid = (lo + hi) // 2; if a[mid] < target: lo = mid; else: hi = mid. Explain exactly when it hangs, fix it, and then say when it is worth sorting an array first versus scanning it once.
It hangs when the range narrows to two elements: mid = (lo + hi) // 2 equals lo, and lo = mid leaves the range unchanged, so it loops forever
Fix: lo = mid + 1 in that branch - every iteration must strictly shrink the range
Sort first when: you will do many lookups, or the question is about order (median, duplicates, ranges, top-k) - n log n once, then log n per query
Do not sort when: it is a single lookup - one linear scan is O(n), cheaper than sortingIt hangs when: ______
Fix: ______
Sort first when: ______
Do not sort when: ______Show a hint
- Try it by hand with exactly two elements remaining
- The invariant is that the range must strictly shrink
Check yourself
1. You need one membership check on an unsorted array of a million items. Sort first?
Show answer
B. No — a single linear scan is O(n), cheaper than sorting
2. What does lower_bound return?
Show answer
B. The first index whose value is >= target
3. When can you binary search the answer rather than an array?
Show answer
B. When feasibility is monotonic in the candidate value
Common questions
Do I need any background to start DSA?
No. This track begins at its own beginning and assumes nothing, and the first lesson explains what the thing is before showing you any syntax.
How long does the DSA track take?
About 136 minutes of reading across 8 lessons, plus the practice challenges and 24 multiple-choice questions, which is where the time actually goes.
Is it free?
Yes, and there is no account. Everything runs in your browser.
More: all 15 tracks · what employers actually ask for · the full syllabus