Horizontal & Vertical Scanning: The Longest Common Prefix Problem

Given several strings, how much of the beginning do they share? We can compare one string at a time, or check the same character position across every string. Both approaches can stop as soon as there is nothing left in common.

I'll walk through horizontal and vertical scanning in TypeScript, including the stopping conditions that make each version work.

Understanding the Problem

Given an array of strings, find the longest common prefix (LCP) amongst all the strings. If there is no common prefix, return an empty string: "".

Some Examples

A few examples make the expected result clearer:

• For the strings ["apple", "applied", "applause"], the LCP is "appl";
• For the strings ["book", "boon", "bootcamp"], the LCP is "boo";
• For the strings ["car", "bus", "train"], the output is "" because there is no common prefix.

Solve Using Horizontal Scanning

The Concept

Horizontal Scanning involves taking the first string as a reference and comparing it with the next string until a common prefix for both is found. This prefix is then taken as the reference for the next comparison, and so on.

In Code

const longestCommonPrefix = (strs: string[]): string => {
  if (strs.length === 0) return '';

  const first = strs[0];
  let prefixLength = first.length;

  for (let i = 1; i < strs.length && prefixLength > 0; i++) {
    const current = strs[i];
    let matched = 0;

    while (
      matched < prefixLength &&
      matched < current.length &&
      first[matched] === current[matched]
    ) {
      matched++;
    }

    prefixLength = matched;
  }

  return first.substring(0, prefixLength);
};

How It Works

1. We keep the first string as first and start prefixLength at its full length.
2. For each remaining string, we count matching characters from the beginning, stopping at a mismatch or the end of the surviving prefix or current string.
3. We shorten prefixLength to that count. If it reaches zero, the loop stops; the final substring() returns the surviving prefix.

Solve Using Vertical Scanning

The Concept

Instead of comparing strings individually, we compare characters at the same position (index) across the strings. This way, we vertically scan through the array.

In Code

const longestCommonPrefix = (strs: string[]): string => {
  if (strs.length === 0 || strs[0] === '') return '';

  for (let i = 0; i < strs[0].length; i++) {
    const char = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (i === strs[j].length || strs[j][i] !== char) {
        return strs[0].substring(0, i);
      }
    }
  }
  return strs[0];
};

How It Works

1. We loop over the characters of the first string.
2. For each character, we then check if the same character exists at the same index in all other strings.
3. If not, we return the prefix up to the current index.

Comparing the Two Methods

Horizontal scanning finishes comparing one string before moving to the next. If the early strings share a long prefix but the last string starts differently, it does work that a vertical scan could avoid.

Vertical scanning checks a position across all strings before advancing. It can discover that later first‑character mismatch quickly. Neither order is always faster; the position of the mismatches matters.

Complexity and Edge Cases

For these implementations, let n be the number of strings and S their combined length in UTF‑16 code units. Both take O(n + S) time in the worst case: each comparison advances through a string, and the returned substring is produced once. They use O(1) extra working space, excluding the returned prefix. The shortest string limits the final answer, but it does not bound the earlier work of the horizontal scan.

Useful edge cases include an empty array, a single string, an empty string inside the array, identical strings, and a mismatch at the first character. These examples compare case‑sensitive UTF‑16 code units, as JavaScript string indexing does. That suits the simple word examples here; a user‑facing text feature may need a different definition of a character.

When Each Scan is Clearer

Horizontal scanning reads naturally when you think of the prefix as something that is gradually shortened. Vertical scanning reads naturally when you think column by column across all strings. I tend to choose the version that makes the stopping condition easiest to see in the code review.

Closing Thoughts

The useful distinction is the order of the comparisons. Trace a mismatch near the end of the array through both versions and the difference becomes much easier to see.