Longest Common Prefix — The Column Scan That Shows Up at Google

Problem Statement#

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

Example 1:

Input:  strs = ["flower", "flow", "flight"]
Output: "fl"
Explanation: "fl" is the longest prefix shared by all three strings.

Example 2:

Input:  strs = ["dog", "racecar", "car"]
Output: ""
Explanation: There is no prefix common to all strings.

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of lowercase English letters only

Why This Problem Matters#

Longest Common Prefix (LeetCode 14) is rated Easy, but it appears disproportionately often in Google phone screens and on-site rounds — not because it is hard, but because it is a litmus test. The interviewer is not checking whether you can write a loop. They are checking three things at once.

First: can you identify the right axis to scan? The naive instinct is to compare strings against each other. The better instinct is to scan columns — character positions across all strings simultaneously — which reframes the problem from O(n^2) pairwise comparisons to a clean linear scan.

Second: can you think about multiple approaches and articulate trade-offs? Google interviewers almost always follow up with "how else could you solve this?" Having vertical scan, horizontal fold, and binary search on length ready to discuss (not just code) is what separates a hire from a no-hire at this level.

Third: can you handle edge cases without being prompted? An empty input array, an array containing an empty string, an array with a single element, all identical strings — these are the first things a good interviewer probes. Knowing them cold means you are thinking like an engineer, not a student.

The problem also introduces a technique — scanning character positions across multiple strings simultaneously — that appears in autocomplete systems, trie-based search, and DNS prefix matching. It is not just an interview toy.

The Core Insight / Key Technique#

The key question is: what does "longest common prefix" actually mean geometrically?

Think of the strings as rows in a grid:

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

The common prefix is everything in the columns where every row agrees. The moment any column has a mismatch — or any row runs out of characters — the prefix ends.

This framing immediately suggests the optimal approach: scan column by column, left to right. At each column position, check whether every string has a character there and whether all those characters are identical. The first column where that check fails is where the prefix ends.

This is the vertical scan approach. It is O(S) where S is the total number of characters across all strings — you never look at any character more than once, and you stop as early as possible the moment a mismatch is found.

The critical edge insight: the prefix can never be longer than the shortest string in the input. If any string has length 0, the answer is immediately "". The vertical scan handles this naturally because at column 0 it will immediately find that the short string has no character.

A second insight powers the horizontal fold approach: if you take any two strings and find their common prefix, that result is an upper bound on what the final answer can be. Reduce left to right: prefix = lcp(strs[0], strs[1]), then prefix = lcp(prefix, strs[2]), and so on. Each step can only shrink the prefix, never grow it.

The binary search on length approach exploits a monotonicity property: if a prefix of length k is common to all strings, then every prefix of length j < k is also common. If a prefix of length k is NOT common, then no prefix of length j > k can be common either. This means you can binary search on the prefix length from 0 to len(shortest_string), halving the search space each time.

Visual Dry Run#

Let's trace all three approaches on strs = ["flower", "flow", "flight"].

Vertical Scan Trace#

We scan column by column across all strings:

Column 0: 'f', 'f', 'f'  → all match, continue
Column 1: 'l', 'l', 'l'  → all match, continue
Column 2: 'o', 'o', 'i'  → MISMATCH ('o' vs 'i'), stop

Return strs[0][:2] = "fl". Done in 7 character comparisons total.

Horizontal Fold Trace#

Start:  prefix = "flower"
 
Step 1: compare "flower" with "flow"
        "flow".startswith("flower")? No  → trim: "flowe"
        "flow".startswith("flowe")? No  → trim: "flow"
        "flow".startswith("flow")? Yes  → prefix = "flow"
 
Step 2: compare "flow" with "flight"
        "flight".startswith("flow")? No  → trim: "flo"
        "flight".startswith("flo")? No  → trim: "fl"
        "flight".startswith("fl")? Yes  → prefix = "fl"
 
Result: "fl"

Binary Search Trace#

Shortest string is "flow" (length 4). We binary search on the prefix length in [0, 4].

lo=0, hi=4
 
Round 1: mid = (0+4)//2 = 2
  Check prefix "fl" (length 2) against all strings:
    "flower"[:2] = "fl" ✓
    "flow"[:2]   = "fl" ✓
    "flight"[:2] = "fl" ✓
  All match → lo = mid + 1 = 3
 
Round 2: mid = (3+4)//2 = 3
  Check prefix "flo" (length 3) against all strings:
    "flower"[:3] = "flo" ✓
    "flow"[:3]   = "flo" ✓
    "flight"[:3] = "fli" ✗
  Mismatch → hi = mid - 1 = 2
 
lo(3) > hi(2): stop
Answer = shortest_string[:lo-1+1] ... use strs[0][:lo] where lo ended at 3
→ Actually return strs[0][:lo] = "flower"[:3]... let's be precise:
  After loop, lo = 3, the last successful mid was 2.
  Return strs[0][:hi+1] = "flower"[:3] = "flo"? No...

Let me clarify the binary search invariant precisely: we track lo (the smallest length that might work) and hi (the largest length that might work). When the loop ends, hi is the largest confirmed-working length.

lo=1, hi=4  (lengths, 1-indexed)
 
Round 1: mid=2 → "fl" works → lo=3
Round 2: mid=3 → "flo" fails → hi=2
 
lo(3) > hi(2): done. Return strs[0][:hi] = "flower"[:2] = "fl" ✓

Common Mistakes#

These are real errors candidates make under pressure — not contrived test cases, but thinking errors that happen when the clock is running.

Mistake 1: Forgetting that the prefix length is bounded by the shortest string.

A common bug is iterating up to len(strs[0]) without checking whether other strings are long enough at each column. If strs = ["ab", "a"], iterating to column 1 on "ab" will attempt strs[1][1] which is an index-out-of-bounds error. The fix in vertical scan is to check col >= len(s) as a short-circuit condition before comparing characters. The horizontal fold approach sidesteps this naturally since startswith handles length differences internally.

Mistake 2: Returning the wrong string slice on early exit.

When the vertical scan finds a mismatch at column col, the correct answer is strs[0][:col] — the prefix up to but not including column col. A frequent off-by-one error is returning strs[0][:col+1] (including the mismatched column) or strs[0][:col-1] (missing the last valid character). Trace through ["fl", "fl"] manually: the loop ends naturally (not via mismatch), and the correct answer is strs[0] itself — "fl". Make sure the no-mismatch path also returns correctly.

Mistake 3: Not handling the empty array or empty string inputs.

The constraints say strs.length >= 1, but they also say strs[i].length >= 0 — meaning the empty string is a valid element. If strs = ["", "abc"], the answer is "". The vertical scan handles this correctly because at column 0, the empty string fails the length check immediately. But candidates who "optimize" by initializing prefix = strs[0] in horizontal fold and then start the loop at index 1 can accidentally return strs[0] unchanged if there is only one element — which is actually correct. The edge case to double-check: if strs = [""], the answer is "", not an error.

Mistake 4: Mutating the input in the binary search approach.

Some candidates use the first string both as the candidate prefix source and as one of the strings to validate against. If they slice and reassign strs[0] during the search, they corrupt the binary search state. Always slice from a separate variable (e.g., the shortest string) and validate against the original strs array unchanged.

Mistake 5: Binary search on the wrong variable.

The binary search is on prefix length, not on array index. Candidates who have just solved a binary-search-on-index problem sometimes conflate the two. The search space is [0, len(shortest_string)] — the length of the shortest string is the hard upper bound. The predicate is "does a prefix of this length exist in all strings?" which is all(s.startswith(candidate) for s in strs) or equivalently all(s[:mid] == candidate for s in strs).

Solutions#

Approach 1 — Vertical Scan (Column by Column) — Optimal#

The cleanest approach. Scan character positions from left to right. At each position, check all strings. Stop the moment any string is too short or has a different character.

Python

from typing import List
 
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # Edge case: empty input list — no prefix is possible
        if not strs:
            return ""
 
        # Iterate over each character position using the first string as reference
        for col in range(len(strs[0])):
            # The character at this column position in the first string
            char = strs[0][col]
 
            # Check every other string at the same column position
            for s in strs[1:]:
                # Two failure conditions:
                # 1) s is shorter than strs[0] — col is out of bounds for s
                # 2) s has a different character at this column
                if col >= len(s) or s[col] != char:
                    # The prefix ends at this column (not including it)
                    return strs[0][:col]
 
        # No mismatch found — the entire first string is the common prefix
        # This happens when all strings start with strs[0] (e.g., all identical)
        return strs[0]

JavaScript

/**
 * @param {string[]} strs
 * @return {string}
 */
function longestCommonPrefix(strs) {
    // Edge case: empty input — no prefix possible
    if (!strs.length) return '';
 
    // Use the first string's characters as reference for each column
    for (let col = 0; col < strs[0].length; col++) {
        const char = strs[0][col];
 
        // Check all other strings at this column position
        for (let i = 1; i < strs.length; i++) {
            // Mismatch if: string is too short, or character differs
            if (col >= strs[i].length || strs[i][col] !== char) {
                // Prefix ends here — return everything before this column
                return strs[0].slice(0, col);
            }
        }
    }
 
    // All characters in strs[0] matched across every string
    return strs[0];
}

Approach 2 — Horizontal Fold (Reduce Left to Right)#

Start with the first string as the candidate prefix. For each subsequent string, shrink the prefix until it is a valid prefix of that string, or until the prefix becomes empty.

This approach is intuitive because it mirrors how you would solve the problem by hand: start with a guess (the full first string) and keep trimming until it fits every string you encounter.

Python

from typing import List
 
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # Start with the first string as our best guess for the prefix
        prefix = strs[0]
 
        # Refine the prefix against each subsequent string
        for s in strs[1:]:
            # Keep trimming from the right until s starts with our prefix
            # or until prefix is empty
            while not s.startswith(prefix):
                # Remove the last character from the candidate prefix
                prefix = prefix[:-1]
                # If we have trimmed everything, no common prefix exists
                if not prefix:
                    return ""
 
        return prefix

JavaScript

/**
 * @param {string[]} strs
 * @return {string}
 */
function longestCommonPrefix(strs) {
    // Seed the prefix with the first string
    let prefix = strs[0];
 
    for (let i = 1; i < strs.length; i++) {
        // Shrink prefix from the right until it matches the start of strs[i]
        while (!strs[i].startsWith(prefix)) {
            // Trim one character off the right end
            prefix = prefix.slice(0, -1);
            // Early exit if prefix is now empty
            if (!prefix) return '';
        }
    }
 
    return prefix;
}

Approach 3 — Binary Search on Prefix Length#

This approach uses a non-obvious observation: the valid prefix lengths form a monotone boolean sequence. If a prefix of length k works, all shorter prefixes also work. If a prefix of length k fails, all longer prefixes also fail. This means binary search applies.

This is the approach interviewers use to distinguish candidates who know binary search deeply from candidates who only apply it to sorted arrays. The predicate here has nothing to do with sorted order — it is a monotone property of prefix length.

Python

from typing import List
 
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
 
        # The prefix can be at most as long as the shortest string
        min_len = min(len(s) for s in strs)
 
        # Helper: check if all strings share a prefix of exactly `length` chars
        def is_common_prefix(length: int) -> bool:
            # Use the first string's prefix of this length as the candidate
            candidate = strs[0][:length]
            # Every string must start with this candidate
            return all(s.startswith(candidate) for s in strs)
 
        # Binary search on prefix length in [0, min_len]
        lo, hi = 0, min_len
 
        while lo <= hi:
            mid = (lo + hi) // 2
            if is_common_prefix(mid):
                # Length mid works — try longer
                lo = mid + 1
            else:
                # Length mid fails — try shorter
                hi = mid - 1
 
        # hi is the largest confirmed-working prefix length
        # (lo overshot by 1 when the loop ended)
        return strs[0][:hi]

JavaScript

/**
 * @param {string[]} strs
 * @return {string}
 */
function longestCommonPrefix(strs) {
    if (!strs.length) return '';
 
    // The prefix cannot be longer than the shortest string
    const minLen = Math.min(...strs.map(s => s.length));
 
    // Check whether a prefix of `length` characters is shared by all strings
    function isCommonPrefix(length) {
        const candidate = strs[0].slice(0, length);
        return strs.every(s => s.startsWith(candidate));
    }
 
    // Binary search the prefix length
    let lo = 0;
    let hi = minLen;
 
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (isCommonPrefix(mid)) {
            // This length works — search longer prefixes
            lo = mid + 1;
        } else {
            // This length fails — search shorter prefixes
            hi = mid - 1;
        }
    }
 
    // hi is the largest prefix length that passed the check
    return strs[0].slice(0, hi);
}

Bonus — Pythonic Vertical Scan with zip#

Python's zip(*strs) transposes the list of strings into columns, making the vertical scan almost a one-liner. This is worth knowing for Python interviews where conciseness signals fluency.

from typing import List
 
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # zip(*strs) stops at the shortest string — handles length mismatch automatically
        # Each `chars` is a tuple of characters at the same column across all strings
        for i, chars in enumerate(zip(*strs)):
            # If all characters in this column are not identical, the prefix ends here
            if len(set(chars)) > 1:
                return strs[0][:i]
 
        # All columns matched up to the length of the shortest string
        # Return the shortest string itself (it is a prefix of all others)
        return min(strs, key=len)

The key detail: zip(*strs) stops at the shortest string automatically, so min(strs, key=len) as the fallback correctly returns the shortest string when all strings share that full prefix.

Complexity Analysis#

Vertical Scan#

Horizontal Fold#

Binary Search on Length#

Comparison Summary#

The vertical scan is strictly optimal in both time and space. Binary search is slower by a log factor — but it demonstrates advanced pattern recognition that interviewers at Google and Meta reward specifically when they ask "can you think of another approach?"

Follow-up Questions#

These are actual escalations from Google and Meta interview reports. Each one tests a distinct concept.

Q1: What if the strings can be very long (megabyte-sized) but there are only a few of them?

The vertical scan remains optimal — it exits as soon as the first mismatch is found. If the common prefix is short (the typical case with long strings that diverge early), you pay very little cost. Horizontal fold performs similarly. Binary search on length is useful here specifically because it reads from the middle of each string first, potentially avoiding reading large chunks of disk or memory entirely if you are dealing with strings backed by lazy I/O.

Q2: What if the strings arrive as a stream, one at a time, and you need to maintain the current common prefix?

Maintain a running prefix variable initialized to the first string you receive. For each new string that arrives, run the horizontal fold comparison: shrink prefix until it is a valid prefix of the new string. The state after processing k strings is the LCP of those k strings. This is O(total characters processed) overall, O(m) space for the current prefix. This is exactly how autocomplete systems maintain prefix suggestions as users type — each new character narrows the prefix set.

Q3: What if you need to answer LCP queries for arbitrary pairs of strings from a large corpus efficiently?

This is where the Trie data structure enters. Build a trie from all strings. The LCP of any two strings is found by tracing from the root until their paths diverge — O(m) per query, O(n * m) to build. For repeated queries on large corpora, this preprocessing cost pays off. Suffix arrays with LCP arrays (the lcp array in suffix array construction) allow O(1) LCP queries after O(n log n) preprocessing.

Q4: What if all strings are guaranteed to be sorted lexicographically?

When strings are sorted, the LCP of the entire array equals the LCP of just the first and last string. Why? Because lexicographic sorting means every other string falls between the first and last string in character order — any column where the first and last string agree must also agree for all strings in between. This reduces the problem to a single pairwise comparison: O(m) time where m is the length of the shorter of the two boundary strings.

Q5: Can you solve this using divide and conquer?

Yes. Split the array in half. Recursively find the LCP of the left half and the LCP of the right half. Then find the LCP of those two results. This gives O(S) time overall (the work at each level of recursion sums to O(S)) and O(m log n) space due to the recursion stack. It is not faster than the iterative approaches but demonstrates a clean recursive decomposition that interviewers ask for explicitly to test whether you understand divide-and-conquer as a general paradigm.

This Pattern Solves#

The column-scan and monotone-binary-search techniques you learned here appear directly in these problems:

• LeetCode 720 — Longest Word in Dictionary: find the longest word buildable one character at a time — uses prefix membership, trie, or sorted prefix scanning
• LeetCode 1268 — Search Suggestions System: for each prefix of the search word, return the 3 lexicographically smallest strings that share that prefix — vertical scan plus sorted array slicing
• LeetCode 1858 — Longest Word With All Prefixes: a word is valid only if every prefix of it also exists in the dictionary — trie traversal using the same column-by-column thinking
• LeetCode 28 — Find the Index of the First Occurrence in a String: prefix matching in a rolling window — same "does this string start with this prefix?" predicate
• LeetCode 421 — Maximum XOR of Two Numbers in an Array: trie-based bit-by-bit (column-by-column) scan, the same spatial decomposition applied to binary representations

Key Takeaways#

• LeetCode 14 — Longest Common Prefix is an Easy problem asked at Google, Amazon, and Microsoft; it tests reframing skills — the problem is really a column-scan, not a string-comparison.
• Vertical scan (column by column across all strings) is O(S) time where S is the total characters — optimal and straightforward to explain.
• Horizontal fold (reduce prefix by comparing consecutive strings) is equivalent in complexity but easier to code in one line.
• Binary search on prefix length is O(S log m) — useful when the interviewer asks for a different approach; it demonstrates monotone predicate intuition.
• Key insight: "Is prefix of length k valid?" is monotone — once false, longer lengths are also false — enabling binary search outside sorted arrays.
• Common mistake: not handling the empty array edge case, which causes out-of-bounds on strs[0].
• Presents well as a three-approach progression: vertical scan → horizontal fold → binary search; that sequence signals engineering depth at Google's bar.