Longest Common Prefix

Tiny Summary

Find the longest string that is a prefix of all strings in an array. Use the simulation to compare Horizontal Scanning (compare prefix with each string) vs Vertical Scanning (check each character column across all strings).

---

Problem

Find the longest common prefix string amongst an array of strings.

Example: ["flower","flow","flight"] → "fl"

---

Horizontal Scanning

Compare the prefix with each string row-by-row, trimming it down after each comparison.

┌─────────────┐
 │ prefix = strs[0]        │  "flower"
└─────────────┘
      │
      ↓
┌─────────────────────────┐
│  Compare with strs[1]   │  "flow"
│  f-l-o-w ✓              │
│  Trim to: "flow"        │
└─────────────────────────┘
      │
      ↓
┌─────────────────────────┐
│  Compare with strs[2]   │  "flight"
│  f-l ✓, o-i ✗           │
│  Trim to: "fl"          │
└─────────────────────────┘
      │
      ↓
   Result: "fl"

Time complexity: O(n∗m) Space complexity: O(1)

---

Vertical Scanning

Check each column position across all strings simultaneously, stopping at the first mismatch.

     Col 0   Col 1   Col 2
       │       │       │
       ↓       ↓       ↓
    ┌──────────────────────┐
    │  f   │   l   │   o   │  "flower"
    │  f   │   l   │   o   │  "flow"
    │  f   │   l   │   i   │  "flight"
    └──────────────────────┘
       ✓       ✓       ✗
                       └─── STOP! Mismatch found

    Result: "fl" (columns 0-1)

Time complexity: O(n∗m) Space complexity: O(1)

---

Which Approach?

• Horizontal: More intuitive, better cache locality
• Vertical: Faster when common prefix is short or strings have varying lengths

Use the simulation above to see both algorithms in action!