Skip to main content

72. Edit Distance

hardAsked at Broadcom

Compute the minimum number of insertions, deletions, and substitutions to transform one string into another. Broadcom asks this classic DP problem because Levenshtein distance underlies error-correcting code similarity metrics and firmware diff-patching algorithms — both critical in Broadcom's over-the-air update systems for embedded device fleets.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2025-10)— Reported in Broadcom senior SWE onsite reports as a 2D DP hard problem testing state-transition reasoning.
  • Blind (2025-07)— Broadcom threads mention Edit Distance as a hard DP problem asked in infrastructure software principal-level rounds.

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. You have the following three operations permitted on a word: Insert a character, Delete a character, Replace a character.

Constraints

  • 0 <= word1.length <= 500
  • 0 <= word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

Examples

Example 1

Input
word1 = "horse", word2 = "ros"
Output
3

Explanation: horse → rorse (replace h→r) → rose (delete r) → ros (delete e). 3 operations.

Example 2

Input
word1 = "intention", word2 = "execution"
Output
5

Explanation: 5 operations: replace i→e, replace n→x, delete t, replace n→u, replace i→i (already correct), replace o→o (already correct)... various 5-op paths exist.

Approaches

1. 2D bottom-up DP

dp[i][j] = minimum operations to convert word1[0..i-1] to word2[0..j-1]. Base cases: dp[0][j]=j (delete all), dp[i][0]=i (insert all). Transition: if chars match, dp[i][j]=dp[i-1][j-1]; otherwise min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) for delete, insert, replace.

Time
O(m * n)
Space
O(m * n)
function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => i === 0 ? j : j === 0 ? i : 0)
  );
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete from word1
          dp[i][j - 1],     // insert into word1
          dp[i - 1][j - 1]  // replace
        );
      }
    }
  }
  return dp[m][n];
}

Tradeoff: O(m*n) time and space. The standard answer. The transition covers all three operations cleanly. Broadcom interviewers expect you to name each dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] as delete, insert, and replace respectively.

2. Space-optimised (two-row DP)

Since dp[i][j] depends only on the previous row and the current row, maintain only two 1D arrays instead of the full m×n matrix.

Time
O(m * n)
Space
O(n)
function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);
  for (let i = 1; i <= m; i++) {
    const curr = new Array(n + 1).fill(0);
    curr[0] = i;
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        curr[j] = prev[j - 1];
      } else {
        curr[j] = 1 + Math.min(prev[j], curr[j - 1], prev[j - 1]);
      }
    }
    prev = curr;
  }
  return prev[n];
}

Tradeoff: O(n) space — a significant improvement for large inputs. Broadcom interviewers reward proactive space optimisation. The two-row approach mirrors how streaming diff-patch algorithms work with fixed memory budgets.

Broadcom-specific tips

At Broadcom, state the three DP transitions with their semantic meaning before coding: 'dp[i-1][j]+1 is delete a character from word1; dp[i][j-1]+1 is insert a character into word1; dp[i-1][j-1]+1 is replace.' Connecting to Broadcom's domain: 'Edit distance is the core metric in firmware binary diff algorithms — computing minimal patch files for over-the-air firmware updates to millions of edge devices.' Follow up with the space-optimised two-row version proactively.

Common mistakes

  • Incorrect base cases: dp[0][j] should equal j (delete all j chars of word2 to get empty) and dp[i][0] should equal i.
  • Mixing up which transition corresponds to insert vs delete — dp[i-1][j] is deleting from word1 (moving up), dp[i][j-1] is inserting into word1 (moving left).
  • Not initialising the 2D array correctly in JavaScript — Array(m+1).fill(new Array(n+1)) shares the same row reference.
  • Not handling empty strings — word1='' requires n insertions; word2='' requires m deletions.

Follow-up questions

An interviewer at Broadcom may pivot to one of these next:

  • Longest Common Subsequence (LC 1143) — related DP; edit distance can be derived from LCS.
  • One Edit Distance (LC 161) — check if two strings differ by exactly one operation.
  • How would you compute edit distance for very long strings that don't fit in memory (streaming / blocked DP)?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What does each DP transition represent?

dp[i-1][j]+1: delete word1[i] (advance i, stay at j). dp[i][j-1]+1: insert word2[j] into word1 (stay at i, advance j). dp[i-1][j-1]+1: replace word1[i] with word2[j] (advance both).

How is edit distance related to LCS?

edit_distance = m + n - 2 * LCS_length. Knowing the LCS gives you the minimum characters that don't need to change; the rest are inserts and deletes.

Why is the space optimisation from O(mn) to O(n) valid?

Each cell dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. All three come from the previous row or the current row to the left — two rows of data are sufficient.

Practice these live with InterviewChamp.AI

Drill Edit Distance and other Broadcom interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →