3266. Final Array State After K Multiplication Operations II

HardArraySimulationHeap (Priority Queue)

Problem Description

You are given an integer array nums, an integer k, and an integer multiplier. Your task is to perform k operations on nums. In each operation:

Identify the minimum value x in nums. If there are multiple occurrences of the minimum value, choose the one that appears first.
Replace the selected minimum value x with x * multiplier.

After completing all k operations, apply modulo (10^9 + 7) to each value in nums. Your goal is to return an integer array that represents the final state of nums after the k operations and the modulo application.

Intuition

To solve the problem efficiently, we can utilize a priority queue (min-heap) to track the minimum values in nums quickly. The core idea is to repeatedly find and multiply the minimum element until we perform k operations or reach a case where multiplying further is unnecessary (i.e., when all elements are greater than or equal to the maximum element m in nums).

Initial Priority Queue: Use the min-heap to access the smallest element efficiently. This helps in quickly identifying and replacing the minimum value in each operation.
Replacing Minimum Values: For each operation, replace the smallest element by multiplying it with multiplier. Push the updated value back into the heap to maintain the order.
Handling Remaining Operations: Once the operations based on the heap are exhausted (either all elements exceed the initial max value or all k operations are performed), the distribution of remaining operations should be considered. Since each remaining operation involves turning the smallest element into the largest, the modulo of k divided by the size of nums gives the count of smaller elements which will receive one extra multiplication.
Modular Arithmetic: After performing the necessary multiplications, apply the modulo operation to ensure values fit within the required range, using fast exponentiation for efficient calculation.

This approach balances the problem's requirements with computational efficiency, using a combination of heap operations, arithmetic manipulations, and modular constraints to achieve the desired outcome.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution uses a combination of a priority queue (min-heap) and modular arithmetic to achieve the desired transformations on the nums array.

Steps:

Priority Queue Initialization:
- Begin by converting nums into a min-heap using Python's heapq. This allows efficient retrieval and replacement of the minimum element.
- Compile a list of tuples (x, i) where x is each element in nums and i is its index. This helps keep track of the original indices after modifying elements.
```
pq = [(x, i) for i, x in enumerate(nums)]
heapq.heapify(pq)
```

Perform k Operations:

Execute up to k operations or until no change can occur (when the minimum element in the heap is not less than m, the maximum number in nums).
For each operation, pop the smallest element from the heap, multiply it by multiplier, and push it back.

while k and pq[0][0] < m:
    x, i = heapq.heappop(pq)
    heapq.heappush(pq, (x * multiplier, i))
    k -= 1

Final Adjustments:

If any operations remain, distribute them evenly across the elements using integer division and modulo operations.
Sort the heap to prepare for final transformations, precisely adjusting each element based on its number of necessary multiplications remaining.

pq.sort()
n = len(nums)
mod = 10**9 + 7
for i, (x, j) in enumerate(pq):
    nums[j] = x * pow(multiplier, k // n + int(i < k % n), mod) % mod

Returning Results:
- The modified nums array is returned, containing the final results of the operations after modulo.

The solution effectively leverages the properties of priority queues to handle frequent minimum element access and updates efficiently. By balancing initial and remaining operations, it efficiently produces the correct final state of nums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example where nums = [3, 5, 1, 4], k = 2, and multiplier = 3. We will walk through the solution approach step-by-step.

Priority Queue Initialization:
- Convert nums into a min-heap using Python's heapq. This allows us to efficiently retrieve and replace the minimum element.
- Create a list of tuples (x, i) where x is the element and i is its index to track original positions. After initialization, the priority queue will be [(1, 2), (4, 3), (3, 0), (5, 1)].
Perform k Operations:
- First Operation: Pop (1, 2) from the heap (minimum element 1 at index 2), multiply it by 3 to get 3, and push (3, 2) back into the heap.
  - The heap is now [(3, 0), (3, 2), (5, 1), (4, 3)].
- Second Operation: Pop (3, 0) from the heap (minimum element 3 at index 0), multiply it by 3 to get 9, and push (9, 0) back into the heap.
  - The heap is now [(3, 2), (4, 3), (5, 1), (9, 0)].
- We have completed 2 operations (k = 0), so we stop here.
Final Adjustments:
- No operations remain (k = 0), so there's no need for further distribution adjustments.
Returning Results:
- Sort the heap to retrieve the final order of original indices. Then modify nums based on these.
- Applying the sorted priority queue and considering initial indices, the final state of nums is [9, 5, 3, 4] after applying modulo 10^9 + 7.

Thus, after performing all k operations and applying the modulo transformation, the final array is [9, 5, 3, 4].

Solution Implementation

1from typing import List
2import heapq
3
4class Solution:
5    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
6        # If the multiplier is 1, the list remains unchanged
7        if multiplier == 1:
8            return nums
9      
10        # Create a priority queue from the list of numbers with their indices
11        pq = [(x, i) for i, x in enumerate(nums)]
12        heapq.heapify(pq)  # Transform the list into a heap
13      
14        # Find the maximum value in the original list
15        m = max(nums)
16      
17        # Apply the multiplier to the smallest element 'k' times or until all elements are >= maximum
18        while k and pq[0][0] < m:
19            x, i = heapq.heappop(pq)  # Extract the smallest element
20            heapq.heappush(pq, (x * multiplier, i))  # Push back the updated element multiplied by the multiplier
21            k -= 1
22      
23        # Length of the list
24        n = len(nums)
25      
26        # Use modulo operation for large numbers
27        mod = 10**9 + 7
28      
29        # Sort the priority queue based on the updated values
30        pq.sort()
31      
32        # Update nums based on remaining 'k' and sorted priority queue
33        for i, (x, j) in enumerate(pq):
34            # Calculate new value by raising the multiplier to the power determined by remaining operations and position
35            power = k // n + (1 if i < k % n else 0)
36            nums[j] = x * pow(multiplier, power, mod) % mod
37      
38        return nums
39

1import java.util.PriorityQueue;
2import java.util.Arrays;
3
4class Solution {
5    public int[] getFinalState(int[] nums, int k, int multiplier) {
6        // If multiplier is 1, return the original array as no change will occur.
7        if (multiplier == 1) {
8            return nums;
9        }
10
11        // Initialize a priority queue that sorts elements based on their values,
12        // breaking ties with indices.
13        PriorityQueue<long[]> pq = new PriorityQueue<>(
14            (a, b) -> a[0] == b[0] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));
15
16        int length = nums.length;
17        // Find the maximum value in the array.
18        int maxNum = Arrays.stream(nums).max().getAsInt();
19      
20        // Add all elements with their indices to the priority queue.
21        for (int i = 0; i < length; ++i) {
22            pq.offer(new long[] {nums[i], i});
23        }
24
25        // Multiply the smallest element by the multiplier for at most k times
26        // as long as the smallest element is less than the maximum value.
27        while (k > 0 && pq.peek()[0] < maxNum) {
28            long[] smallest = pq.poll();
29            smallest[0] *= multiplier;
30            pq.offer(smallest);
31            --k;
32        }
33
34        final int mod = (int) 1e9 + 7; // Modulus value to keep results within bounds.
35      
36        // Compute the final state considering remaining operations and modulus.
37        for (int i = 0; i < length; ++i) {
38            long[] current = pq.poll();
39            long value = current[0];
40            int index = (int) current[1];
41          
42            // Calculate the power multiplier effect based on number of full rounds
43            // and remaining operations, updating the nums in mod space.
44            nums[index] = (int) ((value % mod) * qpow(multiplier, k / length + (i < k % length ? 1 : 0), mod) % mod);
45        }
46        return nums;
47    }
48
49    // Helper method to compute power modulus: (a^n) % mod
50    private int qpow(long base, long exp, long mod) {
51        long result = 1 % mod; // To handle the case when mod is very small.
52        while (exp > 0) {
53            // If the current exponent's LSD is 1, multiply the base to the result.
54            if ((exp & 1) == 1) {
55                result = result * base % mod;
56            }
57            // Square the base and reduce the exponent by half.
58            base = base * base % mod;
59            exp >>= 1;
60        }
61        return (int) result;
62    }
63}
64

1class Solution {
2public:
3    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
4        // If the multiplier is 1, the numbers remain unchanged.
5        if (multiplier == 1) {
6            return nums;
7        }
8
9        // Define short form for long long and pair<long long, int>.
10        using ll = long long;
11        using pli = pair<ll, int>;
12
13        // Custom comparator for the priority queue, sorting by the first value. If equal, sort by second in reverse.
14        auto cmp = [](const pli& a, const pli& b) {
15            if (a.first == b.first) {
16                return a.second > b.second;
17            }
18            return a.first > b.first;
19        };
20
21        // Priority queue (min-heap by default) to store pairs of number and their original index.
22        priority_queue<pli, vector<pli>, decltype(cmp)> pq(cmp);
23
24        int n = nums.size();
25        int m = *max_element(nums.begin(), nums.end()); // Find the maximum element in nums.
26
27        // Initialize the priority queue with the numbers and their indices.
28        for (int i = 0; i < n; ++i) {
29            pq.emplace(nums[i], i);
30        }
31
32        // Apply the multiplier to the smallest elements until k iterations or until all numbers are >= max value.
33        while (k > 0 && pq.top().first < m) {
34            auto p = pq.top(); // Get the smallest element.
35            pq.pop();          // Remove it from the queue.
36            p.first *= multiplier; // Multiply it by the multiplier.
37            pq.emplace(p);     // Push it back with the updated value.
38            --k;               // Decrease the number of allowed operations.
39        }
40
41        // Exponentiation by squaring function to calculate (a^n) % mod.
42        auto qpow = [&](ll a, ll n, ll mod) {
43            ll ans = 1 % mod;
44            a = a % mod;
45            while (n > 0) {
46                // If n is odd, multiply the answer with the current base.
47                if (n & 1) {
48                    ans = ans * a % mod;
49                }
50                a = a * a % mod; // Square the base.
51                n >>= 1;         // Shift right for division by 2.
52            }
53            return ans;
54        };
55
56        const int mod = 1e9 + 7; // Define modulus to handle large numbers.
57
58        // Adjust each number to account for any remaining multiplier effects using the power function.
59        for (int i = 0; i < n; ++i) {
60            auto p = pq.top(); // Get the top element from the queue.
61            pq.pop();          // Remove it from the queue.
62            long long x = p.first;
63            int j = p.second;
64            // Calculate the number of remaining multiplications and adjust the value.
65            nums[j] = static_cast<int>((x % mod) * qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod);
66        }
67
68        return nums; // Return the modified array.
69    }
70};
71

1// Define a type for a pair of a number and its original index.
2type Pair = [number, number];
3
4// Custom comparator function for sorting pairs in the priority queue.
5const comparator = (a: Pair, b: Pair): boolean => {
6    if (a[0] === b[0]) {
7        return a[1] > b[1];
8    }
9    return a[0] > b[0];
10};
11
12// Function to perform exponentiation by squaring. Calculates (base^exp) % mod.
13const qpow = (base: number, exp: number, mod: number): number => {
14    let result = 1 % mod;
15    base = base % mod;
16    while (exp > 0) {
17        // If the exponent is odd, multiply result with the current base.
18        if (exp & 1) {
19            result = (result * base) % mod;
20        }
21        base = (base * base) % mod; // Square the base.
22        exp >>= 1; // Divide the exponent by 2.
23    }
24    return result;
25};
26
27// Main function to calculate the final state of the array after applying the multiplier.
28const getFinalState = (nums: number[], k: number, multiplier: number): number[] => {
29    // If multiplier is 1, the numbers remain unchanged.
30    if (multiplier === 1) {
31        return nums;
32    }
33
34    const n = nums.length;
35    const maxNum = Math.max(...nums); // Find the maximum element in nums.
36
37    // Priority queue (min-heap) to store pairs of number and their original index.
38    const pq = new MinHeap<Pair>(comparator);
39
40    // Initialize the priority queue with the numbers and their indices.
41    for (let i = 0; i < n; ++i) {
42        pq.insert([nums[i], i]);
43    }
44
45    // Apply the multiplier to the smallest elements until k operations are done or until all numbers are >= max value.
46    while (k > 0 && pq.peak()[0] < maxNum) {
47        const p = pq.extract(); // Get the smallest element.
48        p[0] *= multiplier; // Multiply it by the multiplier.
49        pq.insert(p); // Push it back with the updated value.
50        --k; // Decrease the number of allowed operations.
51    }
52
53    const mod = 1e9 + 7; // Define modulus to handle large numbers.
54
55    // Adjust each number to account for any remaining multiplier effects using the power function.
56    for (let i = 0; i < n; ++i) {
57        const p = pq.extract(); // Get the top element from the queue.
58        const value = p[0];
59        const index = p[1];
60        // Calculate remaining multiplications and adjust the value.
61        nums[index] = (value % mod) * qpow(multiplier, Math.floor(k / n) + (i < k % n ? 1 : 0), mod) % mod;
62    }
63
64    return nums; // Return the modified array.
65};
66
67// MinHeap class to handle priority queue operations.
68class MinHeap<T> {
69    private data: T[];
70    private compare: (a: T, b: T) => boolean;
71
72    constructor(compareFunc: (a: T, b: T) => boolean) {
73        this.data = [];
74        this.compare = compareFunc;
75    }
76
77    public insert(value: T): void {
78        this.data.push(value);
79        this.bubbleUp(this.data.length - 1);
80    }
81
82    public extract(): T {
83        this.swap(0, this.data.length - 1);
84        const value = this.data.pop();
85        this.bubbleDown(0);
86        return value!;
87    }
88
89    public peak(): T {
90        return this.data[0];
91    }
92
93    private bubbleUp(index: number): void {
94        while (index > 0) {
95            const parentIndex = Math.floor((index - 1) / 2);
96            if (this.compare(this.data[parentIndex], this.data[index])) {
97                this.swap(parentIndex, index);
98                index = parentIndex;
99            } else {
100                break;
101            }
102        }
103    }
104
105    private bubbleDown(index: number): void {
106        const length = this.data.length;
107        while (true) {
108            const leftChildIndex = 2 * index + 1;
109            const rightChildIndex = 2 * index + 2;
110            let largestIndex = index;
111
112            if (leftChildIndex < length && this.compare(this.data[largestIndex], this.data[leftChildIndex])) {
113                largestIndex = leftChildIndex;
114            }
115
116            if (rightChildIndex < length && this.compare(this.data[largestIndex], this.data[rightChildIndex])) {
117                largestIndex = rightChildIndex;
118            }
119
120            if (largestIndex !== index) {
121                this.swap(index, largestIndex);
122                index = largestIndex;
123            } else {
124                break;
125            }
126        }
127    }
128
129    private swap(i: number, j: number): void {
130        [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
131    }
132}
133

Time and Space Complexity

The code primarily operates in two stages: first, it uses a min-heap to repeatedly pop and push elements while performing a specified number of multiplier operations; second, it adjusts the remaining multipliers' impact on elements after the loop. Here's the breakdown:

The time complexity involves three key components:
- Initial heap creation using heapify(pq) costs O(n) for n elements.
- The loop processes each element up to k times, where each operation includes a heappop and heappush, both O(log n). Thus, this loop costs O(k \times \log n).
- After the loop, sorting with pq.sort() has a complexity of O(n \times \log n).
Inside the loop, the code also calculates the maximum element once, which is an O(n) operation. Given that k multiplications and heap operations may increase the value of each element significantly, consider that M, the max possible value after such operations, could lead to additional computation, accounting for O(\log M) in the analysis.

The precise computational time complexity would be approximated as: O(n) + O(k \times \log n) + O(n \times \log n \times \log M).
The space complexity is primarily driven by the storage of the heap, pq, alongside temporary variables within the operations. Therefore, the space complexity is O(n).

Encompassing all factors, the overall complexity observed aligns with O(n \times \log n \times \log M + n \times \log k) for time complexity and O(n) for space complexity.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First Search

Breadth-First Search

Binary Search

Priority Queue

I don’t know