Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the longest string that is a prefix of every string in the array. The cleanest answer is vertical scanning: walk column 0, 1, 2… of the first string and check that same column matches in every other string; stop at the first mismatch or the first string that runs out. O(S) time where S is the total number of characters.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you handle the messy edge cases (empty array, empty string, single string) cleanly and pick a simple linear scan instead of over-engineering — and whether you can articulate why the answer is bounded by the shortest string.
Where candidates slip
Dereferencing `strs[0]` before checking the array is non-empty, or looping past the end of a shorter string and throwing an index error.
How to stand out
State the shortest-string bound up front, write the clean vertical scan, then mention that binary search on the prefix length (O(S log m)) and divide-and-conquer exist as alternatives — without claiming they beat O(S).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFind shared text across many stringsAnchored at index 0?No, substring anywhereYes, true prefixExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Vertical Scanning (Optimal)
1Hint 1Explore hintHide hint
The answer can never be longer than the shortest string — so you only ever look at columns 0 through (shortest length − 1). What do all strings have to agree on at each column?
2Hint 2Explore hintHide hint
Fix a column index i. Take the character at position i in the first string, then check every other string has the same character at position i. The first column that fails ends the prefix.
3Hint 3Explore hintHide hint
Two ways a column fails: some string is too short to have an index i at all, or it has a different character there. Both mean 'stop and return strs[0] up to i'.
A · Core idea
Picture the strings stacked on top of each other, aligned at the left edge, like rows in a table. The longest common prefix is the widest block of fully-matching columns starting from column 0. Vertical scanning walks those columns left to right and stops at the first one that isn't unanimous.
Why we anchor on `strs[0]`. The prefix, if it exists, is a prefix of every string — including the first one. So strs[0] is a perfectly good reference: its character at column i is the candidate, and we only need to verify the other strings agree. There's no need to maintain a separate growing buffer; we just remember how far we got and slice strs[0] once at the end.
The two ways a column dies. For column i, a string s breaks the prefix in exactly two situations: either i == len(s) — s simply ran out of characters and can't extend the prefix any further — or s[i] != c — s has a character here but it's the wrong one. Folding both into a single if (i == len(s) || s[i] != c) is what makes the inner loop both correct and tidy. The i == len(s) half is precisely the shorter-string cutoff, handled for free without computing the minimum length up front.
Why this is the answer interviewers want. It's O(S) — you can't do better than reading the shared characters at least once — it uses O(1) extra space, and it makes the edge cases obvious rather than hidden. The empty-array guard is the only ceremony; after that, an empty string in the input ends the scan at column 0 automatically, and a single-element array returns that element unchanged. Simple, linear, and boundary-safe.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
strs = ["flower", "flow", "flight"]Interactive diagram
Why a column dies
i=0, c='f'Each column must be unanimous. The scan ends at the first column that isn't — either a mismatch or a string that ran out.
"fl"C · Code with teaching comments
D · Why it works and complexityO(S) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The shorter-string cutoff and the character-mismatch are the same event — 'this column is not unanimous' — so they belong in one condition. Candidates who write a separate Math.min length pre-pass aren't wrong, but the i == len(s) check inside the loop is strictly cleaner and proves you understand the invariant.
ComplexityO(S) time, O(1) space — In the worst case (all strings identical) we touch every character once: S = sum of all lengths. No buffer is built, so extra space is O(1) beyond the output.
E · Edge cases and pitfalls6strs = ["", "abc"] — len(strs[0]) is 0, so the outer loop body never runs → return "" (the whole first string).Explore edge casesHide edge cases
Edge cases handled
strs = ["", "abc"]len(strs[0]) is 0, so the outer loop body never runs → return "" (the whole first string).strs = ["abc"]Only one string; the inner loop never runs, every column passes → return "abc".strs = ["abc", "ab"]At i=2, i == len("ab") triggers the shorter-string cutoff → return "ab".
Pitfalls
- Indexing strs[0] before the empty-array guard — throws on strs = [].
- Testing s[i] before i == len(s) — raises IndexError / StringIndexOutOfBounds on a shorter string.
- Returning strs[0].substring(0, i+1) instead of (0, i) — off-by-one that includes the failing column.
Approach 2 of 2
Binary Search on Prefix Length (Alternative)
1Hint 1Explore hintHide hint
The set of valid prefix lengths is monotonic: if a prefix of length L is common to all strings, then so is every shorter length. That monotonic boundary is exactly what binary search exploits.
2Hint 2Explore hintHide hint
Let m be the shortest string's length. Binary search the largest L in [0, m] such that strs[0][0:L] is a prefix of every string.
3Hint 3Explore hintHide hint
For a candidate length mid, checking 'is this a common prefix?' costs O(n·mid). Wrap that in a binary search over L to get O(S log m).
A · Core idea
This approach reframes the problem as a search over the answer's length rather than a scan over characters. The key observation is monotonicity: if all strings share a prefix of length L, they automatically share every prefix shorter than L; and if they fail to share a prefix of length L, they fail every longer one too. That yes-then-no boundary is the classic setup for binary search.
How the search runs. We bound the answer to [0, m] where m is the shortest string's length — nothing longer can be common. We binary search the largest mid for which strs[0][0:mid] is a prefix of all strings. If mid works, the answer is at least mid, so we move the low bound up; if it fails, the answer is below mid, so we drop the high bound. We use the (lo + hi + 1) / 2 midpoint to bias upward and avoid an infinite loop when lo and hi are adjacent.
Why it isn't actually faster. The per-check cost is O(S) and we run O(log m) checks, so the total is O(S log m) — worse than the vertical scan's O(S) by a logarithmic factor. The win, if any, is when the common prefix is short and strings are long: binary search may bail after touching fewer characters on average. But the worst case is genuinely slower, so present this as a discussion point, not an upgrade.
The cousin: divide-and-conquer. A third option splits the array in half, recursively computes the LCP of each half, and merges by taking the common prefix of the two results. It's also O(S) total and parallelizes nicely, but for an interview it's strictly more code than the vertical scan for the same big-O. Naming both binary search and divide-and-conquer signals breadth; coding the vertical scan signals judgment.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
strs = ["flower", "flow", "flight"]lo=0, hi=4
mid=(0+4+1)/2=2 → "fl" common? yes
lo=2, hi=4"fl"C · Code with teaching comments
Reference implementation previewpublic String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; int minLen = Integer.MAX_VALUE; for (String s : strs) minLen = Math.min(minLen, s.length()); int lo = 0, hi = minLen;Explore the full codeHide the full code
D · Why it works and complexityO(S log m) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The unlock is recognizing that 'valid prefix lengths' form a monotonic predicate (true, true, …, true, false, …, false). Any time a property flips exactly once along an axis, binary search the flip point — that mental trigger is far more reusable than this specific problem.
ComplexityO(S log m) time, O(1) space — Each isCommonPrefix check scans up to n strings × mid chars = O(S). We do O(log m) such checks, giving O(S log m). No extra structures → O(1) space.
E · Edge cases and pitfalls5strs = ["abc", ""] — min_len = 0 → hi = 0, loop never runs → return "".Explore edge casesHide edge cases
Edge cases handled
strs = ["abc", ""]min_len = 0 → hi = 0, loop never runs → return "".strs = ["abab", "aba", "abc"]Monotonic boundary lands at length 2 → "ab".
Pitfalls
- Using (lo + hi) / 2 with the lo = mid update — infinite loop when hi = lo + 1.
- Forgetting the empty-array / empty-string guard, so min_len or substring(0, len) misbehaves.
- Claiming this beats the vertical scan — it's O(S log m), strictly worse in the worst case.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; for (int i = 0; i < strs[0].length(); i++) { char c = strs[0].charAt(i); for (int j = 1; j < strs.length; j++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1No empty-array guard
Every solution dereferences strs[0]. With strs = [], that throws ArrayIndexOutOfBounds (Java) or IndexError (Python) before any logic runs.
Explore the code comparisonHide the code comparison
No empty-array guard
Every solution dereferences strs[0]. With strs = [], that throws ArrayIndexOutOfBounds (Java) or IndexError (Python) before any logic runs.
Don't write this
public String longestCommonPrefix(String[] strs) {
for (int i = 0; i < strs[0].length(); i++) { // throws if strs is empty
// ...
}
}Write this instead
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
// ...
}
}2Indexing a shorter string out of bounds
Checking the character before the length means a string that is shorter than the current column index throws instead of cleanly ending the prefix.
Explore the code comparisonHide the code comparison
Indexing a shorter string out of bounds
Checking the character before the length means a string that is shorter than the current column index throws instead of cleanly ending the prefix.
Don't write this
for s in strs[1:]:
if s[i] != c or i == len(s): # s[i] evaluated first → IndexError
return strs[0][:i]Write this instead
for s in strs[1:]:
if i == len(s) or s[i] != c: # length check short-circuits first
return strs[0][:i]3Off-by-one in the returned slice
i is the first column that FAILED, so the agreed prefix is [0, i). Slicing to i+1 sneaks the failing column into the answer.
Explore the code comparisonHide the code comparison
Off-by-one in the returned slice
i is the first column that FAILED, so the agreed prefix is [0, i). Slicing to i+1 sneaks the failing column into the answer.
Don't write this
return strs[0].substring(0, i + 1); // includes the mismatching columnWrite this instead
return strs[0].substring(0, i); // excludes the column that failedRevise
Carry the pattern into the interview
Pattern to remember
Character-by-character agreement (vertical scan)
Code pattern to memorize
if array empty: return ""
for i in 0..len(strs[0]):
c = strs[0][i]
for s in strs[1:]:
if i == len(s) or s[i] != c:
return strs[0][:i] # mismatch or shorter string
return strs[0] # first string is the whole prefixRules to remember
- 1Handle the empty array first.
strs = []must return""— dereferencingstrs[0]without this guard throws. - 2Stop the moment a string runs out. When the column index
iequals some string's length, the prefix can't grow pasti— returnstrs[0][0..i]. - 3The answer can never be longer than the shortest string. That's the loop bound and the key invariant.
- 4A single empty string in the array forces the answer to `""`.
["", "abc"]→"", because column 0 already runs out. - 5Compare against the first string, not a running buffer you rebuild. Slicing
strs[0]once at the end is cheaper and clearer than appending char by char.
Use this pattern when
- You need the shared leading characters across a set of strings
- The match must be a true prefix — anchored at index 0, not a substring anywhere
- Autocomplete / routing / file-path collapsing where common roots matter
- Input is a list of strings and order doesn't matter to the answer
Choose another pattern when
- Need the longest common *substring* (anywhere) → DP or suffix structures, not a prefix scan
- Need the longest common *subsequence* → 2-D DP
- Matching one pattern against many strings repeatedly → build a Trie instead
- Only two strings and you want suffix overlap → that's a different (Z/KMP) problem
Interview takeaway
Longest Common Prefix is the gentlest 'compare strings column by column' problem. Vertical scanning is the interview-grade answer; the binary-search and divide-and-conquer variants are nice to *name* but rarely worth coding unless asked. The real skill being tested is careful boundary handling: empty array, empty string, and the shorter-string cutoff.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternVertical character agreement across multiple strings. The same column-by-column thinking shows up in any 'what do all these strings share at the front?' task, and the Trie generalizes it when you need repeated prefix queries. Binary-search-on-answer and divide-and-conquer are reusable templates worth recognizing even though the linear scan wins here.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Implement Trie (Prefix Tree)Coming soonIf you'll answer many prefix queries, build a Trie once; the LCP is the longest single chain before a branch.
- Design Add and Search WordsComing soonTrie with wildcard matching — extends prefix thinking to pattern queries.
- Longest Word in DictionaryComing soonTrie / sort-and-set; a word is buildable only if all its prefixes exist.