Longest Common Prefix

The problem. Given an array of strings strs, return the longest string that every word starts with. If they share nothing, return the empty string.

Example

strs = ["flower","flow","flight"]           ->  "fl"
strs = ["dog","racecar","car"]              ->  ""
strs = ["interview","inter","internet"]     ->  "inter"   (stops where "inter" ends)

The pattern: scan and build

Some string questions need no clever data structure at all: walk the input once, keep a tiny bit of state (where you are, the current run, the sign seen so far), and build the answer as you go — with a builder or a write pointer, never with += in a loop. The difficulty is in the details: where to stop, what to skip, which edge cases break the loop.

This pattern covers prefixes, compression, parsing numbers, converting between formats (Roman numerals, Zigzag), adding big numbers digit by digit. The three lessons here go from a two-line idea to a careful parser.

1. Sort, then compare the first and last word

Sort the words. In dictionary order, the first and last words are the most different ones, and any prefix they share is shared by every word between them. So only those two need comparing.

1function longestCommonPrefix(strs) {2  const sorted = [...strs].sort();            // the first and last words differ the most3  const first = sorted[0], last = sorted[sorted.length - 1];4  let i = 0;5  while (i < first.length && first[i] === last[i]) i++;6  return first.slice(0, i);                   // what they share, everyone shares7}

Time O(m · n log n), space O(n) for n words of length up to m: sorting compares strings, each comparison up to m characters.

2. Scan column by column

Use the first word as a guide and compare column by column: check that every word has the same character at position 0, then 1, and so on. Stop at the first column where a word disagrees or has already ended.

1function longestCommonPrefix(strs) {2  const first = strs[0];3  for (let i = 0; i < first.length; i++) {    // column i4    for (const word of strs) {5      if (i === word.length || word[i] !== first[i]) {6        return first.slice(0, i);             // a word ended or disagreed: stop here7      }8    }9  }10  return first;                               // the whole first word is shared11}

Time O(S), space O(1) beyond the answer, where S is the total number of characters. In fact it stops after reading only the shared columns plus one, which is often far less.

Comparing the approaches

The column scan is the expected answer: it reads no more than it must and needs no extra memory. The sorting trick is worth mentioning as a neat observation.

Edge cases to test

Variations