LeetCode Solutions
#14 — Longest Common Prefix

Problem statement

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 "".

Example 1:

Example 2:

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters if it is non-empty.

The naïve way — horizontal scanning

The most intuitive approach is to take the first string as a candidate prefix, then iterate over the remaining strings. For each subsequent word, we shorten the candidate until it becomes a prefix of that word. This is called horizontal scanning because we move from left to right across the array, comparing the prefix with each string horizontally.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]          # Only one string → it's the prefix
        
        prefix = strs[0]
        
        for i in range(1, len(strs)):
            # Keep shortening prefix until it matches the start of strs[i]
            while strs[i].find(prefix) != 0:
                prefix = prefix[:-1]   # Remove last character
                if not prefix:
                    return ""          # No common prefix
        return prefix
            

Let's trace the example strs = ["flower","flow","flight"]:

This method is straightforward but may perform redundant comparisons. In the worst case, we could end up shortening the prefix character by character for each string, leading to O(S) time where S is the sum of all characters in all strings. Space is O(1) auxiliary.

A different angle — vertical scanning

Instead of comparing whole words, we can scan character by character vertically. We pick the first character of the first string and compare it with the first character of every other string. If all match, we move to the second character, and so on. The moment we find a mismatch or reach the end of any string, we stop and return the prefix built so far.

This approach can be more efficient in cases where the common prefix is short or a mismatch occurs early, because we avoid looking at the rest of the strings.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]
        
        # Scan characters of the first string
        for i in range(len(strs[0])):
            ch = strs[0][i]
            # Compare with every other string at position i
            for j in range(1, len(strs)):
                # Stop if we exceed length or find a mismatch
                if i == len(strs[j]) or strs[j][i] != ch:
                    return strs[0][:i]
        
        # All characters of first string matched in all others
        return strs[0]
            

Let’s trace strs = ["flower","flow","flight"] with vertical scanning:

Time complexity is still O(S) in the worst case (when all strings are identical), but often it performs fewer character comparisons. Space remains O(1).

Divide and conquer

This problem also lends itself nicely to a recursive divide‑and‑conquer strategy. The idea: split the array into two halves, find the LCP of each half recursively, and then find the LCP of those two results. This is a classic application of the paradigm and can be useful when we want to parallelize or when the array is large.

The helper function lcp(left, right) finds the common prefix between two strings using a vertical scan, and divide_and_conquer recursively splits the array.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(left: str, right: str) -> str:
            """Return the common prefix of two strings."""
            min_len = min(len(left), len(right))
            for i in range(min_len):
                if left[i] != right[i]:
                    return left[:i]
            return left[:min_len]

        def divide_and_conquer(arr, l, r):
            """Recursively find LCP in arr[l..r]."""
            if l == r:
                return arr[l]
            mid = (l + r) // 2
            left_lcp = divide_and_conquer(arr, l, mid)
            right_lcp = divide_and_conquer(arr, mid + 1, r)
            return lcp(left_lcp, right_lcp)

        return divide_and_conquer(strs, 0, len(strs) - 1)
            

Trace for strs = ["flower","flow","flight"]:

The recurrence relation for time complexity is T(n) = 2·T(n/2) + O(m), where m is the length of the strings. In the worst case this still results in O(S) total character comparisons. However, the divide‑and‑conquer approach has the advantage of being easily parallelizable and demonstrates a powerful algorithmic pattern.

Optimizing further — binary search

Can we do better than linear scans? If we consider the length of the common prefix, it is bounded by the length of the shortest string. We can perform a binary search on the possible prefix length. For a candidate length mid, we check whether the first mid characters of the first string form a valid common prefix for all strings. If yes, we try a longer length; if not, we try a shorter one.

This approach reduces the number of comparisons in many scenarios, especially when strings are long and the prefix is relatively short or long. The check itself (isLCP(mid)) iterates over the strings, making the overall time O(S·log m) where m is the length of the shortest string. This can be faster than linear scanning in practice.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isLCP(length: int) -> bool:
            """Check if the first `length` chars of strs[0] are common."""
            prefix = strs[0][:length]
            for s in strs[1:]:
                if not s.startswith(prefix):
                    return False
            return True

        if len(strs) == 1:
            return strs[0]

        low, high = 0, min(len(s) for s in strs)
        while low <= high:
            mid = (low + high) // 2
            if isLCP(mid):
                low = mid + 1      # Try a longer prefix
            else:
                high = mid - 1     # Try a shorter one

        return strs[0][:high]
            

Trace binary search for strs = ["flower","flow","flight"] where shortest length = 4 ("flow"):

The binary search solution elegantly narrows down the prefix length. Space complexity is O(1), and the startswith check uses efficient substring comparison.

Final complexity comparison

All four approaches are correct and run within the problem's constraints. Here's a quick summary:

• Horizontal scanning: O(S) time, O(1) space. Simple but may do extra work.
• Vertical scanning: O(S) time, O(1) space. Often stops early.
• Divide and conquer: O(S) time, O(m·log n) space due to recursion stack (or O(1) with iterative). Demonstrates recursion.
• Binary search: O(S·log m) time, O(1) space. Can be faster when strings are long and prefix length is extreme.

In an interview setting, the vertical scanning or binary search methods are particularly appreciated for their efficiency and clarity.

References & further reading

• LeetCode Longest Common Prefix Problem Page — official problem and discussion forums.
• Wikipedia: LCP array — related concept in suffix arrays.
• Wikipedia: Divide-and-conquer algorithm — the paradigm behind the recursive solution.
• Real Python: Strings and Character Data in Python — a deep dive into string operations like startswith().

Can't get enough from lumænaut? Read this...

• Chapter 2 | Everything I Don't Know About Blogging — the logbook behind the site: domains, SEO, plugins, and learning in public.
• The 8 Algorithm Paradigms — eight mental models you’ll keep reusing across problems, interviews, and production code.
• How the Game Loop Works — the heartbeat of a game frame: update, render, and steady timing in plain language.