Interactive DSA and system design

Learn complex engineering ideas by watching them move.

48stepsO(n*m)averageO(n*m)space

DP lab

LCS 2D Matrix Optimal Trace Flow

Step 1 / 48

	∅	L	O	N	G	E	S	T
∅
S
T
O
N
E

Referencing Cell Active Cell Selected Base Optimal Path

Animation speed

Space play / pause←→ stepR reset

Current operation

Initialize 2D Table

Create a 2D matrix of size 6x8 to store LCS lengths for subsequences of A ("STONE") and B ("LONGEST").

Algorithm state

STONEString ALONGESTString B

LCS String Presets

Complexity notes

O(n*m)averageO(n*m)worstO(n*m)spaceN/Astable

Synced code trace

function LCS(A, B) {  const dp = Array(n+1).fill(0);  if (A[i-1] === B[j-1])    dp[i][j] = dp[i-1][j-1] + 1;  else    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);  return backtrack(dp, n, m);}

Interactive Notes

✓ Notes are saved automatically and persist per step.