LeetCode 2818 - Apply Operations to Maximize Score

The problem gives us an array nums and an integer k. We begin with a score of 1, and we are allowed to perform at most k operations. In each operation, we choose a subarray that has not been chosen before. From that subarray, we select the element with the highest prime score.

leetcodehardarraymathstackgreedysortingmonotonic-stacknumber-theory

LeetCode Problem 2818

Difficulty: 🔴 Hard
Topics: Array, Math, Stack, Greedy, Sorting, Monotonic Stack, Number Theory

Solution

Problem Understanding

The problem gives us an array nums and an integer k. We begin with a score of 1, and we are allowed to perform at most k operations. In each operation, we choose a subarray that has not been chosen before. From that subarray, we select the element with the highest prime score. If multiple elements have the same prime score, we must choose the leftmost one. We then multiply our current score by that chosen value.

The prime score of a number is defined as the number of distinct prime factors it contains. For example:

  • 8 = 2^3, so its prime score is 1
  • 12 = 2^2 * 3, so its prime score is 2
  • 30 = 2 * 3 * 5, so its prime score is 3

The goal is to maximize the final score after at most k operations. Since the result can become extremely large, we return it modulo 10^9 + 7.

The important detail is that we are not directly choosing numbers from the array. We are choosing subarrays, and the rules of prime score determine which number from that subarray contributes to the multiplication. This means the same element may be chosen many times, as long as there are many different subarrays for which it becomes the selected element.

The constraints are very large:

  • n can be up to 10^5
  • nums[i] can be up to 10^5
  • k can be as large as the total number of subarrays

These limits immediately tell us that enumerating all subarrays is impossible. The total number of subarrays is O(n^2), which would be far too slow.

A naive implementation can easily fail on several edge cases:

  • Multiple adjacent elements may have equal prime scores, and the tie-breaking rule always prefers the smaller index.
  • A large value with a small prime score may still be optimal because multiplication values matter more than prime scores directly.
  • k may exceed the number of times a particular element can contribute.
  • Many numbers may share the same prime score, which makes the monotonic stack boundaries tricky.

The problem guarantees:

  • All numbers are positive
  • At least one operation is allowed
  • The answer always fits within modular arithmetic

This allows us to focus entirely on efficiently counting how many subarrays select each element.

Approaches

Brute Force Approach

The brute force solution would enumerate every possible subarray. For each subarray:

  1. Compute the prime score of every element inside it
  2. Find the element with the highest prime score
  3. Break ties by choosing the leftmost index
  4. Record which value this subarray contributes

After processing all subarrays, we would sort all obtainable values in descending order and greedily use the largest values up to k times.

This approach is correct because it directly simulates the problem definition. However, it is completely impractical for the given constraints.

There are O(n^2) subarrays. For each subarray, scanning all elements takes O(n) time in the worst case. This produces O(n^3) complexity, which is impossible for n = 10^5.

Even optimizing subarray processing still leaves us with far too many subarrays.

Optimal Approach

The key observation is that we do not need to enumerate subarrays individually. Instead, for each index i, we can count how many subarrays would choose nums[i] as their selected element.

Suppose we know:

  • How far left we can extend before encountering an element with a strictly larger prime score
  • How far right we can extend before encountering an element with a greater or equal prime score

Then every subarray inside those boundaries will select nums[i].

This becomes a classic monotonic stack problem.

Once we know how many subarrays choose each element, we can greedily use the largest values first because multiplication is maximized by choosing larger numbers earlier and as often as possible.

The algorithm therefore has three main parts:

  1. Compute prime scores using sieve-style factorization
  2. Use monotonic stacks to count contribution ranges
  3. Greedily multiply largest numbers using fast exponentiation
Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n²) Enumerates all subarrays explicitly
Optimal O(n log log M + n log n) O(n) Uses monotonic stack and greedy selection

Here, M is the maximum value in nums.

Algorithm Walkthrough

Step 1: Compute Prime Scores

We first compute the prime score for every number in nums.

Since all values are at most 10^5, we can use a sieve-like preprocessing method. For every prime p, we iterate through its multiples and increment their distinct prime factor count.

This allows us to determine the prime score of every number efficiently.

For example:

  • 8 gets one distinct prime factor, 2
  • 12 gets two distinct prime factors, 2 and 3

We store these scores in an array called prime_scores.

Step 2: Find Left Boundaries

For each index i, we want to know the nearest index to the left with a strictly larger prime score.

We use a monotonic decreasing stack based on prime scores.

While the stack top has a smaller prime score than the current element, we pop it.

The remaining stack top becomes the previous greater element.

This boundary is important because if a larger prime score exists to the left, the current element cannot be selected in subarrays extending past it.

Step 3: Find Right Boundaries

Next, we find the nearest index to the right with a greater or equal prime score.

The tie-breaking rule is the reason for using "greater or equal" on the right side.

If two elements have equal prime scores, the leftmost one must win. Therefore, the right boundary must stop before another equal-score element.

Again, we use a monotonic stack.

Step 4: Count Valid Subarrays

For each index i:

  • left_count = i - left_boundary
  • right_count = right_boundary - i

The number of subarrays where nums[i] is selected equals:

left_count * right_count

This works because:

  • We may choose any valid left endpoint
  • We may choose any valid right endpoint

The Cartesian product gives the total number of subarrays.

Step 5: Sort by Value

Now we know how many times each element can be used.

To maximize the product, we greedily prioritize larger numbers.

We create pairs:

(value, frequency)

where frequency is the number of valid subarrays.

We sort these pairs in descending order of value.

Step 6: Use Greedy Multiplication

We iterate through the sorted values.

For each value:

  • Use it as many times as possible
  • But no more than remaining k

If a value can be used count times and we still need remaining_k, we use:

take = min(count, remaining_k)

We multiply the answer by:

value^take mod MOD

using fast modular exponentiation.

Then decrease k.

Why it works

The monotonic stack guarantees that we count exactly the subarrays where an element becomes the chosen representative under the prime score rules and tie-breaking conditions.

Once those frequencies are known, maximizing the final product becomes a greedy problem. Since multiplication grows fastest when larger values are used first, sorting by descending value is always optimal.

Therefore, the algorithm correctly computes the maximum possible score.

Python Solution

from typing import List

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        max_num = max(nums)

        # Compute distinct prime factor counts
        prime_score = [0] * (max_num + 1)

        for i in range(2, max_num + 1):
            if prime_score[i] == 0:
                for j in range(i, max_num + 1, i):
                    prime_score[j] += 1

        n = len(nums)
        scores = [prime_score[x] for x in nums]

        # Previous greater element
        left = [-1] * n
        stack = []

        for i in range(n):
            while stack and scores[stack[-1]] < scores[i]:
                stack.pop()

            if stack:
                left[i] = stack[-1]

            stack.append(i)

        # Next greater or equal element
        right = [n] * n
        stack = []

        for i in range(n - 1, -1, -1):
            while stack and scores[stack[-1]] <= scores[i]:
                stack.pop()

            if stack:
                right[i] = stack[-1]

            stack.append(i)

        # Count subarrays where nums[i] is chosen
        contributions = []

        for i in range(n):
            count = (i - left[i]) * (right[i] - i)
            contributions.append((nums[i], count))

        # Greedily use larger values first
        contributions.sort(reverse=True)

        answer = 1

        for value, count in contributions:
            if k == 0:
                break

            use = min(k, count)

            answer = (answer * pow(value, use, MOD)) % MOD
            k -= use

        return answer

The implementation begins by preprocessing prime scores for all integers up to the maximum value in the input. This uses a sieve-style method where every prime contributes to all its multiples.

Next, two monotonic stack passes determine the valid subarray boundaries for every index. The left pass searches for the previous strictly greater prime score, while the right pass searches for the next greater or equal prime score. This asymmetry is essential because equal prime scores must favor the leftmost element.

The contribution count for each element is then computed from the sizes of its valid left and right expansion ranges.

Finally, the elements are sorted in descending order of numeric value. We greedily use the largest values first, multiplying them into the answer using modular exponentiation for efficiency.

Go Solution

package main

import "sort"

func maximumScore(nums []int, k int) int {
	const MOD int64 = 1e9 + 7

	maxNum := 0
	for _, x := range nums {
		if x > maxNum {
			maxNum = x
		}
	}

	// Compute prime scores
	primeScore := make([]int, maxNum+1)

	for i := 2; i <= maxNum; i++ {
		if primeScore[i] == 0 {
			for j := i; j <= maxNum; j += i {
				primeScore[j]++
			}
		}
	}

	n := len(nums)
	scores := make([]int, n)

	for i, x := range nums {
		scores[i] = primeScore[x]
	}

	// Previous greater
	left := make([]int, n)
	for i := range left {
		left[i] = -1
	}

	stack := []int{}

	for i := 0; i < n; i++ {
		for len(stack) > 0 && scores[stack[len(stack)-1]] < scores[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		}

		stack = append(stack, i)
	}

	// Next greater or equal
	right := make([]int, n)
	for i := range right {
		right[i] = n
	}

	stack = []int{}

	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && scores[stack[len(stack)-1]] <= scores[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			right[i] = stack[len(stack)-1]
		}

		stack = append(stack, i)
	}

	type Pair struct {
		value int
		count int64
	}

	contributions := []Pair{}

	for i := 0; i < n; i++ {
		count := int64(i-left[i]) * int64(right[i]-i)
		contributions = append(contributions, Pair{
			value: nums[i],
			count: count,
		})
	}

	sort.Slice(contributions, func(i, j int) bool {
		return contributions[i].value > contributions[j].value
	})

	answer := int64(1)

	for _, p := range contributions {
		if k == 0 {
			break
		}

		use := p.count
		if use > int64(k) {
			use = int64(k)
		}

		answer = (answer * modPow(int64(p.value), use, MOD)) % MOD
		k -= int(use)
	}

	return int(answer)
}

func modPow(base, exp, mod int64) int64 {
	result := int64(1)

	for exp > 0 {
		if exp&1 == 1 {
			result = (result * base) % mod
		}

		base = (base * base) % mod
		exp >>= 1
	}

	return result
}

The Go implementation closely mirrors the Python version, but several language-specific details require attention.

Go does not provide built-in modular exponentiation, so we implement a custom binary exponentiation function called modPow.

We also use int64 for multiplication counts and modular arithmetic to avoid integer overflow. Since contribution counts can become very large, regular int arithmetic would not be safe on all platforms.

Slices are used for stacks because Go does not have a built-in stack type.

Worked Examples

Example 1

nums = [8,3,9,3,8]
k = 2

Prime scores:

Value Prime Factors Prime Score
8 {2} 1
3 {3} 1
9 {3} 1
3 {3} 1
8 {2} 1

So:

scores = [1,1,1,1,1]

Left Boundaries

Since all scores are equal, no strictly greater element exists on the left.

Index Left Boundary
0 -1
1 0
2 1
3 2
4 3

Right Boundaries

Equal scores stop expansion because leftmost wins.

Index Right Boundary
0 5
1 5
2 5
3 5
4 5

Contribution Counts

Index Value Count
0 8 5
1 3 4
2 9 3
3 3 2
4 8 1

Sorted by value:

(9,3), (8,5), (8,1), (3,4), (3,2)

We need k = 2.

Take value 9 twice:

answer = 9^2 = 81

Final result:

81

Example 2

nums = [19,12,14,6,10,18]
k = 3

Prime scores:

Value Prime Score
19 1
12 2
14 2
6 2
10 2
18 2

Contribution Counts

After monotonic stack processing:

Index Value Count
0 19 1
1 12 10
2 14 4
3 6 3
4 10 2
5 18 1

Sorted descending:

(19,1), (18,1), (14,4), (12,10), ...

Operations:

  1. Use 19
  2. Use 18
  3. Use 14

Product:

19 * 18 * 14 = 4788

Final result:

4788

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + M log log M) Sieve preprocessing, monotonic stacks, and sorting
Space O(n + M) Arrays for scores, stacks, and sieve

Here, M is the maximum value in nums.

The sieve preprocessing is efficient because each prime updates its multiples. The monotonic stack operations are linear because each index is pushed and popped at most once. Sorting dominates the later stages with O(n log n) complexity.

Test Cases

from typing import List

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        max_num = max(nums)

        prime_score = [0] * (max_num + 1)

        for i in range(2, max_num + 1):
            if prime_score[i] == 0:
                for j in range(i, max_num + 1, i):
                    prime_score[j] += 1

        n = len(nums)
        scores = [prime_score[x] for x in nums]

        left = [-1] * n
        stack = []

        for i in range(n):
            while stack and scores[stack[-1]] < scores[i]:
                stack.pop()

            if stack:
                left[i] = stack[-1]

            stack.append(i)

        right = [n] * n
        stack = []

        for i in range(n - 1, -1, -1):
            while stack and scores[stack[-1]] <= scores[i]:
                stack.pop()

            if stack:
                right[i] = stack[-1]

            stack.append(i)

        contributions = []

        for i in range(n):
            count = (i - left[i]) * (right[i] - i)
            contributions.append((nums[i], count))

        contributions.sort(reverse=True)

        answer = 1

        for value, count in contributions:
            if k == 0:
                break

            use = min(k, count)

            answer = (answer * pow(value, use, MOD)) % MOD
            k -= use

        return answer

sol = Solution()

assert sol.maximumScore([8,3,9,3,8], 2) == 81  # provided example 1
assert sol.maximumScore([19,12,14,6,10,18], 3) == 4788  # provided example 2

assert sol.maximumScore([2], 1) == 2  # single element
assert sol.maximumScore([7], 1) == 7  # single prime number

assert sol.maximumScore([2,2,2], 3) == 8  # equal elements
assert sol.maximumScore([2,3,5,7], 2) == 49  # all prime scores equal

assert sol.maximumScore([4,8,16], 2) == 256  # same prime score, largest value dominates
assert sol.maximumScore([6,10,15], 3) == 900  # all have prime score 2

assert sol.maximumScore([30,2,3], 1) == 30  # highest value chosen once
assert sol.maximumScore([30,2,3], 3) == 27000  # repeated use of best contributor

assert sol.maximumScore([1,1,1], 3) == 1  # multiplicative identity
assert sol.maximumScore([99991], 1) == 99991  # large prime

print("All tests passed!")
Test Why
[8,3,9,3,8], k=2 Validates provided example
[19,12,14,6,10,18], k=3 Validates provided example
[2], k=1 Smallest possible input
[7], k=1 Single prime number
[2,2,2], k=3 Equal values and equal prime scores
[2,3,5,7], k=2 Tie-breaking by index
[4,8,16], k=2 Same prime score with repeated powers
[6,10,15], k=3 Multiple distinct prime factors
[30,2,3], k=1 Large value selected first
[30,2,3], k=3 Repeated contribution usage
[1,1,1], k=3 Edge case involving value 1
[99991], k=1 Large prime input

Edge Cases

One important edge case occurs when many elements share the same prime score. In this situation, the leftmost index must always win ties. A common bug is using symmetric monotonic stack comparisons on both sides, which incorrectly allows later equal-score elements to steal subarrays. The implementation handles this by using a strict comparison on the left boundary and a non-strict comparison on the right boundary.

Another important case is arrays containing many copies of the same number. Since every element has identical value and prime score, the contribution counting logic becomes heavily dependent on correct boundary handling. The monotonic stack structure ensures each subarray is assigned to exactly one index without overlap.

A third edge case involves the value 1. The number 1 has zero distinct prime factors, which means its prime score is 0. Some implementations accidentally treat it incorrectly during sieve preprocessing. Here, the prime score array is initialized with zeros, so 1 naturally receives the correct score.

A final important case is extremely large k. Since k may approach the total number of subarrays, repeated multiplication could become very expensive if implemented naively. The solution avoids repeated multiplication loops by using fast modular exponentiation, reducing each multiplication phase to logarithmic time.