Prime Subtraction Operation Python Solution

lcpy gen -n 2601   # by problem number
lcpy gen -s prime_subtraction_operation   # by problem name

Input: nums = [4,9,6,10]
Output: true
Explanation: In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums[0], so that nums becomes [1,9,6,10].
In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums becomes equal to [1,2,6,10].
After the second operation, nums is sorted in strictly increasing order, so the answer is true.

Input: nums = [6,8,11,12]
Output: true
Explanation: Initially nums is sorted in strictly increasing order, so we don't need to make any operations.

Input: nums = [5,8,3]
Output: false
Explanation: It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.

from bisect import bisect_left


class Solution:
    # Time: O(n log P + P log log P) where P = max(nums)
    # Space: O(P)
    def prime_sub_operation(self, nums: list[int]) -> bool:
        limit = max(nums)
        sieve = [True] * (limit + 1)
        if limit >= 0:
            sieve[0] = False
        if limit >= 1:
            sieve[1] = False
        for i in range(2, int(limit**0.5) + 1):
            if sieve[i]:
                for multiple in range(i * i, limit + 1, i):
                    sieve[multiple] = False
        primes = [i for i in range(2, limit + 1) if sieve[i]]

        prev = 0
        for num in nums:
            # Largest prime p < num - prev keeps the resulting value as small as
            # possible while still exceeding prev; a smaller value is never worse.
            idx = bisect_left(primes, num - prev) - 1
            value = num - primes[idx] if idx >= 0 else num
            if value <= prev:
                return False
            prev = value
        return True