Abstract / Summary

Find the length of the longest starting part that is the same in all given strings.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (400k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation computes the length of the longest common prefix shared by any pair of integers where the two members of the pair come from different input arrays. It treats each integer as a string, merges the two collections while preserving the origin of each element, sorts the merged list, and then scans adjacent entries to find the maximal prefix length across cross-array pairs.

Core Algorithm

The first phase builds a combined list that records both the string representation of each number and an identifier indicating its source array.

all = []
for a in arr1:
    all.append((str(a), 1))
for b in arr2:
    all.append((str(b), 2))

By converting numbers to strings once, the algorithm avoids repeated conversions during later comparisons.

Sorting for Proximity

Sorting the merged list groups together strings that share lexical prefixes. Because the sort order is based on the string representation, any two strings that could share a non-empty prefix will appear next to each other or within a small neighbourhood in the sorted sequence.

all.sort()

This step reduces the number of pairwise checks needed: only adjacent entries need to be examined for a potential cross-array prefix.

Pairwise Comparison

The algorithm iterates over each consecutive pair in the sorted list, extracts the string values and their source identifiers, and proceeds only when the two entries originate from different input arrays.

for left, right in zip(all, all[1:]):
    one, src1 = left
    two, src2 = right
    if src1 != src2:
        # prefix detection follows

The zip construct creates overlapping windows of size two, ensuring every adjacent pair is examined exactly once.

Prefix Length Computation

When a cross-array pair is found, a nested loop walks character by character through both strings until a mismatch occurs. The counter i records the length of the matching prefix, and the global result is updated with the maximum value seen so far.

i = 0
for a, b in zip(one, two):
    if a == b:
        i += 1
    else:
        break
result = max(result, i)

The early exit on the first differing character prevents unnecessary iteration over the remainder of the strings.

Edge Cases Handled

The code gracefully handles empty input arrays because the initial result remains zero and the loops simply do not execute. When one array contains a single element and the other contains many, the sorting and adjacent-pair logic still correctly evaluates all possible cross-array matches. Numbers of varying digit lengths are compared as strings, so leading zeros are not introduced, and the prefix detection stops as soon as the shorter string ends, correctly yielding the length of the common prefix (which may be the entire shorter string). Duplicate values within the same source array are ignored for prefix calculation because the source identifiers must differ; duplicates across arrays are still considered, allowing the algorithm to capture a full-length match. Cases where no two numbers share any prefix result in result staying at zero, reflecting the absence of a common prefix.

Performance Optimizations

The design minimizes work by converting each integer to a string exactly once, storing the result in the combined list. Sorting the list brings potentially matching strings into adjacency, which eliminates the need for a quadratic scan of all cross-array pairs. The use of zip to generate overlapping windows ensures each adjacent pair is processed only once, avoiding redundant comparisons. Within the prefix detection loop, the immediate break on the first mismatch prevents needless character checks beyond the point of divergence. The final max operation updates the answer in constant time per pair, keeping the overall runtime tightly bound to the cost of sorting and the linear scans of adjacent pairs.

Imagine you have two big buckets filled with numbered blocks. The code starts by taking all those blocks and writing their numbers down on tiny stickers. Each sticker also gets a special mark so you know if it came from the first bucket or the second bucket. Once every block has a sticker, the code lines them all up in alphabetical order, just like books on a library shelf.

Next, the code looks at the blocks that are sitting right next to each other in that long line. It specifically looks for a pair where one block came from the first bucket and the one beside it came from the second bucket. When it finds a pair like that, it peeks at the numbers written on them and compares the digits starting from the very front. It counts how many of those front digits are exactly the same. If the numbers start with the same pattern, that is a match. The code keeps a little scoreboard to remember the longest match it has found so far. Every time it sees a new pair, it checks to see if the new match is longer than the one it already saved. By the time it finishes looking through all the neighbor pairs, the longest match stays on the scoreboard.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python		TS
	WalkCCC		Java	C++		Python
	leetcode.ca	JS	Java	C++	Go	Python	Rust	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	varunu28		Java
	withaarzoo			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality