DSA AnimatorDSA animations
Longest Common Prefix LC #14 Easy Horizontal Scan
Problem

Write a function to find the longest common prefix string among an array of strings. If there is no common prefix, return an empty string "".

Example 1
Input: strs = ["flower","flow","flight"]
Output: "fl"
Explanation: f and l match across all strings, but "flo" fails on "flight".
Example 2
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: No common prefix — first chars d, r, c are all different.
Constraints: 1 ≤ strs.length ≤ 200 | 0 ≤ strs[i].length ≤ 200 | strs[i] consists of lowercase English letters
Try Examples
Custom:
Approach
Horizontal scan: trim prefix until it matches each string
Start with prefix = strs[0]. For each next string, shrink prefix from right until it matches. O(S) total characters.
String Grid
Current Prefix
""
Scanning…
Variables
i
—
prefix
—
compare
—
starts?
—
len
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Set prefix = strs[0] (candidate starts as the first string)
2
For i = 1 to n−1: check strs[i].startsWith(prefix)
3
While strs[i] does not start with prefix: trim one char from the right
4
If prefix becomes empty → return "" immediately
5
Once all strings match the prefix → return prefix
Time
O(S)
Space
O(1)
Why This Works

Horizontal scanning treats strs[0] as the candidate prefix. The prefix can only shrink — it is trimmed from the right until it matches each subsequent string. Once trimmed to match all strings, it is the longest possible common prefix. S = total characters across all strings.

How to solve Longest Common Prefix

LeetCode 14 · Easy · Strings · Pattern: Vertical Scan

Why the obvious approach is slow

Building every possible prefix and checking it against every word is slow. And remember, the prefix can never be longer than the shortest word.

The key idea

Line the words up, one under another, and read them column by column. Take the letter from the first word, and check that every other word has the same letter in that column. Stop at the first mismatch, or as soon as a word runs out.

Remember

Compare column by column, and stop at the first mismatch. The prefix is never longer than the shortest word.

Run the animation above on your own input, or watch the 1:20 video explanation of Longest Common Prefix with a dry run and Java code.

More Strings problems