Log inSign up
easyleetcodeNot Started

Longest Common Prefix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

Input: strs = ["flower","flow","flight"]
Output: "fl"
Explanation: "fl" is the longest prefix shared by all three strings.

Example 2 · Example:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master vertical matrix-like scanning across arrays of variable length strings.
  • Prevent out-of-bounds exceptions via guarded column comparisons.
  • Understand the sorting extremal comparison shortcut.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding shared initial segment across a collection of words.
  • Prefix reduction and Trie common ancestral paths.

Algorithmic Decision Tree:

  • Vertical Scanning
  • Horizontal Reduction
  • Lexicographical Boundary Comparison

Connected Patterns:

Longest Palindromic SubstringImplement TrieLongest Prefix Suffix

1. Horizontal Scanning (Pairwise Prefix Reduction)

Intuition

Set prefix = strs[0]. Iterate i from 1 to strs.length - 1: while strs[i] does not start with prefix, remove the last character from prefix. If prefix becomes empty, return "". Return prefix.

When to apply: Basic functional reduction approach.

Algorithm

  1. If strs is empty, return "".
  2. Set prefix = strs[0].
  3. For i from 1 to strs.length - 1:
  4. While strs[i].indexOf(prefix) != 0:
  5. prefix = prefix.substring(0, prefix.length - 1)
  6. If prefix is empty: return "".
  7. Return prefix.

Horizontal Scanning Pairwise Prefix Reduction Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [flower, flow, flight]
Current operationSTEP 1 OF 6
Observation: Take the first string strs[0] = "flower" as the initial candidate prefix
Visual state
Values and pointers at this exact step
array
S
flower
flow
flight
0
1
2
Variables at this step
Initial Prefix
flower
Length
6
String Index
0
Check / comparison
Initialize prefix = strs[0] = "flower".
Decision / next transition
Compare candidate prefix against each subsequent string in array.
Why this step matters

Observation: Take the first string strs[0] = "flower" as the initial candidate prefix.

Decision: Sequentially compare this prefix against strs[1] and strs[2], trimming characters from the end until it matches.

Invariant: Prefix is monotonically non-increasing in length.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string longestCommonPrefix(std::vector<std::string>& strs) {
8 if (strs.empty()) return "";
9 std::string prefix = strs[0];
10 for (size_t i = 1; i < strs.size(); ++i) {
11 while (strs[i].find(prefix) != 0) {
12 prefix = prefix.substr(0, prefix.size() - 1);
13 if (prefix.empty()) return "";
14 }
15 }
16 return prefix;
17 }
18};
19
20int main() {
21 Solution sol;
22 std::vector<std::string> strs = {"flower","flow","flight"};
23 std::cout << sol.longestCommonPrefix(strs) << std::endl; // "fl"
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(S) where S is the total number of characters in all strings — In the worst case, all strings are identical and we compare all S characters.
  • Space complexity: O(1) auxiliary space

Why Brute Force Doesn't Scale:

Vertical column scanning short-circuits at the minimum prefix divergence point.

Operates in O(1) auxiliary space without constructing intermediate prefix buffers.

2. Sorting Extremals (First and Last)

Intuition

Sort the array of strings lexicographically. The most divergent strings will be placed at index 0 (first) and index n - 1 (last). The common prefix between first and last is guaranteed to be the common prefix for every string in the array.

When to apply: Compact and elegant formulation.

Algorithm

  1. If strs is empty, return "".
  2. Sort strs lexicographically.
  3. Let first = strs[0], last = strs[strs.length - 1].
  4. Loop i from 0 to min(first.length, last.length) - 1:
  5. If first[i] != last[i]: return first.substring(0, i).
  6. Return first.

Sorting Extremals First & Last String Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [flight, flow, flower]
Current operationSTEP 1 OF 6
Observation: After lexicographical sorting, strings that share the longest prefix appear adjacent
Visual state
Values and pointers at this exact step
array
S
flight
flow
flower
0
1
2
Variables at this step
First
flight
Last
flower
Middle Ignored
flow
Check / comparison
Sort strs array lexicographically: ["flight", "flow", "flower"].
Decision / next transition
Common prefix is strictly bounded by first and last sorted strings.
Why this step matters

Observation: After lexicographical sorting, strings that share the longest prefix appear adjacent. The common prefix of ALL strings is strictly bounded by comparing only first = strs[0] and last = strs[N-1].

Decision: Compare only "flight" and "flower".

Invariant: Any character common to both first and last must be shared by all intermediate strings.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 std::string longestCommonPrefix(std::vector<std::string>& strs) {
9 if (strs.empty()) return "";
10 std::sort(strs.begin(), strs.end());
11 std::string first = strs.front(), last = strs.back();
12 int i = 0;
13 while (i < (int)first.size() && i < (int)last.size() && first[i] == last[i]) {
14 i++;
15 }
16 return first.substr(0, i);
17 }
18};
19
20int main() {
21 Solution sol;
22 std::vector<std::string> strs = {"flower","flow","flight"};
23 std::cout << sol.longestCommonPrefix(strs) << std::endl; // "fl"
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N * M log N) where N is number of strings and M is max string length — Sorting N strings takes O(M * N log N). Comparing first and last takes O(M).
  • Space complexity: O(1) auxiliary

3. Vertical Scanning (Column-by-Column)

Intuition

Loop column index i from 0 to strs[0].length - 1. Let c = strs[0][i]. For every other string strs[j] from j = 1 to strs.length - 1: if i == strs[j].length (the string is shorter) or strs[j][i] != c (character mismatch), return strs[0].substring(0, i). If all columns in strs[0] match across all strings, return strs[0].

When to apply: Optimal benchmark solution with minimal character inspections and zero auxiliary allocations.

Algorithm

  1. If strs is empty, return "".
  2. For i from 0 to strs[0].length - 1:
  3. Let c = strs[0][i].
  4. For j from 1 to strs.length - 1:
  5. If i == strs[j].length or strs[j][i] != c:
  6. Return strs[0].substring(0, i).
  7. Return strs[0].

Vertical Character Column Scanning

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [f, l, o, w, e, r]
Current operationSTEP 1 OF 6
Observation: Column 0 has character 'f' in first string "flower"
Visual state
Values and pointers at this exact step
array
S
f
l
o
w
e
r
0
↑ Col 0: 'f'
1
2
3
4
5
Variables at this step
Column
0
Character
f
All Words Match
true
Current Prefix
f
Check / comparison
flower[0]=='f', flow[0]=='f', flight[0]=='f'. All match!
Decision / next transition
Prefix expands to "f". Advance to Col 1.
Why this step matters

Observation: Column 0 has character 'f' in first string "flower".

Decision: Check other strings: "flow"[0] == 'f', "flight"[0] == 'f'. All match!

Invariant: Character 'f' is confirmed part of the longest common prefix.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string longestCommonPrefix(std::vector<std::string>& strs) {
8 if (strs.empty()) return "";
9
10 for (int i = 0; i < (int)strs[0].size(); ++i) {
11 char c = strs[0][i];
12 for (int j = 1; j < (int)strs.size(); ++j) {
13 if (i == (int)strs[j].size() || strs[j][i] != c) {
14 return strs[0].substr(0, i);
15 }
16 }
17 }
18 return strs[0];
19 }
20};
21
22int main() {
23 Solution sol;
24 std::vector<std::string> strs = {"flower","flow","flight"};
25 std::cout << sol.longestCommonPrefix(strs) << std::endl; // "fl"
26
27 std::vector<std::string> strs2 = {"dog","racecar","car"};
28 std::cout << """ << sol.longestCommonPrefix(strs2) << """ << std::endl; // ""
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(S) where S is sum of characters; O(N * minLen) best/average case — Exits at column minLen, checking at most N * minLen characters.
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Horizontal ScanningO(S)O(1)Intuitive pairwise prefix shrinking.Processes entire first string even if last string has length 0.
2.Sorting Lexicographically (First & Last)O(N * M log N)O(1)Very short code; only compares lexicographical minimum and maximum.Overhead of sorting the entire array.
3.Vertical Scanning (Optimal)OptimalO(S) worst case, O(N * minLen) best caseO(1) extra spaceBest average case; exits immediately on the earliest mismatch without scanning trailing characters.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not checking if i == strs[j].length before accessing strs[j][i], causing string index out of bounds error.

Pitfall 2:

Concatenating characters one by one in quadratic string append fashion instead of substring slice.

Crucial Edge Cases to Validate:

  • strs contains empty string strs = ["", "b"]: At column i=0, i == strs[0].length triggers immediately and returns "".
  • Single element array strs = ["a"]: Inner loop over other strings does not run, returns strs[0] = "a".
  • No common prefix strs = ["dog", "cat"]: Column i=0 differs (d != c), returns "" immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention vertical scanning as the optimal choice due to early exit capabilities.
  2. Showcase the sorting first/last trick as an elegant secondary solution.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is vertical scanning generally preferred over horizontal scanning in practice?

Back to DSA Sheet