Problem Description

You have an array of integers nums with 0-based indexing and length n.

You can perform a special operation on the array multiple times:

• Choose any index i that hasn't been chosen before
• Select a prime number p that is strictly less than nums[i]
• Subtract p from nums[i]

Your goal is to determine if you can transform the array into a strictly increasing array using these operations. A strictly increasing array means each element must be strictly greater than the element before it (i.e., nums[0] < nums[1] < nums[2] < ... < nums[n-1]).

The key constraints are:

• Each index can only be picked once for the operation
• The prime number chosen must be strictly less than the current value at that index
• You want to make the array strictly increasing (no equal consecutive elements allowed)

Return true if it's possible to achieve a strictly increasing array through these operations, and false otherwise.

For example, if you have nums = [4, 9, 6, 10], you could:

• Pick index 0 and subtract prime 3 from nums[0] to get [1, 9, 6, 10]
• Pick index 2 and subtract prime 3 from nums[2] to get [1, 9, 3, 10]
• This would not work since 3 < 9 but we need strictly increasing

The solution works backwards from the end of the array, trying to make each element as large as possible while still being less than the next element, by subtracting the smallest suitable prime.

Intuition

The key insight is to work backwards from the end of the array. Why backwards? Because we want to maximize the values of earlier elements to give us the most flexibility.

Think about it this way: if we process from left to right, we might subtract too much from an early element, making it impossible to maintain strict increasing order later. But if we work from right to left, we know exactly what constraint each element must satisfy - it must be less than the element to its right.

For each element nums[i], we need nums[i] < nums[i+1]. If this condition already holds, we don't need to do anything - keeping nums[i] as large as possible gives more room for elements to its left.

If nums[i] >= nums[i+1], we must subtract a prime from nums[i]. The question is: which prime? We need the smallest prime p such that after subtracting it, nums[i] - p < nums[i+1]. This means we need p > nums[i] - nums[i+1].

Why the smallest such prime? Because we want to keep nums[i] as large as possible after the operation. A larger nums[i] makes it easier for nums[i-1] to be less than nums[i].

The binary search comes naturally here - we precompute all primes up to the maximum value in the array, then use binary search to quickly find the smallest prime greater than nums[i] - nums[i+1].

If we can't find such a prime (either because no prime is large enough, or the required prime is >= nums[i]), then it's impossible to make the array strictly increasing, and we return false.

This greedy approach of maximizing each element while satisfying the constraint works because each index can only be operated on once - there's no second chance to adjust a value.

Learn more about Greedy, Math and Binary Search patterns.

Solution Approach

The implementation consists of two main parts: preprocessing prime numbers and processing the array from right to left.

Step 1: Generate Prime Numbers

First, we need to generate all prime numbers up to max(nums). The code uses a simple sieve-like approach:

p = []
for i in range(2, max(nums)):
    for j in p:
        if i % j == 0:
            break
    else:
        p.append(i)

For each number i from 2 to max(nums) - 1, we check if it's divisible by any previously found prime. If not divisible by any prime in p, then i itself is prime and gets added to the list.

Step 2: Process Array from Right to Left

We iterate through the array from the second-to-last element backwards to the first element:

for i in range(n - 2, -1, -1):
    if nums[i] < nums[i + 1]:
        continue

If nums[i] < nums[i + 1], the strict increasing condition is already satisfied, so we skip to the next element.

Step 3: Find and Apply the Smallest Valid Prime

When nums[i] >= nums[i + 1], we need to subtract a prime from nums[i]:

j = bisect_right(p, nums[i] - nums[i + 1])

We use bisect_right to find the smallest prime greater than nums[i] - nums[i + 1]. This gives us the index j of the first prime that, when subtracted from nums[i], will make it less than nums[i + 1].

Step 4: Validation and Update

if j == len(p) or p[j] >= nums[i]:
    return False
nums[i] -= p[j]

We check two failure conditions:

• j == len(p): No prime is large enough to satisfy our requirement
• p[j] >= nums[i]: The required prime is not strictly less than nums[i]

If either condition is true, it's impossible to make the array strictly increasing, so we return False.

Otherwise, we subtract p[j] from nums[i] and continue processing.

Time Complexity: O(m√m + n log m) where m = max(nums) and n = len(nums). The prime generation takes O(m√m) and for each element, we perform a binary search in O(log m).

Space Complexity: O(π(m)) where π(m) is the prime counting function, representing the number of primes less than m.

Example Walkthrough

Let's walk through the solution with nums = [5, 8, 3].

Step 1: Generate primes up to max(nums) = 8

• Primes less than 8: [2, 3, 5, 7]

Step 2: Process from right to left

Index i = 1 (comparing nums[1] = 8 with nums[2] = 3):

• Is 8 < 3? No, so we need to subtract a prime from nums[1]
• We need nums[1] - p < 3, which means p > 8 - 3 = 5
• Using binary search on [2, 3, 5, 7] to find smallest prime > 5
• bisect_right([2, 3, 5, 7], 5) returns index 3 (pointing to 7)
• Check: Is 7 < 8? Yes, valid!
• Subtract: nums[1] = 8 - 7 = 1
• Array becomes: [5, 1, 3]

Index i = 0 (comparing nums[0] = 5 with nums[1] = 1):

• Is 5 < 1? No, so we need to subtract a prime from nums[0]
• We need nums[0] - p < 1, which means p > 5 - 1 = 4
• Using binary search on [2, 3, 5, 7] to find smallest prime > 4
• bisect_right([2, 3, 5, 7], 4) returns index 2 (pointing to 5)
• Check: Is 5 < 5? No! The prime must be strictly less than nums[0]
• Since we can't find a valid prime, return False

The array cannot be made strictly increasing because we would need to subtract at least 5 from nums[0] = 5, but the prime must be strictly less than 5.

Let's try another example where it works: nums = [6, 9, 12]

Step 1: Generate primes up to 12

• Primes: [2, 3, 5, 7, 11]

Step 2: Process from right to left

Index i = 1 (comparing nums[1] = 9 with nums[2] = 12):

• Is 9 < 12? Yes, already satisfied. Continue.
• Array remains: [6, 9, 12]

Index i = 0 (comparing nums[0] = 6 with nums[1] = 9):

• Is 6 < 9? Yes, already satisfied. Continue.
• Array remains: [6, 9, 12]

All elements are already strictly increasing, so return True.

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(m√m + n log p) where m = max(nums), n = len(nums), and p is the number of primes less than m.

Breaking down the time complexity:

1. Prime generation: The outer loop runs O(m) times. For each number i, we check divisibility against all previously found primes. In the worst case, we check up to O(√i) primes (since if a number has a factor, it must have one ≤ √i). This gives us O(m√m) for generating all primes up to max(nums).

2. Main operation loop: The loop runs O(n) times. Each iteration performs a bisect_right operation on the prime list, which takes O(log p) time where p ≈ m/ln(m) by the prime number theorem. This gives us O(n log p).

The overall time complexity is O(m√m + n log p). Since p < m, we can simplify this to O(m√m + n log m). When m is treated as bounded by the input values (not growing with n), this can be approximated as O(n log n) for the dominant operation on the array.

The space complexity is O(p) for storing the prime numbers, where p ≈ m/ln(m). Since m = max(nums) and could be proportional to n in many cases, the space complexity can be expressed as O(n) when considering the relationship between the maximum value and array length.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Working Forward Instead of Backward

A natural instinct is to process the array from left to right, trying to make each element as small as possible. However, this greedy approach fails because you don't know what constraints future elements will impose.

Why it fails: If you make early elements too small, you might not have enough "room" for later elements to be strictly increasing.

Example:

• nums = [5, 8, 3]
• Working forward: Subtract 3 from nums[0] → [2, 8, 3]
• Now you're stuck - you can't make 3 > 8

Solution: Work backward from the end. This way, you know exactly what constraint each element must satisfy (being less than the next element), and you can maximize each element's value while meeting that constraint.

2. Using <= Instead of < for Prime Selection

The problem states the prime must be strictly less than nums[i], but it's easy to accidentally use <= in the condition check.

Incorrect:

if prime_index == len(primes) or primes[prime_index] > nums[i]:  # Wrong!
    return False

Correct:

if prime_index == len(primes) or primes[prime_index] >= nums[i]:  # Correct
    return False

3. Incorrect Binary Search Target

When finding the minimum prime to subtract, the calculation nums[i] - nums[i + 1] gives us the minimum difference needed. We need a prime strictly greater than this value, not greater than or equal to.

Why bisect_right is correct:

• If nums[i] = 10 and nums[i + 1] = 5
• We need prime p such that 10 - p < 5, so p > 5
• bisect_right(primes, 5) gives us the first prime strictly greater than 5

Common mistake: Using bisect_left would give us primes >= 5, which might include 5 itself, leading to 10 - 5 = 5, violating the strictly increasing requirement.

4. Not Handling the Case Where No Operation is Needed

The code correctly handles this by checking if nums[i] < nums[i + 1]: continue, but forgetting this check would cause unnecessary operations and potentially invalid results.

Example: nums = [1, 2, 3] is already strictly increasing. Without the check, you might try to subtract primes unnecessarily and make the array invalid.

5. Inefficient Prime Generation

While the given implementation works, using a more efficient sieve like the Sieve of Eratosthenes would be better for larger inputs:

def generate_primes(limit):
    if limit < 2:
        return []
    sieve = [True] * limit
    sieve[0] = sieve[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit, i):
                sieve[j] = False
    return [i for i in range(2, limit) if sieve[i]]

This runs in O(m log log m) time versus the O(m√m) of the trial division method.