Edit Distance

▶

Steps

setup

Initialize lengths and next_row array

We calculate the lengths of word1 and word2, then initialize the next_row array with zeros. This array will hold the DP values for the suffix starting beyond the last character of word1.

💡 Setting up lengths and the DP array is essential to prepare for bottom-up computation of edit distances.

Line:

m, n = len(word1), len(word2)
next_row = [0] * (n + 1)

💡 The DP arrays have size n+1 to handle empty suffixes of word2.

fill_row

Fill next_row with base case values

We fill next_row with the cost of converting an empty suffix of word1 to suffixes of word2. This is simply the number of characters left in word2 to insert.

💡 This base case sets the cost when word1 is empty, which is the length of the remaining word2 suffix.

Line:

for j in range(n + 1):
    next_row[j] = n - j

💡 The DP array now represents the cost of inserting characters to match word2 suffixes.

traverse

Process i=4 ('e') row: initialize and compute DP values

Initialize current array for i=4 and set current[n] to cost of deleting remaining characters. Then compute current[j] for j=2,1,0 by comparing characters and choosing minimal edit operations.

💡 Processing from the end allows bottom-up DP to build solutions for smaller suffixes first.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 The DP formula combines insert, delete, and replace costs to find minimal edits.

expand

Swap current and next_row arrays after i=4

Assign current to next_row to prepare for next iteration with i=3.

💡 Swapping arrays saves space and moves the DP computation forward.

Line:

next_row = current

💡 The next_row now holds the latest DP results for suffix starting at i=4.

traverse

Process i=3 ('s') row: initialize and compute DP values

Initialize current array for i=3 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Each new row starts with base deletion cost for suffix of word1.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 Matching characters allow carrying forward previous cost without increment.

expand

Swap current and next_row arrays after i=3

Assign current to next_row for next iteration with i=2.

💡 Swapping arrays moves the DP computation forward efficiently.

Line:

next_row = current

💡 Next_row now holds DP results for suffix starting at i=3.

traverse

Process i=2 ('r') row: initialize and compute DP values

Initialize current array for i=2 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Each row starts with deletion cost for suffix of word1.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 Matching characters reduce edit distance by carrying forward previous costs.

expand

Swap current and next_row arrays after i=2

Assign current to next_row for next iteration with i=1.

💡 Moving DP computation forward.

Line:

next_row = current

💡 Next_row holds DP results for suffix starting at i=2.

traverse

Process i=1 ('o') row: initialize and compute DP values

Initialize current array for i=1 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Starting new DP row with deletion cost.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 DP combines three possible operations to find minimal cost.

expand

Swap current and next_row arrays after i=1

Assign current to next_row for next iteration with i=0.

💡 Moving DP computation forward.

Line:

next_row = current

💡 Next_row holds DP results for suffix starting at i=1.

traverse

Process i=0 ('h') row: initialize and compute DP values

Initialize current array for i=0 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Starting new DP row with deletion cost.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 DP row fully computed for i=0.

reconstruct

Final swap and read answer

Assign current to next_row and return next_row[0] as the minimum edit distance between the full strings.

💡 The answer is the minimal edits to convert word1 to word2.

Line:

next_row = current
return next_row[0]

💡 The DP solution is complete and the answer is at next_row[0].

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)  # STEP 1
    next_row = [0] * (n + 1)  # STEP 1
    for j in range(n + 1):  # STEP 2
        next_row[j] = n - j  # STEP 2

    for i in range(m - 1, -1, -1):  # STEPS 3,5,7,9,11
        current = [0] * (n + 1)  # STEPS 3,5,7,9,11
        current[n] = m - i  # STEPS 3,5,7,9,11
        for j in range(n - 1, -1, -1):  # Inner loop
            if word1[i] == word2[j]:  # Character match
                current[j] = next_row[j + 1]
            else:
                current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])
        next_row = current  # Swap rows

    return next_row[0]  # STEP 12

📊

Edit Distance - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the algorithm builds solutions for smaller suffixes and combines them to solve the full problem, making the dynamic programming approach intuitive.

setup

0

0

0

1

0

2

n

0

3

fill_row

j

3

0

2

1

1

2

0

3

compare

3

0

2

1

1

2

1

3

move_left

3

0

2

1

1

2

i

1

3

compare

3

0

2

1

1

2

i

2

3

move_left

3

0

2

1

i

1

2

2

3

compare

2

0

3

1

i

3

2

3

3

move_left

2

0

i

3

1

3

2

3

3

compare

3

0

i

3

1

4

2

4

3

move_left

i

3

0

3

1

4

2

4

3

compare

i

4

0

4

1

5

2

5

3

record

answer

3

0

2

1

1

2

1

3

Result: 3

Key Takeaways

✓ The DP arrays represent minimal edit distances for suffixes of the strings, computed bottom-up.

This insight is hard to see from code alone because the arrays are reused and updated in place.

✓ Matching characters allow the algorithm to carry forward previous costs without adding edits.

Seeing this visually clarifies why some DP cells copy values instead of adding 1.

✓ Each DP cell chooses the minimal cost among insert, delete, and replace operations, illustrating the decision process.

Watching the min calculation step-by-step reveals how the algorithm balances different edit operations.

Practice

1. You are given a list of daily stock prices and a maximum number of allowed transactions. You want to maximize profit by buying and selling stocks multiple times but cannot hold more than one stock at a time. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Pure recursion exploring all buy/sell combinations without memoization

B. Greedy approach that buys whenever price is lower than the next day and sells the next day

C. Dynamic programming with states tracking day, transactions left, and holding status

D. Sorting prices and picking the top k profitable pairs

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing profit with at most k transactions, where each transaction is a buy followed by a sell, and you cannot hold multiple stocks simultaneously.

2. Step 2: Identify suitable algorithmic approach

   Greedy approaches fail because local optimal buys/sells do not guarantee global maximum profit. Pure recursion is correct but inefficient. Sorting prices and picking pairs ignores transaction limits and order constraints. Dynamic programming tracks day, transactions left, and holding state to explore all valid sequences efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP with states is the classic solution for k transaction stock problems [OK]

Hint: DP with day, transactions, holding states solves optimally [OK]

Common Mistakes:

• Assuming greedy always works for stock buy/sell
• Trying pure recursion without memoization
• Ignoring holding state in DP

2. You are given an array representing the heights of adjacent bars in a histogram. The task is to find the largest rectangular area that can be formed within the bounds of the histogram bars. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Greedy approach selecting the tallest bar and expanding outwards

B. Brute force nested loops checking all possible rectangles

C. Dynamic programming with memoization of subproblems

D. Single pass stack-based approach that tracks indices of bars

Solution

1. Step 1: Understand problem constraints and requirements

   The problem requires finding the largest rectangle in a histogram efficiently, which involves checking contiguous bars and their heights.

2. Step 2: Identify optimal approach using stack

   The single pass stack-based approach uses a stack to keep track of indices of bars in ascending order, allowing calculation of maximal rectangle areas in O(n) time by popping bars when a smaller height is encountered.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach is known optimal for largest rectangle in histogram [OK]

Hint: Stack-based approach achieves O(n) time [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing this with a DP problem
• Thinking greedy expansion from tallest bar suffices

3. What is the time complexity of the single pass stack-based solution for the Largest Rectangle in Histogram problem, and why might a candidate mistakenly think it is higher?

medium

A. O(n) because each bar is pushed and popped at most once

B. O(n log n) due to sorting or binary search steps

C. O(n^2) because each bar can be pushed and popped multiple times

D. O(n) but with O(n^2) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze push/pop operations

   Each bar index is pushed onto the stack once and popped once when a smaller height is encountered, so total stack operations are O(n).

2. Step 2: Understand why complexity is linear

   Since the inner while loop pops bars only when a smaller height is found, total pops across all iterations sum to at most n, making the overall time O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Push/pop per bar once -> linear time [OK]

Hint: Each bar pushed and popped once -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing stack operations as repeated for each iteration
• Thinking recursion or sorting is involved

4. Examine the following modified code for Largest Rectangle in Histogram. Which line contains a subtle bug that can cause incorrect maximum area calculation?

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel to flush stack at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # Restore original list
    return max_area

medium

A. Line with 'while stack and heights[stack[-1]] >= h:'

B. Line with 'height = heights[stack.pop()]'

C. Line with 'width = i - left - 1'

D. Line with 'heights.append(0)'

Solution

1. Step 1: Identify condition in while loop

   The condition uses '>=' which causes bars of equal height to be popped prematurely, merging areas incorrectly.

2. Step 2: Correct condition

   Changing '>=' to '>' ensures bars of equal height remain on stack, preserving correct width calculations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '>=' pops equal height bars too early, causing wrong max area [OK]

Hint: Use '>' not '>=' to avoid premature popping [OK]

Common Mistakes:

• Using '>=' instead of '>' in while condition
• Miscomputing width boundaries
• Forgetting sentinel bar

5. The following code attempts to solve the Russian Doll Envelopes problem optimally. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes with key (x[0], x[1]) ascending both

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing tails element at found index

Solution

1. Step 1: Examine sorting key

   Sorting by (width asc, height asc) allows envelopes with same width and increasing height, which breaks strict nesting rules.

2. Step 2: Correct sorting key

   Sorting by (width asc, height desc) prevents envelopes with equal width but increasing height from being counted incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing sorting to (x[0], -x[1]) fixes the bug [OK]

Hint: Sort height descending for equal widths to avoid counting duplicates [OK]

Common Mistakes:

• Sorting both width and height ascending
• Using <= instead of < in comparisons
• Not handling equal widths properly