Longest Common Prefix in C++ (LeetCode 14): Horizontal, Vertical, Sorting

The Problem Statement

Given: An array of strings. Task: Write a function to find the longest common prefix string amongst all the strings in the array. If there is no common prefix, return an empty string "".

Example:

• Input: strs = ["flower", "flow", "flight"]
• Output: "fl"
• Input: strs = ["dog", "racecar", "car"]
• Output: "" (No common prefix exists)

Approach 1: Horizontal Scanning (The Standard Way)

Intuition

Think of this like finding the common denominator. You take the first string and assume it's the longest common prefix. Then, you compare it with the second string and chop off characters from the end of your prefix until it matches the beginning of the second string. You repeat this updated prefix against the third string, and so on.

Algorithm

1. If the array is empty, return "".
2. Initialize prefix with the first string strs[0].
3. Loop through the remaining strings from index $1$ to $N-1$.
4. For each string, check if it starts with the prefix.
5. If it doesn't, remove the last character from prefix and check again.
6. If prefix becomes empty at any point, return "".
7. Return prefix after the loop completes.

c++ code:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestCommonPrefixHorizontal(vector<string>& strs) {
    if (strs.empty()) return "";
    
    string prefix = strs[0];
    
    for (int i = 1; i < strs.size(); i++) {
        // while strs[i] doesn't start with the prefix
        while (strs[i].find(prefix) != 0) {
            // shorten the prefix by 1 character from the end
            prefix = prefix.substr(0, prefix.length() - 1);
            if (prefix.empty()) return "";
        }
    }
    
    return prefix;
}

Dry run:

Complexity Analysis

• Time Complexity: $O(S)$, where $S$ is the sum of all characters in all strings. In the worst case, all strings are identical.
• Space Complexity: $O(1)$. We only use constant extra space to store the prefix pointer.

Approach 2: Vertical Scanning (The Fail-Fast Way)

Intuition

Instead of comparing whole strings horizontally, look at the array column by column. Check the $0^{th}$ character of every string. If they all match, check the $1^{st}$ character, and so on. This approach is superior when there is a very short string at the very end of the array, preventing you from needlessly processing long strings at the beginning.

Algorithm

1. If the array is empty, return "".
2. Iterate through the characters of the first string strs[0] using index i.
3. For each character, iterate through the rest of the strings strs[j].
4. If i equals the length of strs[j] (meaning we've reached the end of a string) OR if the character strs[j][i] doesn't match strs[0][i], return the substring of strs[0] up to i.
5. If the loop completes, the entire first string is the common prefix.

C++ Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestCommonPrefixVertical(vector<string>& strs) {
    if (strs.empty()) return "";
    
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0][i];
        
        for (int j = 1; j < strs.size(); j++) {
            // Check for mismatch or if we've reached the end of the current string
            if (i == strs[j].length() || strs[j][i] != c) {
                return strs[0].substr(0, i);
            }
        }
    }
    
    return strs[0];
}

Dry Run:

Complexity Analysis

• Time Complexity: $O(S)$ in the worst case (all strings are identical). However, in the best case (where the very first character mismatches), it's $O(N)$ where $N$ is the number of strings.
• Space Complexity: $O(1)$. Constant extra space used.

Approach 3: Sorting (The Elegant Trick)

Intuition

If you sort an array of strings lexicographically (alphabetically), the strings that share the least common prefix will end up at the extreme ends of the array. Therefore, the longest common prefix for the entire array is simply the common prefix between the first and the last string in the sorted array.

Algorithm

1. Sort the array of strings.
2. Grab the first string strs[0] and the last string strs[N-1].
3. Compare them character by character.
4. Stop when characters differ or you reach the end of the shorter string.
5. Return the matched portion.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string longestCommonPrefixSorting(vector<string>& strs) {
    if (strs.empty()) return "";
    
    // Sort the array lexicographically
    sort(strs.begin(), strs.end());
    
    string first = strs.front();
    string last = strs.back();
    int i = 0;
    
    // Compare first and last strings
    while (i < first.length() && i < last.length() && first[i] == last[i]) {
        i++;
    }
    
    return first.substr(0, i);
}

Dry Run

Input: ["flower", "flow", "flight"]

• Sort: ["flight", "flow", "flower"]
• First string: "flight"
• Last string: "flower"
• Compare:
  • Index 0: f == f
  • Index 1: l == l
  • Index 2: i != o. Mismatch.
• Result: Substring of "flight" up to index 2 $\rightarrow$ "fl"

Complexity Analysis

• Time Complexity: $O(N \cdot M \cdot \log N)$, where $N$ is the number of strings and $M$ is the maximum length of a string. String comparison takes $O(M)$ time, and sorting $N$ items takes $O(N \log N)$ comparisons. While technically slower theoretically than $O(S)$, standard library sorts are highly optimized and it runs incredibly fast in practice.
• Space Complexity: $O(\log N)$ or $O(N)$ depending on the language's sorting algorithm implementation (C++ std::sort uses Introsort, which requires $O(\log N)$ stack space).

Interview & OA Tips

• Watch the Hidden Test Cases: Online assessments are notorious for edge cases. Always explicitly handle strs.empty() == true or strs = [""]. Missing these will cause a segfault or out-of-bounds error on hidden tests.
• Start with Vertical Scanning: If asked to code this live, Vertical Scanning is often the most robust answer because it demonstrates you understand how to avoid unnecessary work (failing fast if a mismatch is found early).
• Use the Sorting Approach as a "Flex": If you solve it quickly with horizontal/vertical scanning, mention the sorting approach as a cool optimization alternative. It shows strong algorithmic thinking and deep familiarity with lexicographical properties.
• Discuss Trade-offs: Be ready to answer: "Which approach is better?"
  • If the array has millions of strings but the mismatch happens on the 2nd character: Vertical Scanning is best.
  • If the strings are incredibly long and mostly identical: Horizontal Scanning is highly cache-friendly.

code link:

https://leetcode.com/problems/longest-common-prefix/description/

video reference: