Longest Common Prefix
Understanding the Problem
A prefix of a string is any leading substring. For example, the prefixes of "flower" are "", "f", "fl", "flo", "flow", "flowe", and "flower". The longest common prefix (LCP) is the longest string that is a prefix of every string in the array.
Two properties bound the answer. Any string in the array can be empty, and an empty string shares no characters, so if even one string is "", the answer is "". And the LCP can never be longer than the shortest string in the array, since a prefix of a shorter string cannot exceed that string's length.
The challenge is comparing characters across all strings efficiently.
Key Constraints:
1 <= strs.length <= 200→ The array has at most 200 strings, so the total character count is small. Time complexity is not the binding concern here; any reasonable scan passes.0 <= strs[i].length <= 200→ A string can be empty, which forces an empty answer. Every approach must handle this case.- Only lowercase English letters → No unicode or special characters to handle.
Approach 1: Vertical Scanning
Intuition
Check the common prefix one character position at a time. Look at position 0 of every string. If they all match, move to position 1, and continue until a position where the characters differ or some string runs out of characters.
With the strings stacked as rows in a grid, this scans down each column. The prefix ends at the first column that is not uniform, or when the shortest string ends.
Algorithm
- If the array is empty, return
"" - For each character position
istarting from 0: - Get the character at position
ifrom the first string - For every other string in the array:
- If
iequals the length of that string (we've run past it), return the prefix so far - If the character at position
idoesn't match, return the prefix so far - If we get through all characters of the first string without stopping, the entire first string is the common prefix
Example Walkthrough
Code
- Time Complexity: O(S) where S is the sum of all characters in all strings. In the worst case (all strings are identical), we visit every character in every string exactly once. In the best case (the first character differs), we check one character per string.
- Space Complexity: O(1). We only use a few variables. The returned string doesn't count toward extra space.
Vertical scanning is already optimal in the worst case, since every character of the prefix has to be confirmed against every string at least once. The next approach uses a property of lexicographic order to avoid touching most strings at all.
Approach 2: Sorting
Intuition
If you sort the array of strings lexicographically, the first and last strings in sorted order are the two that differ earliest. Any prefix common to both of these extremes must also be common to every string between them.
This holds because sorting orders strings by their characters from left to right. If the first sorted string starts with "fl" and the last sorted string also starts with "fl", then every string between them starts with "fl" too, otherwise it would have sorted before the first or after the last. So instead of comparing all n strings, sort once and compare two.
Algorithm
- If the array is empty, return
"" - Sort the array of strings lexicographically
- Compare the first and last strings character by character
- The common prefix of these two strings is the answer
Example Walkthrough
Code
- Time Complexity: O(n m log n) where n is the number of strings and m is the average string length. Sorting performs O(n * log n) comparisons, and each comparison can scan up to O(m) characters. The final prefix scan adds O(m), which sorting dominates.
- Space Complexity: O(log n) for the sort's recursion stack, ignoring the output. The sort runs in place and mutates the input array.
Sorting reduces the work to two strings but pays the O(n m log n) sort cost. The next approach splits the array into halves and combines partial results, which is useful when the strings are spread across machines or computed in parallel.
Approach 3: Divide and Conquer
Intuition
The LCP of an array equals the LCP of two values: the LCP of the left half and the LCP of the right half. Formally, LCP(S1, ..., Sn) = LCP(LCP(S1, ..., Smid), LCP(Smid+1, ..., Sn)). This is associative because a prefix shared by every string in both halves is a prefix shared by every string overall.
Split the array until each piece is a single string (which is its own LCP), then combine results back up by finding the common prefix of two strings at each level. The structure mirrors merge sort: split, solve each half, combine.
Algorithm
- If the array is empty, return
"" - Call a recursive function
findLCP(strs, left, right): - Base case: If
left == right, returnstrs[left](a single string is its own prefix) - Divide: Find
mid = (left + right) / 2 - Conquer: Recursively find
lcpLeft = findLCP(strs, left, mid)andlcpRight = findLCP(strs, mid + 1, right) - Combine: Return the common prefix of
lcpLeftandlcpRight
Example Walkthrough
Code
- Time Complexity: O(S) where S is the sum of all characters across all strings. The base-case comparisons across one level total O(S), and the combine steps only compare characters that survive as prefixes, so they sum to at most O(S) as well. A short common prefix terminates comparisons early.
- Space Complexity: O(m * log n) where m is the length of the longest common prefix. The recursion depth is O(log n), and each active frame holds intermediate LCP strings of length up to m.