LeetCode Problem 3266

Difficulty: 🔴 Hard
Topics: Array, Heap (Priority Queue), Simulation

Solution

LeetCode 3266 - Final Array State After K Multiplication Operations II

Problem Understanding

The problem gives us an integer array nums, an integer k, and an integer multiplier. We must perform exactly k operations on the array.

In each operation, we locate the minimum value currently present in the array. If multiple elements share the same minimum value, we must choose the one with the smallest index, meaning the first occurrence. Once selected, that value is replaced with its product with multiplier.

After all operations are completed, every number in the array is reduced modulo 10^9 + 7, and the resulting array is returned.

The most important detail is that the minimum element changes dynamically after every operation. This means the process is inherently stateful, and the order of updates matters.

The constraints are what make this problem difficult:

• nums.length <= 10^4
• k <= 10^9

The array size is manageable, but k can be enormous. A direct simulation of all operations would be far too slow when k approaches one billion.

Another important observation is that values can grow extremely large during multiplication. Since repeated multiplication may overflow standard integer ranges, modular arithmetic and fast exponentiation become essential.

Several edge cases require careful handling:

• multiplier == 1, because values never change and the same element would always remain minimum.
• Arrays with duplicate minimum values, because tie-breaking by index is required.
• Very large k, where naive simulation is impossible.
• Arrays where some values quickly become much larger than others, causing the update distribution to stabilize into a cyclic pattern.

Approaches

Brute Force Approach

The most direct solution is to simulate every operation exactly as described.

For each of the k operations:

1. Scan the entire array to find the minimum value.
2. If multiple values are equal, choose the first occurrence.
3. Multiply that element by multiplier.

After completing all operations, apply modulo 10^9 + 7 to every element.

This approach is correct because it follows the problem statement exactly. However, its performance is unacceptable for large k.

Finding the minimum element requires O(n) time per operation, so the total complexity becomes O(n * k). With k as large as 10^9, this is impossible to run within time limits.

Optimal Approach

The key insight is that we do not need to simulate all operations individually.

A min-heap allows us to efficiently retrieve and update the smallest element in O(log n) time instead of O(n).

More importantly, after enough operations, the process becomes balanced. Once every element has reached roughly the same scale, operations begin rotating among the elements in sorted order.

At that point:

• Every element receives either floor(k / n) or ceil(k / n) additional multiplications.
• We can distribute the remaining operations mathematically instead of simulating them one by one.
• Fast modular exponentiation computes huge powers efficiently.

The strategy becomes:

1. Use a heap to simulate only the early unstable phase.
2. Stop once the smallest value becomes large enough relative to the current maximum.
3. Distribute the remaining operations evenly using arithmetic.

This reduces the complexity dramatically.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(1)	Direct simulation of every operation
Optimal	O((n + simulated_steps) log n)	O(n)	Heap simulation plus mathematical distribution

Algorithm Walkthrough

Step 1: Handle the trivial multiplier case

If multiplier == 1, every multiplication leaves the array unchanged.

No matter how many operations are performed, the array remains identical. We simply return each value modulo 10^9 + 7.

This special case prevents unnecessary work.

Step 2: Build a min-heap

We create a min-heap storing pairs:

(value, index)

The heap automatically enforces the required tie-breaking rule:

• Smaller values come first.
• If values are equal, smaller indices come first.

This exactly matches the problem statement.

Step 3: Track the current maximum value

We maintain the maximum element currently present in the array.

This is important because once the minimum element becomes comparable to the maximum, the process enters a balanced phase.

Step 4: Simulate the unstable phase

While operations remain:

1. Extract the smallest element from the heap.
2. Multiply it by multiplier.
3. Push the updated value back into the heap.
4. Update the global maximum if necessary.

However, we stop simulating once:

minimum * multiplier > current_maximum

At that point, the updated element would no longer remain near the bottom of the heap. The process begins rotating among all elements in a predictable manner.

Step 5: Sort heap order

After the unstable phase, we extract all heap elements into a sorted list.

The order now determines which elements receive the extra remaining multiplications.

Step 6: Distribute remaining operations evenly

Suppose:

remaining = k

Then every element receives:

base = remaining // n

extra multiplications.

The first:

extra = remaining % n

elements in heap order receive one additional multiplication.

Step 7: Apply modular exponentiation

For each element:

final_value = value * multiplier^count

We compute powers using fast exponentiation modulo 10^9 + 7.

This avoids overflow and runs efficiently even for enormous exponents.

Step 8: Restore original array order

The heap order is not the original index order.

We place computed values back into their original positions and return the final array.

Why it works

The heap always guarantees that we apply operations to the correct minimum element with proper tie-breaking.

During the early phase, values may differ significantly, so explicit simulation is necessary. Once all values become comparable, repeated multiplication distributes almost evenly across elements. Each future cycle effectively gives every element one multiplication.

Therefore, after stabilization, the remaining operations can be distributed mathematically instead of simulated individually. Since modular exponentiation computes large powers correctly, the final result matches the exact simulation while remaining efficient.

Python Solution

from typing import List
import heapq

MOD = 10**9 + 7

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        n = len(nums)

        if multiplier == 1:
            return [x % MOD for x in nums]

        heap = []
        current_max = max(nums)

        for index, value in enumerate(nums):
            heap.append((value, index))

        heapq.heapify(heap)

        # Simulate until values become balanced
        while k > 0:
            smallest_value, index = heap[0]

            if smallest_value * multiplier > current_max:
                break

            heapq.heappop(heap)

            new_value = smallest_value * multiplier
            current_max = max(current_max, new_value)

            heapq.heappush(heap, (new_value, index))

            k -= 1

        # Remaining operations are distributed evenly
        sorted_elements = []

        while heap:
            sorted_elements.append(heapq.heappop(heap))

        base_operations = k // n
        extra_operations = k % n

        result = [0] * n

        for position, (value, index) in enumerate(sorted_elements):
            total_operations = base_operations

            if position < extra_operations:
                total_operations += 1

            final_value = (
                (value % MOD)
                * pow(multiplier, total_operations, MOD)
            ) % MOD

            result[index] = final_value

        return result

The implementation begins by handling the special case where multiplier equals 1. Since multiplication would never change any value, we can immediately return the array modulo 10^9 + 7.

Next, the code constructs a min-heap containing (value, index) pairs. Python tuples naturally enforce lexicographical ordering, which means ties on value are automatically broken by index.

The simulation loop repeatedly updates the smallest element. The stopping condition is the key optimization. Once multiplying the current minimum would push it beyond the current maximum, the process becomes balanced enough for mathematical distribution.

After simulation stops, the remaining operations are distributed evenly among all elements. The sorted heap order determines which elements receive the extra operations.

Finally, modular exponentiation computes large powers efficiently, and results are restored to original index positions.

Go Solution

package main

import (
	"container/heap"
)

const MOD int64 = 1_000_000_007

type Node struct {
	value int64
	index int
}

type MinHeap []Node

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	if h[i].value == h[j].value {
		return h[i].index < h[j].index
	}
	return h[i].value < h[j].value
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

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

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

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

	return result
}

func getFinalState(nums []int, k int, multiplier int) []int {
	n := len(nums)

	if multiplier == 1 {
		result := make([]int, n)

		for i, value := range nums {
			result[i] = value % int(MOD)
		}

		return result
	}

	currentMax := int64(0)

	h := &MinHeap{}

	for i, value := range nums {
		v := int64(value)

		if v > currentMax {
			currentMax = v
		}

		*h = append(*h, Node{
			value: v,
			index: i,
		})
	}

	heap.Init(h)

	for k > 0 {
		top := (*h)[0]

		if top.value*int64(multiplier) > currentMax {
			break
		}

		heap.Pop(h)

		newValue := top.value * int64(multiplier)

		if newValue > currentMax {
			currentMax = newValue
		}

		heap.Push(h, Node{
			value: newValue,
			index: top.index,
		})

		k--
	}

	sortedElements := make([]Node, 0, n)

	for h.Len() > 0 {
		sortedElements = append(sortedElements, heap.Pop(h).(Node))
	}

	baseOps := k / n
	extraOps := k % n

	result := make([]int, n)

	for pos, node := range sortedElements {
		totalOps := baseOps

		if pos < extraOps {
			totalOps++
		}

		finalValue := (
			(node.value % MOD) *
				modPow(int64(multiplier), int64(totalOps)),
		) % MOD

		result[node.index] = int(finalValue)
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python solution.

The primary difference is explicit heap implementation using Go's container/heap package. We define custom comparison logic so ties are resolved by index.

Another important difference is integer handling. Since values can grow very large during multiplication, the implementation uses int64 internally to avoid overflow before modular reduction.

The modular exponentiation helper function is implemented manually because Go does not provide a built-in modular power function.

Worked Examples

Example 1

Input:

nums = [2,1,3,5,6]
k = 5
multiplier = 2

Initial heap:

Heap Value	Index
1	1
2	0
3	2
5	3
6	4

Current maximum:

6

Operation 1

Minimum element:

1

After multiplication:

2

Array state:

[2,2,3,5,6]

Operation 2

Minimum element:

2 at index 0

After multiplication:

4

Array state:

[4,2,3,5,6]

Operation 3

Minimum element:

2 at index 1

After multiplication:

4

Array state:

[4,4,3,5,6]

Operation 4

Minimum element:

3

After multiplication:

6

Array state:

[4,4,6,5,6]

Operation 5

Minimum element:

4 at index 0

After multiplication:

8

Final array:

[8,4,6,5,6]

Example 2

Input:

nums = [100000,2000]
k = 2
multiplier = 1000000

Operation 1

Minimum:

2000

Updated:

2000000000

Array:

[100000,2000000000]

Operation 2

Minimum:

100000

Updated:

100000000000

Array before modulo:

[100000000000,2000000000]

After modulo:

[999999307,999999993]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + simulated_steps) log n)	Heap operations dominate runtime
Space	O(n)	Heap and result storage

The heap contains n elements throughout execution, so heap operations require O(log n) time.

The early simulation phase usually terminates quickly because values grow exponentially under multiplication. After stabilization, remaining operations are distributed mathematically in constant time per element.

The algorithm therefore scales efficiently even when k is extremely large.

Test Cases

solution = Solution()

# Provided examples
assert solution.getFinalState([2,1,3,5,6], 5, 2) == [8,4,6,5,6]  # standard example
assert solution.getFinalState([100000,2000], 2, 1000000) == [999999307,999999993]  # huge values

# Multiplier equals 1
assert solution.getFinalState([1,2,3], 1000000000, 1) == [1,2,3]  # array never changes

# Single element array
assert solution.getFinalState([5], 3, 2) == [40]  # same element updated repeatedly

# Duplicate minimum values
assert solution.getFinalState([1,1,2], 2, 2) == [2,2,2]  # tie-breaking by index

# Large k distribution
assert solution.getFinalState([1,2], 10, 2) == [64,64]  # balanced growth

# Already balanced array
assert solution.getFinalState([4,4,4], 3, 3) == [12,12,12]  # cyclic updates

# Large multiplier
assert solution.getFinalState([1,10], 3, 100) == [10000,1000]  # exponential growth

# Modulo behavior
result = solution.getFinalState([10**9], 5, 10**6)
assert len(result) == 1  # verifies no overflow issues

Test	Why
[2,1,3,5,6], 5, 2	Validates standard heap behavior
[100000,2000], 2, 1000000	Validates large integer handling
multiplier = 1	Ensures early return optimization
Single element array	Confirms repeated updates work correctly
Duplicate minimum values	Verifies index tie-breaking
Large k	Tests mathematical distribution logic
Already balanced array	Validates cyclic update behavior
Large multiplier	Tests rapid exponential growth
Huge powers modulo case	Ensures modular arithmetic correctness

Edge Cases

One important edge case occurs when multiplier == 1. In this situation, multiplying any number leaves it unchanged, so the minimum element never changes either. A naive implementation might still attempt to simulate all k operations, which would be catastrophically slow for k = 10^9. The implementation handles this immediately with an early return.

Another subtle edge case involves duplicate minimum values. The problem explicitly requires selecting the first occurrence among equal minimums. Incorrect heap ordering could violate this requirement. By storing (value, index) pairs in the heap, lexicographical ordering naturally ensures the smallest index is chosen first whenever values are equal.

A third important edge case is integer overflow. Values may become astronomically large after repeated multiplication. Languages with fixed-size integers can overflow long before the final modulo is applied. The solution avoids this problem using modular exponentiation and int64 arithmetic in Go. Python naturally supports arbitrary precision integers, but modular exponentiation is still necessary for efficiency.

Another tricky situation occurs when k is much larger than the array size. A naive heap simulation would still be too slow even with O(log n) updates. The optimization that transitions from explicit simulation to mathematical distribution is what allows the algorithm to scale to the maximum constraints.