Longest Common Prefix: Four Ways and Which One to Say First

Longest Common Prefix (LeetCode 14) looks like a warm-up, and that is exactly why interviewers use it: they want to see whether you pick a clean approach quickly, state the complexity correctly, and handle edge cases without being prompted.

The problem

Given a list of strings, return the longest prefix they all share. ["flower","flow","flight"] gives "fl"; ["dog","racecar","car"] gives "".

1. Vertical scanning (say this first)

Compare character by character, column by column, and stop at the first mismatch or the end of the shortest string.

def longest_common_prefix(strs):
   if not strs:
       return ""
   first = strs[0]
   for i, ch in enumerate(first):
       for s in strs[1:]:
           if i == len(s) or s[i] != ch:
               return first[:i]
   return first

Time is O(S) where S is the total number of characters examined, and it stops early on the first mismatch. Space is O(1) beyond the output.

2. Horizontal scanning

Start with prefix = strs[0] and shrink it against each next string until that string starts with it. Same worst case, but one very short string late in the list makes it do extra work first.

3. Sort and compare the ends

Sort the list; the common prefix of the whole list equals the common prefix of the first and last strings in sorted order. It is short to write, but sorting costs O(n log n * m), so mention it as a neat trick, not the optimal answer.

4. Trie or divide and conquer

A trie makes sense when the follow-up is "many queries against the same set of strings." Divide and conquer splits the list in half and merges prefixes. Both are good to mention for follow-ups, overkill for the base question.

Edge cases to call out

How to present it in an interview

Lead with vertical scanning, state O(S) time and O(1) extra space, walk one example, then offer the sort trick and the trie as follow-ups. That ordering shows you know the trade-offs instead of reciting one memorized answer.

If you practice these explanations out loud, a tool like Linkjob AI's interview copilot app can help you rehearse structured answers for live coding rounds. (Disclosure: I work on Linkjob AI.)

‍