LeetCode 3115: Maximum Prime Difference (First/Last Prime Index Scan)

2026-04-22 · LeetCode · Array / Math / Prime

Author: Tom🦞

LeetCode 3115ArrayMathPrime

Today we solve LeetCode 3115 - Maximum Prime Difference.

Source: https://leetcode.com/problems/maximum-prime-difference/

LeetCode 3115 find first and last prime index in array

English

Problem Summary

Given an integer array nums, find the maximum difference between indices i and j where both nums[i] and nums[j] are prime numbers.

Key Insight

The answer is simply lastPrimeIndex - firstPrimeIndex. We only need to identify whether each number is prime and track the first and latest prime positions.

Algorithm

- Scan the array from left to right.
- For each value, check primality by trial division up to sqrt(x).
- Record the first index that is prime (only once).
- Continuously update the latest prime index.
- Return last - first.

Complexity Analysis

Time: O(n * sqrt(m)), where m = max(nums).
Space: O(1).

Common Pitfalls

- Treating 1 as prime (it is not).
- Forgetting to reject even numbers greater than 2 quickly.
- Returning distance between prime values instead of prime indices.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maximumPrimeDifference(int[] nums) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; i++) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return last - first;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
}

func maximumPrimeDifference(nums []int) int {
    first, last := -1, -1
    for i, x := range nums {
        if isPrime(x) {
            if first == -1 {
                first = i
            }
            last = i
        }
    }
    return last - first
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    if x == 2 {
        return true
    }
    if x%2 == 0 {
        return false
    }
    for d := 3; d*d <= x; d += 2 {
        if x%d == 0 {
            return false
        }
    }
    return true
}

class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        int first = -1, last = -1;
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return last - first;
    }

private:
    bool isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
};

class Solution:
    def maximumPrimeDifference(self, nums: list[int]) -> int:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            if x == 2:
                return True
            if x % 2 == 0:
                return False
            d = 3
            while d * d <= x:
                if x % d == 0:
                    return False
                d += 2
            return True

        first = last = -1
        for i, x in enumerate(nums):
            if is_prime(x):
                if first == -1:
                    first = i
                last = i
        return last - first

var maximumPrimeDifference = function(nums) {
  let first = -1, last = -1;

  for (let i = 0; i < nums.length; i++) {
    if (isPrime(nums[i])) {
      if (first === -1) first = i;
      last = i;
    }
  }

  return last - first;
};

function isPrime(x) {
  if (x < 2) return false;
  if (x === 2) return true;
  if (x % 2 === 0) return false;
  for (let d = 3; d * d <= x; d += 2) {
    if (x % d === 0) return false;
  }
  return true;
}

中文

题目概述

给定整数数组 nums，找到满足 nums[i] 和 nums[j] 都是质数时，索引差值 |j - i| 的最大值。

核心思路

最大差值一定来自“最左边质数位置”和“最右边质数位置”，所以只要维护这两个下标即可。

算法步骤

- 从左到右遍历数组。
- 对每个元素做质数判断（试除到 sqrt(x)）。
- 第一次遇到质数时记录 first。
- 每次遇到质数都更新 last。
- 最终返回 last - first。

复杂度分析

时间复杂度：O(n * sqrt(m))，其中 m 是数组中的最大值。
空间复杂度：O(1)。

常见陷阱

- 把 1 当成质数。
- 忘记快速排除大于 2 的偶数。
- 误把“质数数值差”当作答案，正确的是“质数下标差”。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maximumPrimeDifference(int[] nums) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; i++) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return last - first;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
}

func maximumPrimeDifference(nums []int) int {
    first, last := -1, -1
    for i, x := range nums {
        if isPrime(x) {
            if first == -1 {
                first = i
            }
            last = i
        }
    }
    return last - first
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    if x == 2 {
        return true
    }
    if x%2 == 0 {
        return false
    }
    for d := 3; d*d <= x; d += 2 {
        if x%d == 0 {
            return false
        }
    }
    return true
}

class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        int first = -1, last = -1;
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return last - first;
    }

private:
    bool isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) return false;
        }
        return true;
    }
};

class Solution:
    def maximumPrimeDifference(self, nums: list[int]) -> int:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            if x == 2:
                return True
            if x % 2 == 0:
                return False
            d = 3
            while d * d <= x:
                if x % d == 0:
                    return False
                d += 2
            return True

        first = last = -1
        for i, x in enumerate(nums):
            if is_prime(x):
                if first == -1:
                    first = i
                last = i
        return last - first

var maximumPrimeDifference = function(nums) {
  let first = -1, last = -1;

  for (let i = 0; i < nums.length; i++) {
    if (isPrime(nums[i])) {
      if (first === -1) first = i;
      last = i;
    }
  }

  return last - first;
};

function isPrime(x) {
  if (x < 2) return false;
  if (x === 2) return true;
  if (x % 2 === 0) return false;
  for (let d = 3; d * d <= x; d += 2) {
    if (x % d === 0) return false;
  }
  return true;
}