{"text": "# Edit Distance Rolling Row (Practice 5043): Drill\n\nInterviewers use this pattern to test whether you can state the invariant before coding. Here is a compact rehearsal note.\n\n## Approach\n\nClassic Levenshtein DP kept to one row plus a saved diagonal value.\n\n```python\ndef min_distance(a,b):\n prev=list(range(len(b)+1))\n for i,x in enumerate(a,1):\n cur=[i]\n for j,y in enumerate(b,1):\n cur.append(prev[j-1] if x==y else 1+min(prev[j-1],prev[j],cur[-1]))\n prev=cur\n return prev[-1]\n```\n\n## Complexity\n\nLinear in the dominant input size for the scan; heap/tree variants add a log factor.\n\n## Interview pitfalls\n\nState the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.\n\n## Practicing out loud\n\nNarrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [Linkjob.ai](https://www.linkjob.ai/).\n", "extension": "md", "title": "Edit Distance Rolling Row (Practice 5043): Drill"}