Longest Common Prefix
WHAT IT SAYS
Find the longest string that is a prefix of every string in an array, or the empty string if there is none.
WHAT IT'S REALLY ASKING
"Stop hunting for the longest agreement and hunt for the earliest DISAGREEMENT instead. One column where two strings differ does not just fail at that length — it kills every length above it, permanently. So the answer is not something you search for; it is wherever you are standing when the first mismatch stops you."
Try every prefix length, longest first
O(n * m^2) where n is the number of strings and m the shortest lengthTake the first string. Test whether its full prefix is a prefix of all the others; if not, drop one character and test again; keep shrinking until something works.
WHERE THE WORK IS WASTED — Testing length L re-reads characters 0 through L-1 of every string. Then testing L-1 re-reads characters 0 through L-2 of every string — the same characters, again, minus one. Two consecutive attempts share all but a single character of their work, and you throw the entire comparison away between them. You are paying quadratically to re-learn that the strings agree on the front, which is the one thing you already knew.
One disagreeing column caps every length above it.
The property 'the first L characters are common to all strings' is downward-closed: if it holds at L, it holds at L-1, because a prefix of a common prefix is itself a common prefix. So the valid lengths are 0, 1, 2, ..., up to some boundary, and then nothing. There are no holes. The answer is that boundary. Now look at what a mismatch means. Suppose at column c two strings disagree (or one of them simply ends). Then NO length greater than c can be valid, because any such prefix would have to include column c, where the strings differ. The mismatch is not a hint that you are close to the limit — it IS the limit, exactly, with no further checking required. That is what makes a single left-to-right sweep complete rather than merely convenient. Scan column by column: as long as every string agrees, the answer is at least this long; the instant one disagrees, the answer is exactly this long, and everything to the right of that column is unreachable. You stop immediately, and you have never looked at a character you did not need. (The same downward-closed structure would also license binary search on the length. It buys nothing here — you have to read the answer's characters anyway, so a linear scan is already optimal — but recognising the monotonicity is the reusable half of the insight.)
Scan columns, stop at the first mismatch
O(total characters actually read), which is at most the size of the input and often far less; O(1) extra spaceWalk column index c from 0 upward. At each column, compare the c-th character of the first string against the c-th character of every other string, and stop the moment one of them disagrees or runs out of characters. Return the first c characters.
The sorting trick
O(n * m log n) time for the sort, O(1) extra spaceSort the array lexicographically and compare only the FIRST and LAST strings — whatever prefix those two share is shared by everything sorted between them, since lexicographic order forces every string in the middle to start with it too. Two lines, memorable, and strictly slower: you pay a log factor to avoid looking at the middle strings at all.
Stop at the First Disagreement
YOU'LL SEE IT AGAIN WHEN
- The property you want is downward-closed: if it holds at size L it holds at every smaller size, so the valid sizes form an unbroken run and the answer is their boundary.
- A single counterexample anywhere is fatal to every larger candidate, which means the first failure terminates the search rather than merely informing it.
- The naive loop re-verifies, for each candidate size, everything it already verified for the previous size.