Longest Common Prefix - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: Given an array of strings, return the longest prefix shared by every string. If the strings have no common starting characters, return an empty string. The challenge is efficiently comparing characters across multiple strings without unnecessary repeated work.
Approach 1: Horizontal Scanning (Time: O(S), Space: O(1))
Start with the first string as the candidate prefix. Iterate through the remaining strings and shrink the prefix until it matches the start of the current string. This works by repeatedly checking whether strs[i].startsWith(prefix); if not, remove the last character from the prefix and try again. The key insight: the prefix can only become shorter as you compare more strings. Since each character across all strings is examined at most once, the total cost is proportional to the total number of characters S. This approach uses simple iteration over the array and is the most practical solution for typical string interview problems.
Approach 2: Divide and Conquer (Time: O(S), Space: O(m log n))
Treat the problem similarly to merge operations. Split the array of strings into two halves, recursively compute the longest common prefix for each half, then merge the results by comparing characters of the two prefixes. The merge step scans character by character until a mismatch occurs. The insight is that computing prefixes for smaller groups reduces redundant comparisons across the entire list. This approach uses divide and conquer with recursion and performs the same total amount of character comparisons as horizontal scanning, resulting in O(S) time where S is the total number of characters across all strings.
Approach 3: Trie-Based Prefix Search (Time: O(S), Space: O(S))
Insert all strings into a Trie. After construction, walk down the Trie from the root while there is exactly one child and the node is not marked as the end of a word. Each step represents a shared prefix character. The traversal stops when branching occurs or a word terminates. The collected characters form the longest common prefix. While conceptually clean and useful when solving multiple prefix queries, it requires additional memory proportional to the total characters stored.
Recommended for interviews: Horizontal scanning is the expected answer in most interviews because it is simple, readable, and runs in optimal O(S) time with constant extra space. Divide and conquer demonstrates stronger algorithmic thinking and recursion skills. A Trie solution is rarely required but shows deeper knowledge of prefix-based data structures.
Approach 1: Horizontal Scanning
In this approach, you start with the first string as a reference and gradually compare it with each subsequent string in the array. The reference prefix is shortened until it matches the prefixes of all strings.
This implementation starts by taking the first string as the initial prefix. It iteratively checks if this prefix is valid for each string, adjusting it until all strings have a common start. If a mismatch occurs, we shorten the prefix from the end.
Complexity
Time Complexity: O(S), where S is the sum of all characters in all strings.
Space Complexity: O(1), as we are using constant extra space.
Approach 2: Divide and Conquer
This approach involves dividing the array of strings into two halves, recursively finding the longest common prefix for each half, and merging the results. The merge step compares characters from the two strings to find the common prefix.
This C solution reduces the problem into finding the longest common prefix of smaller sections, leading to a combination of results using a helper function to merge prefixes by character comparison.
Complexity
Time Complexity: O(S), where S is the sum of all characters in the strings.
Space Complexity: O(M*logN), where M is the length of the common prefix and N is the number of strings.
Approach 3: Character Comparison
We use the first string strs[0] as a benchmark, and compare whether the i-th character of the subsequent strings is the same as the i-th character of strs[0]. If they are the same, we continue to compare the next character. Otherwise, we return the first i characters of strs[0].
If the traversal ends, it means that the first i characters of all strings are the same, and we return strs[0].
The time complexity is O(n times m), where n and m are the length of the string array and the minimum length of the strings, respectively. The space complexity is O(1).
Code
Complexity Comparison
| Approach | Complexity |
|---|---|
| Horizontal Scanning | Time Complexity: O(S), where S is the sum of all characters in all strings. |
| Divide and Conquer | Time Complexity: O(S), where S is the sum of all characters in the strings. |
| Character Comparison | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Horizontal Scanning | O(S) | O(1) | Best general solution. Simple iteration across strings with minimal memory. |
| Divide and Conquer | O(S) | O(m log n) | Useful when practicing recursive problem decomposition. |
| Trie-Based Approach | O(S) | O(S) | Helpful when many prefix queries are required on the same dataset. |
Video Solution
Longest Common Prefix - Leetcode 14 - Python • NeetCode • 312,186 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Common Prefix easy or hard?
Longest Common Prefix Python/Java solution
How to solve Longest Common Prefix in O(n)?
What is the best approach for Longest Common Prefix?
Is Longest Common Prefix asked at Google/Amazon/Meta?
What data structure is used in Longest Common Prefix?
What is the time complexity of Longest Common Prefix?
Ready to solve this problem?
Practice Longest Common Prefix with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor