Skip to main content

14. Longest Common Prefix

easyAsked at JPMorgan

Given an array of strings, return the longest common prefix shared by all of them. JPMorgan asks this on Software Engineer Programme phone screens as a string-processing warm-up that doubles as a check on edge-case handling (empty list, single-string list, no common prefix).

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— JPMorgan SDE phone-screen reports list this as a recurring string warm-up.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Reddit r/cscareerquestions (2025-09)— JPMC SWE-I write-up: 'longest common prefix on the phone screen, then asked about Trie generalisation'.

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 if it is non-empty.

Examples

Example 1

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

Example 2

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

Explanation: No common prefix among the input strings.

Approaches

1. Vertical scan (optimal in time)

For each column index, check that every string has the same character at that index. Stop at the first mismatch or first end-of-string.

Time
O(S) where S is the sum of all characters across strings
Space
O(1)
function longestCommonPrefix(strs) {
  if (strs.length === 0) 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: O(S) worst case but typically much faster because it bails as soon as the first mismatch occurs — most realistic inputs share a short prefix. This is the answer JPMorgan interviewers expect.

2. Horizontal scan (intuitive baseline)

Take the first string as the candidate prefix. For each subsequent string, shrink the candidate until it is a prefix of that string.

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

Tradeoff: Same big-O but does more redundant work in the worst case (re-checks the full prefix each time). Slightly easier to explain on the whiteboard, so many candidates lead with it.

3. Binary search on prefix length

Binary search the prefix length in [0, min(len(strs))]. For each candidate length m, verify that all strings share strs[0][0..m).

Time
O(S log m)
Space
O(1)
function longestCommonPrefixBS(strs) {
  if (strs.length === 0) return '';
  let lo = 0;
  let hi = Math.min(...strs.map((s) => s.length));
  while (lo < hi) {
    const m = (lo + hi + 1) >> 1;
    const cand = strs[0].slice(0, m);
    if (strs.every((s) => s.startsWith(cand))) lo = m;
    else hi = m - 1;
  }
  return strs[0].slice(0, lo);
}

Tradeoff: Theoretically O(S log m) vs O(S) — strictly worse in big-O. Worth mentioning as a 'thinking out loud' option, not as the primary.

JPMorgan-specific tips

JPMorgan interviewers care about edge cases on this problem: empty input, single-string input, and 'one string is the prefix of another' (e.g. ['flower', 'flow']). State all three before coding and your solution will land them naturally. Many candidates write the loop and forget the 'i === strs[j].length' guard, which breaks the prefix-of-prefix case.

Common mistakes

  • Forgetting the 'string j has ended' guard inside the inner loop — index out of bounds.
  • Returning the first string when no mismatch is found but the input has only one string — works but tests sometimes expect the full first string only when n > 1.
  • Mutating the input array via sort to find the lexicographically smallest — works but mutates and is unnecessary.
  • Off-by-one when slicing: strs[0].slice(0, i) is correct because slice's end index is exclusive.

Follow-up questions

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

  • Longest common prefix when strings arrive in a stream (Trie insertion + prefix-collapse).
  • Longest common SUFFIX — symmetric problem, reverse and apply.
  • Find the shortest string that contains every input string as a substring.
  • Implement Trie (LC 208) and use it to answer prefix queries against a fixed dictionary.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is vertical scan typically faster than horizontal?

Vertical scan bails on the first mismatching column — most real inputs have a short common prefix, so this terminates quickly. Horizontal scan still has to traverse the whole first string to discover that fact. Asymptotically they are equal; in practice vertical wins by a large constant.

When would you prefer the Trie generalisation?

When you have a dictionary of strings and many prefix queries arrive over time. The Trie costs O(S) to build once and O(p) per query (where p is the query length). For a one-shot longest-common-prefix on a small array, the Trie is overkill.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →