Algorithm

Longest Common Prefix

Arrays & Strings Pattern

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string.

CONSTRAINTS
  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters
EXAMPLE 1
Input: strs = ["flower","flow","flight"]
Output: "fl"
All three words share 'fl'. 'flower' and 'flow' share 'flo', but 'flight' diverges at position 2 with 'i'.
EXAMPLE 2
Input: strs = ["dog","racecar","car"]
Output: ""
There is no shared starting character among the three words, so the prefix is empty.
EXAMPLE 3
Input: strs = ["interview","internal","interpret"]
Output: "inter"
All three words share the prefix 'inter'. They diverge at position 5 with 'v', 'n', and 'p' respectively.
What if the array contains only one string?
The prefix of a single string is the string itself. There are no other strings to differ, so the entire string is the answer.
Can the prefix be longer than the shortest string in the array?
No. The prefix is bounded by the shortest string. If all other words share all its characters, the shortest string is the common prefix.
What if one of the strings is empty?
An empty string has no characters, so there is no common prefix. Return empty string immediately.
Does the order of strings in the array matter?
No. The common prefix must be shared by all strings, regardless of their order.

Finding the longest common prefix means identifying the longest string that all words in an array share at their very beginning. The moment any single word diverges from the others, the shared prefix ends.

Horizontal Scan (O(S))

We find the common prefix between the first two words. We then compare that result with the third word, then the fourth, and so on. If at any point the prefix becomes empty, we can stop early.

python
if not strs: return ""
prefix = strs[0]
for i in range(1, len(strs)):
    while not strs[i].startswith(prefix):
        prefix = prefix[:-1]
        if not prefix: return ""
return prefix
Vertical Verification

The horizontal scan might compare many characters multiple times across strings. The core insight is to look at the words column-by-column. We pick the first word as a guide and check the same position in every other word simultaneously. This allows us to find the exact character where the agreement breaks.

Vertical Scan (O(S))

We iterate through the characters of the first word. For each position, we check if all other strings have the same character. If a string is too short or has a different character, we return the prefix found so far.

python
if not strs: return ""
for i in range(len(strs[0])):
    char = strs[0][i]
    for j in range(1, len(strs)):
        # If word is too short or character doesn't match
        if i == len(strs[j]) or strs[j][i] != char:
            return strs[0][:i]
return strs[0]
Worked Example:["flow", "flower", "flight"]
f
l
o
w
f
l
o
w
e
r
f
l
i
g
h
t
We compare the characters in column 0: 'f', 'f', and 'f'. Since they all match, our common prefix is 'f'.
f
l
o
w
f
l
o
w
e
r
f
l
i
g
h
t
We compare the characters in column 1: 'l', 'l', and 'l'. Since they all match, our common prefix grows to 'fl'.
f
l
o
w
f
l
o
w
e
r
f
l
i
g
h
t
We compare the characters in column 2: 'o', 'o', and 'i'. The character 'i' in 'flight' is a mismatch, so we stop scanning and return 'fl'.
Interactive Strategy Visualization

Vertical Scanning

Column-by-Column Consensus Engine
Scanning column0
STR0
F
L
O
W
E
R
STR1
F
L
O
W
STR2
F
L
I
G
H
T
Prefix so far""
📡

Column 0: reference character is 'F' from "FLOWER".

O(S) Horizontal Shrink
→
O(answer × N) Column Scan · Early Exit