Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
A complete visual walkthrough of scanning strings character by character to find their shared beginning.
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 "".
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.
Constraints:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] consists of only lowercase English letters if it is non-empty.The most intuitive approach: scan column by column. Stack all the strings vertically and move a pointer from left to right, checking if every string has the same character at that position.
Given ["flower", "flow", "flight"], we stack the strings and scan each column:
At column 2, "flower" and "flow" have 'o' but "flight" has 'i'. The characters don't all match, so we stop. Everything before that column is the longest common prefix.
There are a few key observations that make this problem clean to solve:
strs[0] as the reference, then check if every other string matches it at each position.Alternative approach — sort first: If you sort the array lexicographically, the first and last strings will be the most different. You only need to compare those two to find the common prefix. Sorting costs O(S log n) though, so vertical scanning is usually better.
After sorting ["flower", "flow", "flight"] lexicographically:
The middle strings are irrelevant. If first and last share a prefix, all strings in between share it too (because of lexicographic ordering).
Let's trace through the vertical scanning algorithm step by step with ["flower", "flow", "flight"].
Take strs[0].charAt(0) = 'f' and compare against all other strings:
Take strs[0].charAt(1) = 'l' and compare:
Take strs[0].charAt(2) = 'o' and compare:
Early termination: The moment we find a mismatch at position i, we immediately return. We don't need to check any more columns or any more strings in that column. This is what makes vertical scanning efficient in practice.
Every good solution handles the boundaries. Here are the cases to watch for:
i == strs[j].length() immediately.The length check is crucial: The condition i == strs[j].length() fires before we try to access strs[j].charAt(i), preventing an index out of bounds. This naturally handles strings shorter than the first one.
The vertical scanning approach in its entirety. Clean, simple, and handles all edge cases:
class Solution { public String longestCommonPrefix(String[] strs) { // Guard: empty or null input if (strs == null || strs.length == 0) return ""; // Scan column by column, using strs[0] as reference for (int i = 0; i < strs[0].length(); i++) { // Character to match at column i char c = strs[0].charAt(i); // Check every other string at this column for (int j = 1; j < strs.length; j++) { // Two stop conditions: // 1. strs[j] is too short (ran out of characters) // 2. Character mismatch at position i if (i == strs[j].length() || strs[j].charAt(i) != c) { return strs[0].substring(0, i); } } } // All columns matched — strs[0] itself is the prefix return strs[0]; } }
func longestCommonPrefix(strs []string) string { // Guard: empty input if len(strs) == 0 { return "" } // Scan column by column, using strs[0] as reference for i := 0; i < len(strs[0]); i++ { // Character to match at column i c := strs[0][i] // Check every other string at this column for j := 1; j < len(strs); j++ { // Two stop conditions: // 1. strs[j] is too short (ran out of characters) // 2. Character mismatch at position i if i == len(strs[j]) || strs[j][i] != c { return strs[0][:i] } } } // All columns matched — strs[0] itself is the prefix return strs[0] }
class Solution: def longest_common_prefix(self, strs: list[str]) -> str: # Guard: empty input if not strs: return "" # Scan column by column, using strs[0] as reference for i in range(len(strs[0])): # Character to match at column i c = strs[0][i] # Check every other string at this column for j in range(1, len(strs)): # Two stop conditions: # 1. strs[j] is too short (ran out of characters) # 2. Character mismatch at position i if i == len(strs[j]) or strs[j][i] != c: return strs[0][:i] # All columns matched — strs[0] itself is the prefix return strs[0]
impl Solution { pub fn longest_common_prefix(strs: Vec<String>) -> String { // Guard: empty input if strs.is_empty() { return String::new(); } let first = strs[0].as_bytes(); // Scan column by column, using strs[0] as reference for i in 0..first.len() { // Character to match at column i let c = first[i]; // Check every other string at this column for j in 1..strs.len() { let other = strs[j].as_bytes(); // Two stop conditions: // 1. strs[j] is too short (ran out of characters) // 2. Character mismatch at position i if i == other.len() || other[i] != c { return strs[0][..i].to_string(); } } } // All columns matched — strs[0] itself is the prefix strs[0].clone() } }
function longestCommonPrefix(strs: string[]): string { // Guard: empty input if (strs.length === 0) return ""; // Scan column by column, using strs[0] as reference for (let i = 0; i < strs[0].length; i++) { // Character to match at column i const c = strs[0][i]; // Check every other string at this column for (let j = 1; j < strs.length; j++) { // Two stop conditions: // 1. strs[j] is too short (ran out of characters) // 2. Character mismatch at position i if (i === strs[j].length || strs[j][i] !== c) { return strs[0].substring(0, i); } } } // All columns matched — strs[0] itself is the prefix return strs[0]; }
Why use strs[0] as the reference? Any string could work, but using the first string is cleanest. The outer loop iterates over its characters, and the inner loop checks all other strings. If strs[0] happens to be longer than the actual prefix, the inner loop catches it early via the length or mismatch check.
Enter comma-separated strings and step through the algorithm column by column. Watch the character grid light up as each position is scanned.
Where n is the number of strings and m is the length of the shortest string. The outer loop runs at most m times (one per column), and the inner loop checks all n strings at each column. In the worst case (all strings identical), we examine every character once. In the best case, the first column already has a mismatch and we return immediately.
The outer loop scans up to m columns (length of the shortest string) and the inner loop checks all n strings at each column. Early termination at the first mismatch means it never revisits a character. Only an index variable and character reference are needed in memory.
Lexicographic sorting takes O(S log n) where S is the sum of all character lengths, since each string comparison costs up to O(m). After sorting, only the first and last strings need to be compared character by character. The sort itself requires O(S) auxiliary space for string copies.
Binary search on the prefix length performs O(log m) probes, and each probe verifies the candidate prefix across all n strings by comparing up to mid characters each, costing O(n × mid) per step. No extra data structures are needed, but the redundant re-checking makes it slower than vertical scanning.
Binary search on prefix length gives O(n × m × log m), which is worse. At each binary search step you still need to verify the candidate prefix across all n strings (O(n × mid) work), and you do O(log m) steps. Vertical scanning is already optimal -- it stops at the first mismatch and never revisits a character.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.