EasyArrayStringTrieUpdated Sep 2026

14. Longest Common Prefix

Asked at Google, Meta, Oracle, Walmart and 1 more

Difficulty

Easy

Time

O(S)

Space

O(1)

Pattern

Array

Companies

5

Problem

You are given an array of strings strs. Return the longest common prefix shared by all of them.

A prefix is the start of a string. So a common prefix is a string that every string in the array begins with. If the strings start with different characters, there is no common prefix — return an empty string "".

If the array has only one string, that whole string is the answer, because a string is a prefix of itself. A string can also be empty, which makes the answer empty.

Find the shared start of every string

strs012345012flowerflowflightColumns 0 and 1 match everywhere. Column 2 has 'o','o', 'i' — that is the first mismatch.
Compare the strings column by column. The answer is the part before the first column where they disagree.

Constraints

  • ●1 <= strs.length <= 200
  • ●0 <= strs[i].length <= 200
  • ●strs[i] contains only lowercase English letters when it is not empty

Examples

Example 1
Inputstrs = ["flower","flow","flight"]
Output"fl"
WhyAll three strings start with 'f' and then 'l'. At index 2, "flower" and "flow" have 'o' but "flight" has 'i', so the shared part stops there.
Example 2
Inputstrs = ["dog","racecar","car"]
Output""
WhyThe first characters are 'd', 'r' and 'c'. They are not all the same, so there is no common prefix at all.

Asked At

5 companies
CompanyDifficulty
GoogleEasyView all Google questions →
MetaEasyView all Meta questions →
OracleEasyView all Oracle questions →
WalmartEasyView all Walmart questions →
BloombergEasyView all Bloomberg questions →

How to Think About It

1

Vertical scanning: take the first string as a reference. For each character position i, check if every other string has the same character at position i. Stop at the first mismatch. This is O(S) where S is the sum of all characters.

2

Why vertical scanning works: if the first string is "flower" and the second is "flow", compare character by character: f==f, l==l, o==o, w!=w... wait, "flower" and "flow" share "flo". At position 3, "flower" has 'w' and "flow" has 'w' -- actually they match. Position 4: "flower" has 'e', "flow" is out of bounds. Stop. Prefix = "flow".

3

Alternative: binary search on prefix length. The prefix can be at most as long as the shortest string. Check if the first half of that length is a common prefix. If yes, check the second half. This is O(S * log n) where n is the length of the shortest string.

4

The trie approach: insert all strings into a trie. Walk down from the root -- a node with only one child means the prefix continues. A node with multiple children means the prefix stops. This is elegant but overkill for an interview.

5

Edge cases: empty array returns "". Array with one string returns that string. No common prefix at all (first characters differ) returns "". Strings of different lengths -- prefix stops at the shortest one.

Optimal Approach

Step 1: If the array is empty, return "".
Step 2: Use the first string as the reference.
Step 3: For each character position i in the first string:

  • Check every other string at position i
  • If any string is shorter than i, or any string has a different character at i, stop
    Step 4: Return the prefix up to (but not including) position i.

Walkthrough for ["flower", "flow", "flight"]:

  • Reference: "flower" (length 6)
  • i=0: all strings have 'f' at index 0. Continue.
  • i=1: all strings have 'l' at index 1. Continue.
  • i=2: "flower" has 'o', "flow" has 'o', "flight" has 'i'. Mismatch! Stop.
  • Return "fl" (first 2 characters).

Time: O(S) where S is the sum of all characters across all strings. In the worst case, we check every character. Space: O(1) -- we only store the prefix index.

Vertical scanning with the first string as reference

strs012345012flowerflowflightColumn 0: 'f' in all three strings, so the prefix grows to "f".strs012345012flowerflowflightColumn 1: 'l' everywhere, so the prefix is "fl". Column 2 fails, sowe stop here.for i, ch in enumerate(strs[0]): if any string is too short or differs at i: return strs[0][:i]answer = "fl"
Walk down each column of the first string. Stop as soon as one string is too short or has a different letter.
ComplexityTime O(S)Space O(1)S is the total number of characters across all strings; we scan characters column by column and stop at the first mismatch, using no extra memory.

What Trips People Up in Real Interviews

1

Building a full trie for an interview. While correct, it's overkill. Vertical scanning is simpler, faster to code, and shows you can find the right tool for the job. Save trie for when the interviewer asks for a follow-up.

2

Sorting the array first to compare only the first and last strings. This works (O(n * k log n)) but is slower than vertical scanning (O(S)). Interviewers will ask why you sorted when a linear scan suffices.

3

Forgetting to handle strings of different lengths. If the reference string is longer than another string, you'll get an index out of bounds. Always check i < len(other_string) before comparing characters.

4

Using the first string as reference when a shorter string exists. While correct, consider using the shortest string as the reference to minimize comparisons. This is a micro-optimization but shows attention to detail.

5

Not handling the edge case where all strings are identical. In this case, the prefix is the entire shortest string. Make sure your loop completes without early termination and returns the full string.

Solution Code

O(S) time
def longestCommonPrefix(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        for s in strs[1:]:
            if i >= len(s) or s[i] != ch:
                return strs[0][:i]
    return strs[0]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Longest Common Prefix problem?

Find the longest common prefix string among an array of strings. If there is no common prefix, return an empty string. This problem tests string manipulation and can be solved with vertical scanning, `binary search`, or a `trie`.

How do you solve Longest Common Prefix?

The optimal approach runs in O(S) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Longest Common Prefix?

Longest Common Prefix is asked at Google, Meta, Oracle, Walmart, Bloomberg. It is a easy difficulty problem.

What are common mistakes on Longest Common Prefix?
  • Building a full `trie` for an interview. While correct, it's overkill. Vertical scanning is simpler, faster to code, and shows you can find the right tool for the job. Save `trie` for when the interviewer asks for a follow-up.
  • Sorting the array first to compare only the first and last strings. This works (`O(n * k log n)`) but is slower than vertical scanning (`O(S)`). Interviewers will ask why you sorted when a linear scan suffices.
  • Forgetting to handle strings of different lengths. If the reference string is longer than another string, you'll get an index out of bounds. Always check `i < len(other_string)` before comparing characters.
  • Using the first string as reference when a shorter string exists. While correct, consider using the shortest string as the reference to minimize comparisons. This is a micro-optimization but shows attention to detail.
  • Not handling the edge case where all strings are identical. In this case, the prefix is the entire shortest string. Make sure your loop completes without early termination and returns the full string.