Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given an array nums of n positive integers and an integer k.
Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:
nums[l, ..., r] that you haven't chosen previously.x of nums[l, ..., r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.x.Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.
The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5.
Return the maximum possible score after applying at most k operations.
Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: nums = [8,3,9,3,8], k = 2 Output: 81 Explanation: To get a score of 81, we can apply the following operations: - Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray. Hence, we multiply the score by nums[2]. The score becomes 1 * 9 = 9. - Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 1, but nums[2] has the smaller index. Hence, we multiply the score by nums[2]. The score becomes 9 * 9 = 81. It can be proven that 81 is the highest score one can obtain.
Example 2:
Input: nums = [19,12,14,6,10,18], k = 3 Output: 4788 Explanation: To get a score of 4788, we can apply the following operations: - Choose subarray nums[0, ..., 0]. nums[0] is the only element in this subarray. Hence, we multiply the score by nums[0]. The score becomes 1 * 19 = 19. - Choose subarray nums[5, ..., 5]. nums[5] is the only element in this subarray. Hence, we multiply the score by nums[5]. The score becomes 19 * 18 = 342. - Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 2, but nums[2] has the smaller index. Hence, we multipy the score by nums[2]. The score becomes 342 * 14 = 4788. It can be proven that 4788 is the highest score one can obtain.
Constraints:
1 <= nums.length == n <= 1051 <= nums[i] <= 1051 <= k <= min(n * (n + 1) / 2, 109)Problem summary: You are given an array nums of n positive integers and an integer k. Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times: Choose any non-empty subarray nums[l, ..., r] that you haven't chosen previously. Choose an element x of nums[l, ..., r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index. Multiply your score by x. Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive. The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5. Return the maximum possible score after applying at most k operations. Since the answer may be large, return it modulo 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math · Stack · Greedy
[8,3,9,3,8] 2
[19,12,14,6,10,18] 3
next-greater-element-iv)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2818: Apply Operations to Maximize Score
class Solution {
private final int mod = (int) 1e9 + 7;
public int maximumScore(List<Integer> nums, int k) {
int n = nums.size();
int[][] arr = new int[n][0];
for (int i = 0; i < n; ++i) {
arr[i] = new int[] {i, primeFactors(nums.get(i)), nums.get(i)};
}
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
Deque<Integer> stk = new ArrayDeque<>();
for (int[] e : arr) {
int i = e[0], f = e[1];
while (!stk.isEmpty() && arr[stk.peek()][1] < f) {
stk.pop();
}
if (!stk.isEmpty()) {
left[i] = stk.peek();
}
stk.push(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
int f = arr[i][1];
while (!stk.isEmpty() && arr[stk.peek()][1] <= f) {
stk.pop();
}
if (!stk.isEmpty()) {
right[i] = stk.peek();
}
stk.push(i);
}
Arrays.sort(arr, (a, b) -> b[2] - a[2]);
long ans = 1;
for (int[] e : arr) {
int i = e[0], x = e[2];
int l = left[i], r = right[i];
long cnt = (long) (i - l) * (r - i);
if (cnt <= k) {
ans = ans * qpow(x, cnt) % mod;
k -= cnt;
} else {
ans = ans * qpow(x, k) % mod;
break;
}
}
return (int) ans;
}
private int primeFactors(int n) {
int i = 2;
Set<Integer> ans = new HashSet<>();
while (i <= n / i) {
while (n % i == 0) {
ans.add(i);
n /= i;
}
++i;
}
if (n > 1) {
ans.add(n);
}
return ans.size();
}
private int qpow(long a, long n) {
long ans = 1;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
ans = ans * a % mod;
}
a = a * a % mod;
}
return (int) ans;
}
}
// Accepted solution for LeetCode #2818: Apply Operations to Maximize Score
func maximumScore(nums []int, k int) int {
n := len(nums)
const mod = 1e9 + 7
qpow := func(a, n int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
arr := make([][3]int, n)
left := make([]int, n)
right := make([]int, n)
for i, x := range nums {
left[i] = -1
right[i] = n
arr[i] = [3]int{i, primeFactors(x), x}
}
stk := []int{}
for _, e := range arr {
i, f := e[0], e[1]
for len(stk) > 0 && arr[stk[len(stk)-1]][1] < f {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
f := arr[i][1]
for len(stk) > 0 && arr[stk[len(stk)-1]][1] <= f {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
sort.Slice(arr, func(i, j int) bool { return arr[i][2] > arr[j][2] })
ans := 1
for _, e := range arr {
i, x := e[0], e[2]
l, r := left[i], right[i]
cnt := (i - l) * (r - i)
if cnt <= k {
ans = ans * qpow(x, cnt) % mod
k -= cnt
} else {
ans = ans * qpow(x, k) % mod
break
}
}
return ans
}
func primeFactors(n int) int {
i := 2
ans := map[int]bool{}
for i <= n/i {
for n%i == 0 {
ans[i] = true
n /= i
}
i++
}
if n > 1 {
ans[n] = true
}
return len(ans)
}
# Accepted solution for LeetCode #2818: Apply Operations to Maximize Score
def primeFactors(n):
i = 2
ans = set()
while i * i <= n:
while n % i == 0:
ans.add(i)
n //= i
i += 1
if n > 1:
ans.add(n)
return len(ans)
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
mod = 10**9 + 7
arr = [(i, primeFactors(x), x) for i, x in enumerate(nums)]
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, f, x in arr:
while stk and stk[-1][0] < f:
stk.pop()
if stk:
left[i] = stk[-1][1]
stk.append((f, i))
stk = []
for i, f, x in arr[::-1]:
while stk and stk[-1][0] <= f:
stk.pop()
if stk:
right[i] = stk[-1][1]
stk.append((f, i))
arr.sort(key=lambda x: -x[2])
ans = 1
for i, f, x in arr:
l, r = left[i], right[i]
cnt = (i - l) * (r - i)
if cnt <= k:
ans = ans * pow(x, cnt, mod) % mod
k -= cnt
else:
ans = ans * pow(x, k, mod) % mod
break
return ans
// Accepted solution for LeetCode #2818: Apply Operations to Maximize Score
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2818: Apply Operations to Maximize Score
// class Solution {
// private final int mod = (int) 1e9 + 7;
//
// public int maximumScore(List<Integer> nums, int k) {
// int n = nums.size();
// int[][] arr = new int[n][0];
// for (int i = 0; i < n; ++i) {
// arr[i] = new int[] {i, primeFactors(nums.get(i)), nums.get(i)};
// }
// int[] left = new int[n];
// int[] right = new int[n];
// Arrays.fill(left, -1);
// Arrays.fill(right, n);
// Deque<Integer> stk = new ArrayDeque<>();
// for (int[] e : arr) {
// int i = e[0], f = e[1];
// while (!stk.isEmpty() && arr[stk.peek()][1] < f) {
// stk.pop();
// }
// if (!stk.isEmpty()) {
// left[i] = stk.peek();
// }
// stk.push(i);
// }
// stk.clear();
// for (int i = n - 1; i >= 0; --i) {
// int f = arr[i][1];
// while (!stk.isEmpty() && arr[stk.peek()][1] <= f) {
// stk.pop();
// }
// if (!stk.isEmpty()) {
// right[i] = stk.peek();
// }
// stk.push(i);
// }
// Arrays.sort(arr, (a, b) -> b[2] - a[2]);
// long ans = 1;
// for (int[] e : arr) {
// int i = e[0], x = e[2];
// int l = left[i], r = right[i];
// long cnt = (long) (i - l) * (r - i);
// if (cnt <= k) {
// ans = ans * qpow(x, cnt) % mod;
// k -= cnt;
// } else {
// ans = ans * qpow(x, k) % mod;
// break;
// }
// }
// return (int) ans;
// }
//
// private int primeFactors(int n) {
// int i = 2;
// Set<Integer> ans = new HashSet<>();
// while (i <= n / i) {
// while (n % i == 0) {
// ans.add(i);
// n /= i;
// }
// ++i;
// }
// if (n > 1) {
// ans.add(n);
// }
// return ans.size();
// }
//
// private int qpow(long a, long n) {
// long ans = 1;
// for (; n > 0; n >>= 1) {
// if ((n & 1) == 1) {
// ans = ans * a % mod;
// }
// a = a * a % mod;
// }
// return (int) ans;
// }
// }
// Accepted solution for LeetCode #2818: Apply Operations to Maximize Score
function maximumScore(nums: number[], k: number): number {
const mod = 10 ** 9 + 7;
const n = nums.length;
const arr: number[][] = Array(n)
.fill(0)
.map(() => Array(3).fill(0));
const left: number[] = Array(n).fill(-1);
const right: number[] = Array(n).fill(n);
for (let i = 0; i < n; ++i) {
arr[i] = [i, primeFactors(nums[i]), nums[i]];
}
const stk: number[] = [];
for (const [i, f, _] of arr) {
while (stk.length && arr[stk.at(-1)!][1] < f) {
stk.pop();
}
if (stk.length) {
left[i] = stk.at(-1)!;
}
stk.push(i);
}
stk.length = 0;
for (let i = n - 1; i >= 0; --i) {
const f = arr[i][1];
while (stk.length && arr[stk.at(-1)!][1] <= f) {
stk.pop();
}
if (stk.length) {
right[i] = stk.at(-1)!;
}
stk.push(i);
}
arr.sort((a, b) => b[2] - a[2]);
let ans = 1n;
for (const [i, _, x] of arr) {
const l = left[i];
const r = right[i];
const cnt = (i - l) * (r - i);
if (cnt <= k) {
ans = (ans * qpow(BigInt(x), cnt, mod)) % BigInt(mod);
k -= cnt;
} else {
ans = (ans * qpow(BigInt(x), k, mod)) % BigInt(mod);
break;
}
}
return Number(ans);
}
function primeFactors(n: number): number {
let i = 2;
const s: Set<number> = new Set();
while (i * i <= n) {
while (n % i === 0) {
s.add(i);
n = Math.floor(n / i);
}
++i;
}
if (n > 1) {
s.add(n);
}
return s.size;
}
function qpow(a: bigint, n: number, mod: number): bigint {
let ans = 1n;
for (; n; n >>>= 1) {
if (n & 1) {
ans = (ans * a) % BigInt(mod);
}
a = (a * a) % BigInt(mod);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.