LeetCode 2601 - Prime Subtraction Operation

LeetCode Problem 2601

Difficulty: 🟡 Medium
Topics: Array, Math, Binary Search, Greedy, Number Theory

Solution

Problem Understanding

The problem gives us an integer array nums and asks whether it is possible to transform the array into a strictly increasing sequence by performing a special operation.

For any index i, we may choose that index at most once and subtract a prime number p from nums[i], where p must be strictly smaller than nums[i]. Since p < nums[i], every resulting value remains positive. We can also choose to skip an index entirely and leave its value unchanged.

The goal is to determine whether, after performing zero or more such operations, the final array satisfies:

nums[0] < nums[1] < nums[2] < ...

The key restriction is that each index can only be modified once, and we are only allowed to subtract prime numbers. This means we cannot freely adjust values to anything we want. Instead, each element has a limited set of achievable values.

The input consists of:

• An integer array nums
• Length n, where 1 <= n <= 1000
• Values where 1 <= nums[i] <= 1000

The expected output is:

• true if we can transform the array into a strictly increasing array
• false otherwise

The constraints reveal several important things about the problem scale.

Since nums[i] <= 1000, the universe of possible prime numbers is very small. We can precompute all primes up to 1000 efficiently using a sieve or simple primality testing. Also, n <= 1000, which means even an O(n log M) or O(n * M) solution is acceptable, where M is around 1000.

Several edge cases stand out immediately.

A single-element array is always strictly increasing by definition because there are no adjacent comparisons to violate the rule.

Arrays that are already strictly increasing should return true without requiring any operations.

Arrays containing very small numbers such as 1 or 2 can be tricky because there are few or no valid prime numbers smaller than them. For example, 1 cannot be modified at all.

Another subtle case occurs when an element must become smaller than a previous element to preserve increasing order, but no valid prime subtraction can achieve the required value.

Approaches

Brute Force Approach

A brute force strategy would try all valid prime subtraction choices for every index.

For each element, we could either:

1. Leave it unchanged
2. Subtract any valid prime smaller than the number

This creates a branching decision tree. Since each element may have multiple prime choices, the number of possible transformed arrays grows exponentially.

For example, if an element has around 20 prime choices and we have n elements, the total search space becomes enormous. We could use backtracking to test every possible transformed configuration and check whether any arrangement becomes strictly increasing.

This works because it exhaustively explores all valid operations and therefore guarantees correctness. However, it is computationally impractical because the number of combinations explodes exponentially.

Key Insight for an Optimal Solution

The critical observation is that we should process the array from left to right greedily.

At each position, we want to make the current number as small as possible while still remaining greater than the previous number.

Why?

Making an element smaller gives future elements more room to remain strictly increasing. If we leave a number unnecessarily large, later elements may become impossible to fix.

Suppose the previous chosen value is prev. For the current value num, we want:

new_value > prev

Since we can only subtract a prime:

new_value = num - prime

Rearranging:

prime < num - prev

Therefore, we want to subtract the largest prime smaller than num - prev. This minimizes the current number while still keeping it greater than prev.

If no such transformation makes:

new_value > prev

then the answer is immediately false.

Because primes are sorted, we can use binary search to efficiently find the largest valid prime.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Tries all prime subtraction combinations
Optimal	O(n log P + P log log P)	O(P)	Greedy left-to-right with binary search on primes

Here, P = 1000, which is the maximum possible number value.

Algorithm Walkthrough

1. Precompute all prime numbers up to 1000.

Since every number in nums is at most 1000, we only need primes in this range. We generate and store them in sorted order. 2. Initialize a variable prev = 0.

This tracks the previously fixed number in the strictly increasing sequence. 3. Iterate through the array from left to right.

At each step, we consider the current value num. 4. Compute the maximum prime we are allowed to subtract.

We need:

num - prime > prev

Rearranging:

prime < num - prev

So we search for the largest prime strictly smaller than:

num - prev

5. Use binary search to find the largest valid prime.

Since the prime list is sorted, binary search efficiently finds the best subtraction candidate. 6. Subtract the chosen prime if one exists.

If a valid prime exists, subtract it from num. Otherwise, leave the number unchanged. 7. Verify strict increasing order.

If the resulting value is not greater than prev, return false immediately because recovery is impossible. 8. Update prev.

Store the newly fixed value as the previous value for the next iteration. 9. Finish the traversal.

If every element satisfies the condition, return true.

Why it works

The greedy strategy works because making each number as small as possible preserves maximum flexibility for future elements.

At every step, the algorithm chooses the minimum feasible value that still satisfies the increasing condition. Any larger choice would only make future constraints harder. Since future numbers must exceed the current one, minimizing earlier values can never hurt and may only help. Therefore, if the greedy approach fails, no valid arrangement exists.

Python Solution

from typing import List
import bisect

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        def generate_primes(limit: int) -> List[int]:
            is_prime = [True] * (limit + 1)
            is_prime[0] = is_prime[1] = False

            for i in range(2, int(limit ** 0.5) + 1):
                if is_prime[i]:
                    for multiple in range(i * i, limit + 1, i):
                        is_prime[multiple] = False

            return [i for i in range(2, limit + 1) if is_prime[i]]

        primes = generate_primes(1000)

        prev = 0

        for num in nums:
            limit = num - prev

            index = bisect.bisect_left(primes, limit) - 1

            if index >= 0:
                num -= primes[index]

            if num <= prev:
                return False

            prev = num

        return True

The implementation begins by generating all prime numbers up to 1000 using the Sieve of Eratosthenes. Since the constraints guarantee that nums[i] <= 1000, this preprocessing step is sufficient for every test case.

We then maintain a variable called prev, representing the previously finalized value in the strictly increasing sequence.

For every number in the array, we compute:

limit = num - prev

This represents the upper bound on the prime we may subtract. We need a prime strictly smaller than this value.

Using bisect_left, we locate the insertion point of limit in the sorted prime list. Subtracting one gives the index of the largest prime strictly smaller than limit.

If such a prime exists, we subtract it to minimize the current value. Afterward, we verify that the resulting number is still strictly greater than prev.

If not, we immediately return False. Otherwise, we update prev and continue.

If the entire traversal succeeds, we return True.

Go Solution

package main

import "sort"

func primeSubOperation(nums []int) bool {
	primes := generatePrimes(1000)

	prev := 0

	for _, num := range nums {
		limit := num - prev

		index := sort.Search(len(primes), func(i int) bool {
			return primes[i] >= limit
		}) - 1

		if index >= 0 {
			num -= primes[index]
		}

		if num <= prev {
			return false
		}

		prev = num
	}

	return true
}

func generatePrimes(limit int) []int {
	isPrime := make([]bool, limit+1)

	for i := 2; i <= limit; i++ {
		isPrime[i] = true
	}

	for i := 2; i*i <= limit; i++ {
		if isPrime[i] {
			for multiple := i * i; multiple <= limit; multiple += i {
				isPrime[multiple] = false
			}
		}
	}

	primes := []int{}

	for i := 2; i <= limit; i++ {
		if isPrime[i] {
			primes = append(primes, i)
		}
	}

	return primes
}

The Go implementation follows exactly the same logic as the Python version. The main difference lies in binary search.

Instead of bisect_left, Go uses sort.Search, which returns the first index where the condition becomes true. We search for the first prime greater than or equal to limit, then subtract one to obtain the largest prime strictly smaller than limit.

Go slices naturally handle empty arrays, so no special nil handling is required. Integer overflow is also not a concern because values never exceed 1000.

Worked Examples

Example 1

nums = [4, 9, 6, 10]

Index	Current Num	Prev	Limit (num - prev)	Prime Chosen	New Value
0	4	0	4	3	1
1	9	1	8	7	2
2	6	2	4	3	3
3	10	3	7	5	5

Final array:

[1, 2, 3, 5]

This is strictly increasing, so the answer is true.

Example 2

nums = [6, 8, 11, 12]

Index	Current Num	Prev	Limit	Prime Chosen	New Value
0	6	0	6	5	1
1	8	1	7	5	3
2	11	3	8	7	4
3	12	4	8	7	5

Final array:

[1, 3, 4, 5]

Even though the original array was already increasing, the greedy algorithm still works by minimizing values while preserving order.

Answer: true.

Example 3

nums = [5, 8, 3]

Index	Current Num	Prev	Limit	Prime Chosen	New Value
0	5	0	5	3	2
1	8	2	6	5	3
2	3	3	0	None	3

At index 2:

3 <= prev (3)

Strictly increasing order fails.

Answer: false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(P log log P + n log P)	Prime generation plus binary search per element
Space	O(P)	Storage for prime list and sieve

Here, P = 1000.

The sieve requires O(P log log P) time to generate primes. For each of the n elements, we perform one binary search over the prime list, which costs O(log P).

Since P is fixed at 1000, the solution is effectively linear in practice.

Test Cases

sol = Solution()

assert sol.primeSubOperation([4, 9, 6, 10]) is True  # Example 1
assert sol.primeSubOperation([6, 8, 11, 12]) is True  # Example 2
assert sol.primeSubOperation([5, 8, 3]) is False  # Example 3

assert sol.primeSubOperation([1]) is True  # Single element
assert sol.primeSubOperation([2]) is True  # No prime subtraction possible
assert sol.primeSubOperation([1, 2, 3]) is True  # Already increasing
assert sol.primeSubOperation([5, 4, 3]) is False  # Strictly decreasing
assert sol.primeSubOperation([10, 10, 10]) is True  # Equal elements can be adjusted
assert sol.primeSubOperation([3, 2]) is False  # Impossible small case
assert sol.primeSubOperation([1000, 1000]) is True  # Large boundary values
assert sol.primeSubOperation([2, 2]) is False  # Cannot reduce enough
assert sol.primeSubOperation([8, 3, 10]) is False  # Middle element too small
assert sol.primeSubOperation([20, 25, 30]) is True  # Larger increasing values

Test	Why
[4,9,6,10]	Validates first example
[6,8,11,12]	Validates already increasing case
[5,8,3]	Validates impossible scenario
[1]	Single-element boundary
[2]	Smallest prime-related edge
[1,2,3]	No operations needed
[5,4,3]	Decreasing order impossible
[10,10,10]	Equal values can still become increasing
[3,2]	Small impossible input
[1000,1000]	Maximum boundary values
[2,2]	Very limited prime options
[8,3,10]	Small middle element failure
[20,25,30]	Larger successful transformation

Edge Cases

One important edge case is a single-element array. Since there are no adjacent elements to compare, the array is already strictly increasing by definition. A buggy implementation might incorrectly attempt unnecessary prime subtraction. Our implementation handles this naturally because the loop completes without failure.

Another tricky case occurs when numbers are too small to subtract primes. For example:

[2, 2]

The number 2 has no prime strictly smaller than it. Therefore, the first element stays 2, and the second element cannot become greater than 2. Our implementation correctly detects this when:

num <= prev

and returns False.

A third important edge case involves equal or decreasing elements that can still be repaired. Consider:

[10, 10, 10]

A naive solution may prematurely reject equal numbers. However, prime subtraction allows transformation:

[3, 5, 7]

The greedy strategy succeeds because it minimizes each number while maintaining increasing order.

Finally, arrays with very large values near constraints such as [1000, 1000] can expose inefficiencies if prime generation is poorly implemented. By preprocessing primes only once up to 1000, our solution remains efficient and easily fits within limits.