Skip to content
Rungwise

Visualize DSA

Each picture runs the code beside it, one step at a time. Change the input under it and watch again. All visualizers.

New to this? Start with Binary search, then Two pointers.

Section titled “Binary search”

Check the middle of a sorted list. If it’s too small, the target can only be to the right; if too big, only to the left. Each check throws away half, so 1,000 numbers take about 10 checks. The lesson: My binary search says 0 isn’t in [4, 5, 6, 7, 0, 1, 2].

Binary search
  1. 30
  2. 81
  3. 122
  4. 193
  5. 254
  6. 315
  7. 406

Step 1 of 5. lo and hi start at both ends: if 31 is here, it lies between them.

def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Try your own input
Section titled “Do it yourself: binary search”

Now you run it. Click the number binary search checks, then say which half to keep. A wrong move says why. “Show me the next move” plays it for you, and a new puzzle gives you another go.

Find 50. Click the number binary search checks next (the middle of lo..hi), or say it isn’t there.

lo = 0 · hi = 6

Wrong moves: 0

A turned list

Section titled “A turned list”

A sorted list that was turned, like 4 5 6 7 0 1 2, isn’t sorted. But cut it at mid, and one half always is. Check that half’s ends: if the target is between them, keep that half; if not, keep the other. Try your own turned list, like 30 40 10 20. The lesson: My binary search says 0 isn’t in [4, 5, 6, 7, 0, 1, 2].

Binary search on a turned list
  1. 40
  2. 51
  3. 62
  4. 73
  5. 84
  6. 95
  7. 06
  8. 17
  9. 28

Work so far

target1
checks so far0

Step 1 of 9. lo and hi start at both ends. If 1 is in the list, it’s between them.

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:  # the left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # the right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Try your own input

Two pointers

Section titled “Two pointers”

Sort the numbers, then put one pointer at each end. If the pair’s sum is too small, move the left pointer right; if too big, move the right one left. The lesson: Two Sum.

Two pointers on the sorted values
  1. 70was 2
  2. 121was 0
  3. 152was 3
  4. 353was 1
  5. 444was 4

Step 1 of 10. Sort the numbers, keeping each one's original index: 7, 12, 15, 35, 44.

def two_sum(nums: list[int], target: int) -> list[int]:
    pairs = sorted((value, i) for i, value in enumerate(nums))
    lo, hi = 0, len(pairs) - 1
    while lo < hi:
        total = pairs[lo][0] + pairs[hi][0]
        if total == target:
            return sorted([pairs[lo][1], pairs[hi][1]])
        if total < target:
            lo += 1
        else:
            hi -= 1
    return []

Try your own input

Most water

Section titled “Most water”

Two walls hold water up to the shorter one. Start with the walls at both ends, the widest tank. Each step works out the water, then moves the shorter wall in: every tank it could still make is narrower and no taller. So 9 walls take 8 steps, not 36 pairs. The lesson: My tank finder says 40, but two walls hold 49.

Two walls walking in
  1. 10
  2. 81
  3. 62
  4. 23
  5. 54
  6. 45
  7. 86
  8. 37
  9. 78

Work so far

tank now: shorter × widthnone yet
best so far0
tanks checked0

Step 1 of 18. Start with the widest tank: the walls at both ends, lo = 0 and hi = 8. The water rises to the shorter wall.

def most_water(heights: list[int]) -> int:
    lo, hi = 0, len(heights) - 1  # the widest tank
    best = 0
    while lo < hi:
        water = min(heights[lo], heights[hi]) * (hi - lo)
        best = max(best, water)
        if heights[lo] < heights[hi]:
            lo += 1  # no tank with the shorter wall further in holds more
        else:
            hi -= 1
    return best

Try your own input

Hash map lookup

Section titled “Hash map lookup”

For each number, ask a dict whether its partner was seen before, then remember the number. Each question takes about one step. The lesson: Two Sum.

One pass with a hash map
  1. 120
  2. 351
  3. 72
  4. 153
  5. 444

seen (value → index)

empty

Step 1 of 12. Start with an empty map. We want two numbers that add up to 50.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # value -> index
    for i, num in enumerate(nums):
        partner = target - num
        if partner in seen:
            return [seen[partner], i]
        seen[num] = i
    return []

Try your own input

Sliding window

Section titled “Sliding window”

Find the biggest sum of k numbers in a row. Instead of adding up every window again, slide it: add the number coming in and drop the one going out. The lesson: My no-repeat finder says 2, but “vdf” has 3, where this is the first practice problem.

Biggest sum of k numbers in a row
  1. 40
  2. 21
  3. 72
  4. 13
  5. 84
  6. 35

Running totals

window13
best13

Step 1 of 5. Add up the first 3: window = 4 + 2 + 7 = 13. That is the best so far. Question: The window slides one step right: it adds 1 and drops 4. It is 13 now. What will it be?

What happens next? The window slides one step right: it adds 1 and drops 4. It is 13 now. What will it be?

def max_window_sum(nums: list[int], k: int) -> int:
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best

Try your own input

No repeats

Section titled “No repeats”

Find the longest stretch with no character twice. The window grows one character at a time. When the next one is in it already, characters leave from the left, up to the earlier copy. Each character joins once and leaves at most once, so it’s O(n). The lesson: My no-repeat finder says 2, but “vdf” has 3.

A window that grows and shrinks
  1. d0
  2. v1
  3. d2
  4. f3
  5. x4
  6. f5
  7. g6
  8. h7
  9. i8

Work so far

window''
longest so far0

Step 1 of 15. The window starts empty, at lo = 0. hi reads the characters one by one, and each joins the window.

def longest_unique(s: str) -> int:
    seen = set()  # the characters in s[lo:hi + 1]
    best = lo = 0
    for hi, c in enumerate(s):
        while c in seen:  # a repeat: drop from the left
            seen.remove(s[lo])
            lo += 1
        seen.add(c)
        best = max(best, hi - lo + 1)
    return best

Try your own input

Selection sort

Section titled “Selection sort”

Find the smallest score and swap it to the front, then find the smallest of the rest, and so on. Each pass reads all of the rest, so n scores take n(n − 1)/2 comparisons, even when they’re already in order. The lesson: My sort is right, but 50,000 scores take half a minute.

Selection sort
  1. 50
  2. 21
  3. 42
  4. 63
  5. 14
  6. 35

Work so far

smallest so farnone yet
comparisons0

Step 1 of 28. Find the smallest score, and swap it to the front. Then find the smallest of the rest, and so on. Question: With 6 scores, how many comparisons will it make?

What happens next? With 6 scores, how many comparisons will it make?

def sort_scores(scores: list[int]) -> list[int]:
    for i in range(len(scores)):
        smallest = i
        for j in range(i + 1, len(scores)):
            if scores[j] < scores[smallest]:
                smallest = j
        scores[i], scores[smallest] = scores[smallest], scores[i]
    return scores

Try your own input

Insertion sort

Section titled “Insertion sort”

Like sorting cards in your hand: take the next number and move it left past every bigger one. It’s slow on big lists (O(n²)), but fast on lists that are nearly sorted.

Insertion sort
  1. 50sorted
  2. 21
  3. 42
  4. 63
  5. 14
  6. 35

Step 1 of 21. One number on its own is already sorted. Each next number moves left until it fits.

def insertion_sort(nums: list[int]) -> list[int]:
    for i in range(1, len(nums)):
        j = i
        while j > 0 and nums[j - 1] > nums[j]:
            nums[j - 1], nums[j] = nums[j], nums[j - 1]
            j -= 1
    return nums

Try your own input

Do it yourself: insertion sort

Section titled “Do it yourself: insertion sort”

Now you sort. The numbers marked sorted are in order, and the highlighted one moves left through them until it fits. Click the number it swaps with, or say it fits.

Fit 3 into the numbers marked sorted: click the number it swaps with, or say it fits.

Wrong moves: 0

Merge sort

Section titled “Merge sort”

Split the list in half, sort each half with a call, and merge the two sorted halves by taking the smaller front each time. Each call is drawn under the call that made it, with the list it got and the sorted list it returned. About log₂ n rows, and each row’s merges read every score once: n log n comparisons.

Merge sort

Calls so far, each under the call that made it:

  • sort_scores([5, 2, 4, 6, 1, 3]): running now

Work so far

calls made1
comparisons so far0
  • Running now
  • Waiting for a call it made
  • Done: shows what it returned

Step 1 of 22. sort_scores([5, 2, 4, 6, 1, 3]) splits at index 3: [5, 2, 4] and [6, 1, 3]. It sorts the left half with a call, and waits. Question: With 6 scores, how many rows will the tree of calls have?

What happens next? With 6 scores, how many rows will the tree of calls have?

def sort_scores(scores: list[int]) -> list[int]:
    if len(scores) <= 1:
        return scores
    middle = len(scores) // 2
    left = sort_scores(scores[:middle])
    right = sort_scores(scores[middle:])
    return merge(left, right)
 
def merge(left: list[int], right: list[int]) -> list[int]:
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps equal scores in their order
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

Try your own input
Section titled “Breadth-first search”

Find the fewest steps from S to G in a maze. Keep a queue: take the cell that has waited longest, and add its open neighbors to the back. Cells are reached in order of steps, first all those 1 step away, then 2, and so on. So the first time BFS reaches G, it has found the shortest path.

Shortest path in a maze
The maze. Numbers are steps from S.
col 0col 1col 2col 3col 4
row 0S, in the queuewall
row 1wall
row 2wallG
row 3wall

Queue, front first

  1. row 0, col 0

Step 1 of 15. Start at S (row 0, col 0), 0 steps away. The queue holds just S.

from collections import deque
 
MOVES = ((-1, 0), (0, 1), (1, 0), (0, -1))  # up, right, down, left
 
def shortest_path(grid: list[str]) -> int:
    rows, cols = len(grid), len(grid[0])
    top = next(i for i, line in enumerate(grid) if "S" in line)
    start = (top, grid[top].index("S"))
    dist = {start: 0}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if grid[r][c] == "G":
            return dist[(r, c)]
        for dr, dc in MOVES:
            nr, nc = r + dr, c + dc
            inside = 0 <= nr < rows and 0 <= nc < cols
            free = inside and grid[nr][nc] != "#"
            if free and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                queue.append((nr, nc))
    return -1

Try your own input
Section titled “Do it yourself: breadth-first search”

Now you run it. Click the cell at the front of the queue to take it. Then click each open neighbor it hasn’t reached yet: each one is one more step from S and joins the back of the queue.

Take the next cell out of the queue: click it in the maze.

Queue, front first: row 0, col 1

Wrong moves: 0

Counting the work

Section titled “Counting the work”

Two ways to check a list of ids for a repeat, each with a count of its work beside it. Comparing every pair takes 10 pair checks for 5 different ids, and about four times as many each time the ids double. A set of the ids seen so far takes one look for each id. The lesson: My code passed every test, then timed out on the big one.

Check every pair
  1. 410
  2. 171
  3. 82
  4. 333
  5. 254

Work so far

pair checks0

Step 1 of 12. Compare every pair of the 5 ids, looking for two the same. Question: With 5 ids, how many pair checks can it take, at most?

What happens next? With 5 ids, how many pair checks can it take, at most?

def has_duplicate(ids: list[int]) -> bool:
    # Compare every pair once: ids[i] with each id after it.
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                return True
    return False

Try your own input
A set of the ids seen so far
  1. 410
  2. 171
  3. 82
  4. 173
  5. 254

Work so far

looks in seen0
adds to seen0

Step 1 of 9. Start with an empty set, seen. Question: With 5 ids, how many looks in seen can it take, at most?

What happens next? With 5 ids, how many looks in seen can it take, at most?

def has_duplicate(ids: list[int]) -> bool:
    seen: set[int] = set()
    for x in ids:
        if x in seen:  # one look in the set, however big it is
            return True
        seen.add(x)
    return False

Try your own input

Reversing a list

Section titled “Reversing a list”

Two ways to reverse a list of characters, each with a count of its work beside it. Putting each character in at the front of a new list moves every character already there, so 5 characters take 10 moves. Swapping the two ends and moving in takes 2 swaps for 5 characters, with no second list. The lesson: I reversed the list, but the caller’s list didn’t change.

Put each character at the front
  1. 0
  2. 1
  3. 2
  4. 3
  5. 4

Work so far

characters moved0

Step 1 of 7. Start with an empty list, out. Each of the 5 characters goes in at its front. Question: With 5 characters, how many characters will the inserts move, in all?

What happens next? With 5 characters, how many characters will the inserts move, in all?

def reverse_chars(chars: list[str]) -> None:
    out: list[str] = []
    for c in chars:
        out.insert(0, c)  # all of out moves one place right
    chars[:] = out  # copy back into the caller's list

Try your own input
Swap from both ends
  1. h0
  2. e1
  3. l2
  4. l3
  5. o4

Work so far

swaps0

Step 1 of 7. left starts at the first character, and right at the last. Question: With 5 characters, how many swaps will it make?

What happens next? With 5 characters, how many swaps will it make?

def reverse_chars(chars: list[str]) -> None:
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1

Try your own input

Anagram check

Section titled “Anagram check”

Two ways to check that two words use the same letters, the same number of times. Counting each letter with count() reads both words again for every letter: 72 letters read for two words of 6. A dict of counts takes one step per letter, adding for the first word and taking away for the second. The lesson: My anagram check says aab and abb match.

Count each letter by reading both words
  1. l0
  2. i1
  3. s2
  4. t3
  5. e4
  6. n5

Work so far

letters read0

Step 1 of 8. Both words have 6 letters. Now count each letter of word a, in both words. Question: With 6 letters in each word, how many letters can the counts read, at most?

What happens next? With 6 letters in each word, how many letters can the counts read, at most?

def is_anagram(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    # Each count() reads the whole word, once for every letter of a.
    return all(a.count(c) == b.count(c) for c in a)

Try your own input
One dict of counts
  1. a0
  2. a1
  3. b2

counts

empty

Step 1 of 8. Start with an empty dict, counts: letter → how many. Question: With 3 letters in each word, about how many dict steps will it take, at most?

What happens next? With 3 letters in each word, about how many dict steps will it take, at most?

def is_anagram(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    counts: dict[str, int] = {}
    for c in a:
        counts[c] = counts.get(c, 0) + 1
    for c in b:
        counts[c] = counts.get(c, 0) - 1
        if counts[c] < 0:  # b has more of c than a has
            return False
    return True

Try your own input

Call trees

Section titled “Call trees”

Three ways to work out 2 to the power n, each call drawn under the call that made it. Going down by 1 makes a tall line of calls, all in progress at once: Python stops past about 1,000. Halving n keeps the tree short, but making the same call twice doubles every row. Making it once leaves a short line: 4 calls for n = 6. The lesson: My power function crashes when n is 5,000.

Call it with n − 1

Calls so far, each under the call that made it:

  • power(2, 5): running now

Work so far

calls made1
in progress now1
most in progress at once1
  • Running now
  • Waiting for a call it made
  • Done: shows what it returned

Step 1 of 12. power(2, 5) needs power(2, 4) first. It calls it, and waits for the answer. Question: With n = 5, how many calls will be in progress at once, at most?

What happens next? With n = 5, how many calls will be in progress at once, at most?

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    return x * power(x, n - 1)

Try your own input
Halve n, but make the call twice

Calls so far, each under the call that made it:

  • power(2, 6): running now

Work so far

calls made1
in progress now1
most in progress at once1
  • Running now
  • Waiting for a call it made
  • Done: shows what it returned

Step 1 of 30. power(2, 6) needs power(2, 3) twice, once for each side of the ×. It calls the first. Question: With n = 6, how many calls will power make in all?

What happens next? With n = 6, how many calls will power make in all?

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    result = power(x, n // 2) * power(x, n // 2)
    if n % 2 == 1:
        result *= x
    return result

Try your own input
Halve n, and make the call once

Calls so far, each under the call that made it:

  • power(2, 6): running now

Work so far

calls made1
in progress now1
most in progress at once1
  • Running now
  • Waiting for a call it made
  • Done: shows what it returned

Step 1 of 8. power(2, 6) works out power(2, 3) once, as half. Question: With n = 6, how many calls will power make in all?

What happens next? With n = 6, how many calls will power make in all?

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    half = power(x, n // 2)  # once, not twice
    result = half * half
    if n % 2 == 1:
        result *= x
    return result

Try your own input

Bracket check

Section titled “Bracket check”

Check that every bracket closes in the right order with a stack: push each opening bracket, and when a closing one comes, it must match the top, which comes off. With the top at the end of the list, append() and pop() move nothing. With the top at the front, insert(0, x) and pop(0) move every bracket already on the stack: 6 moves for (([])). The lesson: My bracket check says ([)] is fine.

A stack of open brackets
  1. {0
  2. [1
  3. (2
  4. )3
  5. (4
  6. )5
  7. ]6
  8. }7

Work so far

stack, top on the rightempty
most on it at once0
items moved0

Step 1 of 10. Read the brackets from left to right. An opening one goes on the stack. A closing one must match the bracket on top, which comes off. Question: This string has 8 brackets. At most, how many will be on the stack at once?

What happens next? This string has 8 brackets. At most, how many will be on the stack at once?

def is_valid(s: str) -> bool:
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []  # the top is stack[-1]
    for ch in s:
        if ch in opener:
            if not stack or stack[-1] != opener[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

Try your own input
Top at the front: every push moves the stack
  1. (0
  2. (1
  3. [2
  4. ]3
  5. )4
  6. )5

Work so far

stack, top on the leftempty
most on it at once0
items moved0

Step 1 of 8. Read the brackets from left to right. An opening one goes on the stack. A closing one must match the bracket on top, which comes off.

def is_valid(s: str) -> bool:
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []  # the top is stack[0]
    for ch in s:
        if ch in opener:
            if not stack or stack[0] != opener[ch]:
                return False
            stack.pop(0)
        else:
            stack.insert(0, ch)
    return not stack

Try your own input

Rate limiter

Section titled “Rate limiter”

Let a request through only if fewer than the limit went through in the last window. A queue holds the ones that did, oldest first: before each request, the old ones leave from the front, and a request that goes through joins the back. A deque’s popleft() moves nothing. A list’s pop(0) moves every item behind the front: 6 moves for 6 requests with 4 in the window. The window here is 100 ms, so the times stay short. The lesson: My rate limiter let 200 requests through in one second.

A queue of the requests in the window
  1. 10
  2. 21
  3. 32
  4. 1003
  5. 1014
  6. 1025

Work so far

window nownot started
queue, oldest on the leftempty
items moved0

Step 1 of 10. A request goes through if fewer than 3 requests went through in the last 100 ms. The queue keeps the ones that did, oldest first.

from collections import deque
 
def allow(times: list[int], limit: int, window: int) -> list[bool]:
    recent = deque()  # the requests that went through in the last window, oldest first
    out = []
    for t in times:
        while recent and recent[0] <= t - window:
            recent.popleft()  # the oldest has left the window
        if len(recent) < limit:
            recent.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

Try your own input
With a list, pop(0) moves the whole queue
  1. 10
  2. 21
  3. 32
  4. 43
  5. 1014
  6. 1025

Work so far

window nownot started
queue, oldest on the leftempty
items moved0

Step 1 of 10. A request goes through if fewer than 4 requests went through in the last 100 ms. The queue keeps the ones that did, oldest first.

def allow(times: list[int], limit: int, window: int) -> list[bool]:
    recent = []  # the requests that went through in the last window, oldest first
    out = []
    for t in times:
        while recent and recent[0] <= t - window:
            recent.pop(0)  # the oldest has left the window
        if len(recent) < limit:
            recent.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

Try your own input

Rungwise: free Python interview prep, from okay to best.

No account needed. Your progress stays in this browser.