Skip to main content

17. Longest Common Prefix

easyAsked at Dropbox

Find the longest prefix shared by every string in an array — Dropbox uses this pattern when collapsing shared directory prefixes to avoid redundant metadata transfers during a sync pass.

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 lowercase English letters only

Examples

Example 1

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

Explanation: All three strings share the prefix 'fl'.

Example 2

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

Explanation: No common prefix exists.

Approaches

1. Vertical scan

Check each character column across all strings simultaneously, stopping at the first mismatch or the shortest string length.

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

2. Sort then compare endpoints

Sort the array lexicographically; the longest common prefix of the whole array is exactly the common prefix of the first and last strings after sorting.

Time
O(S log n)
Space
O(1)
function longestCommonPrefix(strs) {
  strs.sort();
  const first = strs[0];
  const last = strs[strs.length - 1];
  let i = 0;
  while (i < first.length && first[i] === last[i]) i++;
  return first.slice(0, i);
}

Tradeoff:

Dropbox-specific tips

Dropbox interviewers often pivot this into a file-path context: 'Given a list of absolute paths, find the deepest shared ancestor directory.' Prepare to extend your solution to split on '/' and handle trailing slashes cleanly.

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 Dropbox interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →