Longest Common Prefix

The trap is to compare whole strings before identifying the stopping condition. The answer ends at the first column where agreement breaks—or when the shortest string runs out.

Read the contract before coding

A prefix starts at index 0. For "flower", valid prefixes include "", "f", "fl", and "flower". "low" is a substring, but it is not a prefix because it does not begin at index 0.

The required answer must be a prefix of every string in the input.

Under the supplied constraints:

• The array contains at least one string.
• A string can be empty.
• Nonempty strings contain lowercase English letters.
• If the strings share no starting characters, return "".

Examples:

["flower", "flow", "flight"] -> "fl"
["dog", "racecar", "car"]   -> ""

The first boundary to name is the shortest string. No common prefix can be longer than that string. If one input is empty, the answer is immediately empty because an empty string has no character at index 0.

This boundary gives us a clean way to think about the problem: inspect only positions that could possibly belong to every string.

Recognize the vertical scan

Place the strings one below another:

flower
flow
flight

Now inspect columns instead of comparing complete strings:

f l o w e r
f l o w
f l i g h t

Column 0 contains f in every row. Column 1 contains l in every row. At column 2, the reference string has o, while "flight" has i. That is where the common prefix ends.

This is called vertical scanning because we scan down one character column at a time. It is a direct string prefix scan:

1. Choose one string as the reference.
2. Read its character at position i.
3. Compare that character with position i in every other string.
4. Stop when a string is too short or a character differs.
5. Return the reference prefix before that position.

The state is small: the current index i represents how many characters have already been proven common.

A trie or sorting-based solution can also be designed, but neither is necessary here. A trie builds a separate character structure, and sorting introduces ordering work unrelated to the actual requirement. The direct scan exposes the important condition immediately: every string must agree at the same position.

Derive the invariant

An invariant is a condition that remains true as the algorithm progresses.

For this problem, use:

Before checking position i, every input string shares the reference prefix reference[:i].

At the beginning, i is 0. The prefix reference[:0] is "", which every string shares.

Suppose the invariant holds before checking position i. There are two possibilities:

• Every string has a character at position i, and all those characters match the reference character.
• At least one string ends before position i, or one character differs.

If all characters match, then the common prefix can safely grow from length i to length i + 1. The invariant remains true for the next iteration.

If any comparison fails, every longer prefix would include the failed position. That longer prefix cannot be shared by every string, so returning reference[:i] is correct.

The shortest-string boundary appears naturally here. Once a string has length i, it has no character at index i; indexing it would be invalid, and no prefix of length i + 1 can exist across all inputs.

Build the algorithm step by step

Use the first string as the reference. It does not have to be special or shortest. It is simply a convenient source from which to return the proven prefix.

For each position in the reference:

1. Store the reference character at that position.
2. Visit every string.
3. Check the string's length before indexing.
4. If the string ends at or before this position, return reference[:i].
5. If its character differs from the reference character, return reference[:i].
6. If every string passes, continue to the next position.
7. If the reference is exhausted, return the entire reference.

Here is the Python implementation:

from typing import List


def longest_common_prefix(strs: List[str]) -> str:
    # The problem guarantees at least one string.
    # This guard makes the function safe if called with an empty list.
    if not strs:
        return ""

    reference = strs[0]

    for i, expected in enumerate(reference):
        for current in strs:
            # Position i is unavailable when len(current) <= i.
            if i >= len(current) or current[i] != expected:
                return reference[:i]

    return reference

Each piece of state has a clear job:

• reference supplies the candidate characters and the returned prefix.
• i is the column currently being tested.
• expected is the character every string must match.
• reference[:i] contains exactly the positions already proven common.

The length check must happen before current[i]. In Python, i >= len(current) means the current string has no character at that position.

You can also compute the shortest length first and scan only to that boundary. The version above discovers the same boundary during comparison and avoids storing another value. Both approaches express the same invariant.

Dry-run the state and failure points

Mismatch in the middle

Input:

["flower", "flow", "flight"]

Position	Reference character	Comparison result
0	f	All strings match
1	l	All strings match
2	o	"flight" has i; stop

At position 2, the proven prefix is reference[:2], which is "fl". Returning "flo" would be wrong because "flight" does not begin with "flo".

Another mismatch

Input:

["apple", "ape", "april"]

Position	Reference character	Comparison result
0	a	All strings match
1	p	All strings match
2	p	"apple" has p, "ape" has e; stop

The result is:

"ap"

The first two columns survive every comparison. The next column does not.

The shortest string is the answer

Input:

["inter", "internet", "internal"]

The strings agree at every position in "inter":

i n t e r
i n t e r n e t
i n t e r n a l

The scan reaches the end of the shortest string without finding a mismatch. The entire reference, "inter", is therefore the answer.

The longer strings may continue, but those extra characters cannot be part of a prefix of "inter".

No common first character

Input:

["dog", "racecar", "car"]

At position 0, the reference character is d. The next string begins with r, so the algorithm returns:

reference[:0]  # ""

This is not a special failure path. It is the ordinary first-column mismatch.

An empty string

Input:

["flower", "", "flight"]

At position 0, the empty string has length 0. The condition 0 >= len("") is true, so the function returns reference[:0], or "".

The empty result follows directly from the contract: an empty string cannot share a nonempty prefix.

Prove correctness and analyze complexity

The correctness proof follows the invariant.

Invariant: Before position i is checked, reference[:i] is a prefix of every input string.

• Initialization: At i = 0, reference[:0] is the empty string. It is a prefix of every string.
• Maintenance: If every string contains position i and its character matches expected, then reference[:i + 1] is shared by every string. The invariant holds for the next position.
• Termination: If a string ends before position i, or its character differs, then every prefix longer than reference[:i] includes an invalid position. Therefore reference[:i] is the longest possible common prefix.

If the loop finishes, every position in the reference matched every input string. The reference itself is then a prefix of all strings and is the longest possible answer because the reference has no further positions to extend.

Let:

• n be the number of strings.
• m be the length of the shortest string.

The algorithm performs at most n comparisons for each of m positions, so the time complexity is:

O(nm)

The scan stops early when it finds a mismatch, so many inputs perform less work. But O(nm) is the worst-case bound when the strings agree through the shortest string.

The working space is:

O(1)

aside from the returned prefix. The function does not mutate the input or build a trie, sorted copy, or character buffer.

Early return is not a heuristic optimization. It follows from the invariant: once one condition fails, every longer candidate contains that failure.

Edge cases and implementation traps

Check length before indexing

This is unsafe:

if current[i] != expected:
    ...

It fails when current is shorter than the reference. Use the length check first:

if i >= len(current) or current[i] != expected:
    return reference[:i]

Python evaluates or from left to right and stops once the first condition is true, so current[i] is not accessed when the string is too short.

Return the prefix before the mismatch

At index i, the character at i has not been proven common. Return:

reference[:i]

Python slicing stops before the right endpoint. So reference[:i] contains positions 0 through i - 1, exactly the characters that passed.

Returning reference[:i + 1] would include the mismatching character.

One string

If the input contains one string, that string is already its own longest common prefix. The nested loop compares it with itself, all positions pass, and the function returns the full reference.

Identical strings

If every string is identical, no comparison fails. The scan reaches the end of the reference and returns it unchanged.

Empty input array

The stated constraints guarantee at least one string, so this case does not need to be handled for the judged problem. The defensive guard is still reasonable in reusable code:

if not strs:
    return ""

It makes the function's behavior explicit instead of allowing strs[0] to fail.

The transferable pattern

When several sequences must agree from the same starting position, scan one position at a time and keep the longest prefix proven common.

Before coding, name three things:

1. The boundary: the shortest sequence limits how far agreement can extend.
2. The state: the prefix length already verified.
3. The failure event: a sequence ends or its next value differs.

That recognition rule reaches beyond strings. It applies whenever multiple ordered inputs must share an initial run: compare the same column, preserve the verified prefix, and stop at the first violated condition. Clear the noise. Find the first broken column. Return what the invariant has earned.