Longest Common Prefix LeetCode 14 Guide

LeetCode 14, Longest Common Prefix, asks you to find the longest prefix string that is shared by all strings in an input array. A prefix is any leading substring of a string — for example the longest common prefix of ["flower", "flow", "flight"] is "fl". If the array is empty or no common prefix exists, return an empty string.

The problem is classified as Easy but it rewards knowing multiple approaches. Naive character-by-character comparison across all strings is O(n * m) where n is the number of strings and m is the length of the shortest string. Understanding why this bound is tight — and when sorting or binary search can give you a cleaner implementation — is what separates a rote solution from a deep understanding.

This problem is a gateway to string prefix problems including Trie construction, autocomplete systems, and prefix-based search. Every approach below runs in O(n * m) time in the worst case, but they differ in code clarity and constant factors depending on the input distribution.

Vertical scanning iterates column by column across all strings. For each position index i, compare strs[0][i] with strs[j][i] for all other strings j. If any string is shorter than i+1 characters or any character differs from strs[0][i], return the prefix built so far — strs[0][:i] in Python or strs[0].substring(0, i) in Java.

This approach is the most intuitive because it mirrors how a human would visually scan a table of strings column by column. It naturally handles the edge case of an empty string in the array: when i reaches the length of any string, that string has no character at column i, and we must stop. The prefix at that point is the answer.

Vertical scanning processes characters in column-major order. In the best case — when the first column already has a mismatch — it examines only n characters total. In the worst case — all strings are identical — it examines n * m characters. No comparisons are wasted: as soon as any mismatch is found, the algorithm terminates immediately without looking at remaining columns.

Horizontal reduction applies the identity LCP(s1, s2, ..., sn) = LCP(LCP(s1, ..., sn-1), sn). Start with prefix = strs[0] and iteratively shrink it by comparing with each subsequent string. For each new string, trim prefix from the right until it matches the beginning of that string, then move to the next.

The inner loop uses Python's startswith or Java's startsWith to check if the current string begins with the current prefix. If not, trim one character from the end of prefix and check again. Repeat until prefix is empty (return "") or the current string starts with prefix. This gives O(n * m) time and O(m) extra space for the prefix variable.

Horizontal reduction is row-major: it processes one string at a time. It may scan more characters than vertical scanning when the common prefix is very short, because startsWith must check up to len(prefix) characters on each iteration. However, it is often cleaner to read and reason about, especially when the problem involves streaming strings one at a time.

The sort-based approach exploits the fact that after lexicographic sorting, the longest common prefix of the entire array must equal the longest common prefix of just the first and last strings. This is because any character that differs between the lexicographic minimum and maximum must differ somewhere among all strings in between.

Sort strs lexicographically, then compare only strs[0] and strs[-1] character by character. The first position where they differ (or where either string ends) gives the length of the common prefix. Return strs[0][:i] at that point. This reduces an n-string comparison to a two-string comparison after sorting.

The sort step costs O(n * m * log n) in the worst case — each string comparison during sort is O(m). The subsequent two-string comparison is O(m). So the total is O(n * m * log n), which is worse than the O(n * m) of vertical scanning. However, the code is often cited as elegant and is worth knowing for interviews as a demonstration of creative reduction.

Binary search on the length of the answer offers a fourth approach. The minimum possible prefix length is 0 and the maximum is min(len(s) for s in strs). Binary search on this range: for a candidate length mid, check whether all strings share the prefix strs[0][:mid]. If yes, the true prefix length is at least mid; if no, it is less than mid.

The isCommonPrefix check costs O(n * mid) — compare mid characters across all n strings. Binary search runs O(log m) iterations where m is the length of the shortest string. Total complexity is O(n * m * log m), which is worse than the O(n * m) vertical scan. Binary search on prefix length is theoretically interesting but rarely the best choice in practice.

The key insight for the binary search approach is that the prefix length is monotone: if all strings share a prefix of length k, they also share all shorter prefixes. This monotone property is what makes binary search applicable. Recognizing monotone structure in string problems and applying binary search is a general pattern that appears in harder string problems.

Python vertical scanning: zip(*strs) is the cleanest idiom — it transposes the list of strings into an iterator of tuples, one per column. For col in zip(*strs): if len(set(col)) > 1: return strs[0][:index]. Alternatively iterate with enumerate. If zip exhausts without a mismatch, return the shortest string (the zip stops at the shortest). This is O(n * m) time and O(1) extra space beyond the set per column.

Java vertical scanning: for (int i = 0; i < strs[0].length(); i++) { char c = strs[0].charAt(i); for (String s : strs) { if (i >= s.length() || s.charAt(i) != c) return strs[0].substring(0, i); } } return strs[0]. This is clean, handles empty strings inside the loop, and runs in O(n * m) time and O(1) space (excluding the output string).

Both implementations are compact and directly express the vertical scanning idea. The Python zip(*strs) version is idiomatic and very readable; the Java explicit loop version is verbose but unambiguous. In an interview, either style is acceptable — what matters is correctly handling the edge cases and explaining the time complexity.

Longest Common Prefix belongs to the string prefix and comparison family. Encode and Decode Strings (LeetCode 271) also requires careful character-by-character string processing and handling delimiter edge cases. Group Anagrams (LeetCode 49) applies a different kind of string normalization — sorting characters — to group strings, showing that sorting strings has multiple uses beyond lexicographic ordering.

Implement Trie (LeetCode 208) is the direct follow-up: a Trie is a data structure built for prefix queries at scale. Every path from the root to a node in a Trie represents a prefix, and the depth of the common prefix root gives the LCP length. Building a Trie from all strings and finding the deepest node with a branching factor > 1 gives the LCP. This generalizes vertical scanning to a persistent, queryable prefix structure.

The broader string prefix family includes problems like Add and Search Word (LeetCode 211), Word Search II (LeetCode 212), and Design Search Autocomplete System (LeetCode 642). Mastering LCP with vertical scanning gives you the intuition to reason about prefix operations efficiently — whether the answer is a plain loop, a Trie, or a suffix array depending on the query type and scale.