Longest Common Prefix · Optimal Solution

Read down the columns, not across the rows.

An autocomplete engine narrows suggestions as the user types — 'fl' matches 'flight', 'flow', 'flour'. Finding the longest shared prefix means scanning every candidate at the same character position simultaneously. At column 0 check every first letter; at column 1 every second, and so on. The moment any string disagrees — or the shortest string runs out — the prefix is complete. O(S) time where S is the sum of all characters. O(1) extra space.

Interactive

Watch the column scanner find the shared prefix

Concept

Why scan vertically?

Horizontal pair-by-pair comparison can over-count if the first two strings happen to share a long prefix that later strings don't. Vertical scanning guarantees every word is consulted before advancing the column pointer.

Column-first thinking

Imagine the words stacked in a table. Reading down column 0 asks "does every word start with the same letter?" before ever looking at column 1.

Shortest word governs

No prefix can be longer than the shortest input. Computing min(len) up front gives an upper bound on the loop and prevents out-of-bounds access.

Early exit

The first character mismatch terminates the entire search. In the best case only one column is examined; in the worst case all characters of the shortest word are checked.

Algorithm

Vertical column scan in four steps

  1. Find the shortest word length. This is the maximum number of columns to scan. If any word is empty the answer is immediately "".
  2. For each column index 0 … shortest − 1: take the character from the first word as the candidate for that column.
  3. Compare the candidate against every other word. If a word's character at this column differs, return the prefix collected so far. Otherwise continue to the next word.
  4. All words matched at this column — extend the prefix by one character and advance to the next column.
Edge Cases

Guard rails to remember

Empty string in the array

If any word has length 0, the shortest-word length is 0 and the outer loop never executes. The result is "".

Single word

With only one word there is nothing to compare against. The entire word is its own prefix. Return it directly.

All words identical

Every column matches and the loop runs to the end of the shortest word (all words). The prefix equals the full word.