Skip to main content

14. Longest Common Prefix

easyAsked at Apple

Longest Common Prefix is Apple's clean string-array warm-up. The vertical-scan answer (compare position 0 across all strings, then position 1, ...) beats the horizontal scan in average case and is what Apple grades on. Mention the trie variant if asked for a more reusable structure.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen reports list Longest Common Prefix as a recurring 10-minute string warm-up.
  • Blind (2025-11)— Apple new-grad reports cite Longest Common Prefix as a recurring easy.

Problem

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

Constraints

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

Examples

Example 1

Input
strs = ["flower","flow","flight"]
Output
"fl"

Example 2

Input
strs = ["dog","racecar","car"]
Output
""

Explanation: There is no common prefix among the input strings.

Approaches

1. Vertical scan (optimal)

For each position i, compare strs[0][i] against strs[j][i] for all j > 0. Stop at the first mismatch or end of any string.

Time
O(S) where S is sum of all chars (early termination)
Space
O(1)
function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  for (let i = 0; i < strs[0].length; i++) {
    const ch = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (i === strs[j].length || strs[j][i] !== ch) {
        return strs[0].slice(0, i);
      }
    }
  }
  return strs[0];
}

Tradeoff: Early-terminates on the first mismatching column. Best case (mismatch at column 0) is O(n). Worst case (all strings identical) is O(S). Apple prefers this version because it directly reflects the problem semantics.

2. Horizontal scan (pairwise reduce)

Take strs[0] as the running prefix. For each subsequent string, shorten the prefix until it matches.

Time
O(S)
Space
O(1)
function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1);
      if (!prefix) return '';
    }
  }
  return prefix;
}

Tradeoff: Cleaner code but the worst case (all strings share a long prefix then one short string at the end) does redundant work. Both versions pass.

3. Trie

Build a trie. Walk down until a node has either != 1 child or marks end-of-word.

Time
O(S) build + O(min length) query
Space
O(S)
// Build a standard trie, then walk root → as long as exactly one child and !isEnd, append.
// Code omitted for brevity in the interview — only sketch this if asked for a reusable structure.

Tradeoff: Useful if you'll do MANY prefix queries against the same set. Single query is overkill. Apple sometimes asks 'what if you had to do this 1000 times for different subsets?' — that's when trie wins.

Apple-specific tips

Apple is grading whether you pick the right scan direction. Vertical scan is the answer because it stops as soon as ANY string disagrees at column i — no wasted work. Horizontal scan reduces a running prefix string by string and keeps doing work even after we should have stopped. Articulate the difference; don't just write code.

Common mistakes

  • Forgetting the empty-array case (return '').
  • Forgetting the strs[j].length === i case in vertical scan — one string is a prefix of the others.
  • Doing prefix.slice(0, -1) when prefix is already empty — infinite loop.

Follow-up questions

An interviewer at Apple may pivot to one of these next:

  • Longest Common Prefix using divide-and-conquer (recursively).
  • If the strings were streamed (added one at a time), maintain a trie.
  • If the strings could be very long, sort and compare only first and last (after sort, longest common prefix of full array = lcp(first, last)).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Vertical or horizontal?

Vertical scan is the canonical answer. Same worst-case complexity but better average-case (stops at first divergent column).

What's the sort trick?

If you sort the array lexicographically, the lcp of the entire array equals the lcp of just the first and last strings. O(n log n) sort + O(min length) compare — useful if the array is huge and the prefix is short.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Longest Common Prefix and other Apple interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →