Abstract / Summary

Given an array of integers, find the largest difference between two numbers where both numbers are prime.

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 59% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• Math
• Number Theory

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 provided Solution class implements a method that determines the distance between the earliest prime element and the latest prime element in a given integer list. By locating the first prime from the left and the first prime from the right, it returns the index difference, which represents the maximum span where both ends are prime numbers.

Key Steps

Prime detection with memoization

@cache
def isPrime(x):
    for factor in [2, 3, 5, 7]:  # sufficient for x <= 100
        if x % factor == 0:
            return x == factor
    return x > 1  # 1 isn't prime by definition

The helper function isPrime checks primality by testing divisibility against a small fixed set of factors. The @cache decorator stores results of previous calls, so repeated checks on the same value are answered instantly without recomputation.

Scanning from the left to find the first prime

low = 0
while not isPrime(nums[low]):
    low += 1

Starting at index 0, the loop advances until it encounters a prime number. If the first element is already prime, the loop body is skipped and low remains 0.

Scanning from the right to find the last prime

high = len(nums) - 1
while not isPrime(nums[high]):
    high -= 1

A symmetric scan begins at the final index and moves backward until a prime is found. When the last element is prime, high stays at the terminal position.

Computing the distance

return high - low

The method returns the difference between the two identified indices, which is the maximum distance between a left-most and a right-most prime in the list.

Edge Cases Handled

The algorithm gracefully deals with several boundary conditions. When the list begins with a prime number, the left-side scan stops immediately, leaving low at zero. Conversely, if the list ends with a prime, the right-side scan stops without decrementing high. The primality test explicitly rejects the value 1 and any non-positive integers, ensuring that zero, negative numbers, and one are never treated as prime. Because the factor list [2, 3, 5, 7] suffices for numbers up to 100, the function correctly identifies all primes within that range without unnecessary iteration.

Performance Optimizations

Memoization via @cache eliminates redundant primality calculations when the same number appears multiple times in the input, turning repeated checks into constant-time lookups. The primality test itself is trimmed to a minimal set of divisors, providing rapid determination for the expected input domain. The two linear scans stop as soon as the required primes are found, avoiding a full traversal of the list when the first and last primes are located early. This combination of cached results, limited divisor checks, and early termination yields an efficient solution for the problem at hand.

Imagine a long line of numbered blocks placed in a row. Some of these numbers are special because they are prime numbers, which means they cannot be split into smaller equal groups. To find the answer, the code first looks at the line from the left side and stops as soon as it spots the very first prime number. Then, it looks at the line all the way from the right side and stops when it finds the first prime number starting from that end. After finding those two specific spots, it counts how many blocks are between them by subtracting the position of the first one from the position of the second one. This tells us the distance between the prime numbers at the very edges of the group.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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		Java	Go	C++	Python	TS
	Progiez		Java		C++	Python
github	charles-wangkai		Java
	everthis	JS
	fsq				C++
	muhammadfarhankt			Go
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
muhammadfarhankt	Go

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