Prime Subtraction Operation - Video Solutions
Prime Subtraction Operation - Leetcode 2601 - Python
Prime Subtraction Operation - Video Solution
Watch 10 video solutions for Prime Subtraction Operation, a medium level problem involving Array, Math, Binary Search. This walkthrough by NeetCodeIO has 10,369 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a 0-indexed integer array nums of length n.
You can perform the following operation as many times as you want:
- Pick an index
ithat you haven’t picked before, and pick a primepstrictly less thannums[i], then subtractpfromnums[i].
Return true if you can make nums a strictly increasing array using the above operation and false otherwise.
A strictly increasing array is an array whose each element is strictly greater than its preceding element.
Example 1:
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.
Example 2:
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.
Example 3:
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.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1000nums.length == n
Approach Overview
Problem Overview: You receive an integer array nums. For each element, you may subtract a prime number smaller than the element at most once. The goal is to determine whether these operations can transform the array into a strictly increasing sequence.
Approach 1: Prime Subtraction Greedy Approach (O(n log p) time, O(p) space)
The core observation is that earlier elements should be minimized as much as possible so later elements have more room to remain larger. Iterate from left to right and maintain the previous valid value. For each nums[i], find the largest prime p such that nums[i] - p > prev. This keeps the new value just above the previous element while reducing the current number as much as possible. Store all primes up to the maximum array value and use binary search to quickly locate the largest valid prime. If no such prime exists and nums[i] <= prev, forming a strictly increasing sequence becomes impossible. This greedy strategy works because minimizing earlier numbers maximizes flexibility for the remaining elements.
Approach 2: Optimized Prime Sieve with Early Exit (O(m log log m + n log p) time, O(m) space)
Prime lookup becomes faster by generating all primes up to max(nums) using the Sieve of Eratosthenes from number theory. The sieve runs once in O(m log log m) where m is the largest number in the array. During the main pass, compute the difference diff = nums[i] - prev. Only primes smaller than diff are valid candidates. Use binary search over the prime list to pick the largest valid prime and subtract it. If nums[i] is already greater than prev, you may skip subtraction for efficiency. Add an early exit check whenever the current value cannot exceed prev. This approach combines greedy decision making with precomputed primes to keep each step efficient.
Recommended for interviews: Interviewers typically expect the greedy strategy with precomputed primes. A naive trial of primes per element shows understanding, but the optimized sieve + binary search demonstrates stronger algorithmic thinking. It combines array traversal, prime generation, and greedy decision making while maintaining near-linear performance.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prime Subtraction Greedy with Binary Search | O(n log p) | O(p) | General case when primes are precomputed and you need efficient lookups |
| Optimized Prime Sieve with Early Exit | O(m log log m + n log p) | O(m) | Best for repeated prime queries or large arrays where fast prime generation helps |