How do you handle arrays with only one prime for Maximum Prime Difference?

If there is a single prime, the maximum distance is zero since both start and end indices are the same.

What is the fastest way to identify primes in nums?

Use a precomputed sieve for numbers up to 100 to quickly check each array element.

Does Maximum Prime Difference require primes to be distinct?

No, the maximum difference can involve the same prime number at different positions.

Can this approach be applied to larger ranges of numbers?

Yes, but sieve precomputation or optimized prime checks should scale with the upper limit of numbers in the array.

Why is this problem pattern labeled Array plus Math?

It combines linear array traversal with number-theory calculations for primes, reflecting the typical trade-offs in index and value computations.

#3115

Medium

auto_awesome数组·数学

LeetCode 题解工作台

质数的最大距离

给你一个整数数组 nums 。返回两个（不一定不同的）质数在 nums 中下标的最大距离。示例 1：输入： nums = [4,2,9,5,3] 输出： 3 解释： nums[1] 、 nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3 。示例 2：输入…

数组数学数论

题目描述

给你一个整数数组 nums。

返回两个（不一定不同的）质数在 nums 中下标的 最大距离。

示例 1：

输入： nums = [4,2,9,5,3]

输出： 3

解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：

输入： nums = [4,8,2,8]

输出： 0

解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示：

1 <= nums.length <= 3 * 10⁵
1 <= nums[i] <= 100
输入保证 nums 中至少有一个质数。

lightbulb

解题思路

方法一：遍历

根据题目描述，我们需要找出第一个质数所在的下标 $i$ ，然后找出最后一个质数所在的下标 $j$ ，将 $j - i$ 作为答案返回即可。

因此，我们可以从左到右遍历数组，找到第一个质数所在的下标 $i$ ，然后从右到左遍历数组，找到最后一个质数所在的下标 $j$ ，答案即为 $j - i$ 。

时间复杂度 $O(n \times \sqrt{M})$ ，其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度和数组中的最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            return all(x % i for i in range(2, int(sqrt(x)) + 1))

        for i, x in enumerate(nums):
            if is_prime(x):
                for j in range(len(nums) - 1, i - 1, -1):
                    if is_prime(nums[j]):
                        return j - i

speed

复杂度分析

指标	值
时间	complexity is O(n + k) where n is nums.length and k is the upper limit of prime checks (≤100). Space complexity is O(1) if storing only first and last indices, or O(p) if storing all prime positions.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient prime detection within small bounded numbers.
question_mark
Check if candidate solutions handle arrays with only one prime correctly.
question_mark
Consider both edge cases and normal spreads of primes in the array.

warning

常见陷阱

外企场景

error
Failing to precompute primes, leading to repeated unnecessary calculations.
error
Incorrectly assuming two primes must be distinct for maximum difference.
error
Not handling arrays where a single prime exists, producing incorrect output.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute maximum distance between odd numbers instead of primes.
arrow_right_alt
Find maximum difference between numbers satisfying a custom number-theory property.
arrow_right_alt
Return both indices of the furthest prime numbers, not just the distance.

help

常见问题

外企场景

继续练习

#3116 单面值组合的第 K 小金额 #3044 出现频率最高的质数 #3012 通过操作使数组长度最小