Skip to main content

21. Longest Common Prefix

easyAsked at Spotify

Find the longest common prefix string among an array of strings — the trie-based thinking here mirrors how Spotify's search autocomplete narrows song and artist suggestions as you type.

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

Problem

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.

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: No common prefix among all strings.

Approaches

1. Horizontal scan

Start with the first string as the candidate prefix; trim it until every other string starts with it.

Time
O(S) where S = total characters
Space
O(1)
function longestCommonPrefix(strs) {
  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:

2. Vertical scan

Compare characters column by column across all strings; stop at the first mismatch or end of any string. Exits early on short inputs.

Time
O(S)
Space
O(1)
function longestCommonPrefix(strs) {
  for (let col = 0; col < strs[0].length; col++) {
    const ch = strs[0][col];
    for (let row = 1; row < strs.length; row++) {
      if (col >= strs[row].length || strs[row][col] !== ch) {
        return strs[0].slice(0, col);
      }
    }
  }
  return strs[0];
}

Tradeoff:

Spotify-specific tips

Spotify evaluates this as a gateway to trie conversations. After solving it, expect a follow-up: 'How would you preprocess one million track names for prefix search?' If you can sketch a trie node structure on the spot, you advance to the next round.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →