You are given an integer array nums, an integer k, and an integer multiplier.
You need to perform k operations on nums. In each operation:
x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.x with x * multiplier.After the k operations, apply modulo 109 + 7 to every value in nums.
Return an integer array denoting the final state of nums after performing all k operations and then applying the modulo.
Example 1:
Input: nums = [2,1,3,5,6], k = 5, multiplier = 2
Output: [8,4,6,5,6]
Explanation:
| Operation | Result |
|---|---|
| After operation 1 | [2, 2, 3, 5, 6] |
| After operation 2 | [4, 2, 3, 5, 6] |
| After operation 3 | [4, 4, 3, 5, 6] |
| After operation 4 | [4, 4, 6, 5, 6] |
| After operation 5 | [8, 4, 6, 5, 6] |
| After applying modulo | [8, 4, 6, 5, 6] |
Example 2:
Input: nums = [100000,2000], k = 2, multiplier = 1000000
Output: [999999307,999999993]
Explanation:
| Operation | Result |
|---|---|
| After operation 1 | [100000, 2000000000] |
| After operation 2 | [100000000000, 2000000000] |
| After applying modulo | [999999307, 999999993] |
Constraints:
1 <= nums.length <= 1041 <= nums[i] <= 1091 <= k <= 1091 <= multiplier <= 106Problem Overview: You are given an array and must perform k operations. In each operation, select the smallest element in the array (ties resolved by index), multiply it by a given multiplier, and place it back in the array. After performing all operations, return the final state of the array.
Approach 1: Direct Array Manipulation (O(k * n) time, O(1) space)
The straightforward simulation scans the array during every operation to locate the smallest value. Once found, multiply that element by the given multiplier and update it in place. This approach uses only the original array, so the space complexity stays O(1). However, each operation requires a full O(n) scan, making the total runtime O(k * n). This works when k and n are relatively small, but it becomes slow when the number of operations grows large.
Approach 2: Min-Heap Method (O(k log n) time, O(n) space)
A more efficient solution keeps track of the smallest element using a min-heap (priority queue). Push pairs of (value, index) into the heap so ties are naturally resolved by index. For each operation, pop the smallest element from the heap, multiply its value by the multiplier, and push the updated pair back. The heap guarantees that retrieving the minimum takes O(log n) time instead of scanning the entire array. After completing all k operations, the array reflects the correct final state.
This approach models the process exactly while improving performance significantly. Each operation involves one pop and one push, both O(log n), leading to a total runtime of O(k log n). The heap stores all elements, so the extra memory required is O(n). Priority queues are a natural fit for problems where repeated minimum extraction is required.
Problems like this commonly appear when practicing Array manipulation combined with Heap (Priority Queue) data structures and Simulation techniques.
Recommended for interviews: Start by explaining the direct simulation to show you understand the rules of the process. Then move to the min-heap optimization. Interviewers usually expect the heap-based solution because it reduces repeated scans and demonstrates familiarity with priority queues and efficient state simulation.
Utilize a Min-Heap (Priority Queue) to efficiently track the minimum value in the array. After each operation, extract the minimum value, update it, and re-insert it into the heap with the modified value.
The solution uses a min-heap to maintain the minimum element in the array. Initially, each element's value and index are pushed to the heap. The minimum element is removed and updated, then reinserted into the heap, ensuring the heap property is maintained. This process continues, reducing k until it reaches zero. Finally, the solution applies a modulo operation to each element in the array as required.
Time Complexity: O(k * log(n)) where n is the length of nums.
Space Complexity: O(n) for the heap.
In this approach, iteratively find and replace the minimum value directly in the array without any auxiliary data structures, scanning the array each time an operation is performed.
This algorithm directly manipulates the input array, avoiding priority queues or auxiliary data structures. In each of the k iterations, it locates the minimum value in the array by a linear search and updates it by multiplying it with multiplier.
Time Complexity: O(k * n), where n is the length of nums.
Space Complexity: O(1), as we do not use extra space for manipulation.
Let the length of the array nums be n, and the maximum value be m.
We first use a priority queue (min-heap) to simulate the operations until we complete k operations or all elements in the heap are greater than or equal to m.
At this point, all elements in the array are less than m times multiplier. Since 1 leq m leq 10^9 and 1 leq multiplier leq 10^6, m times multiplier leq 10^{15}, which is within the range of a 64-bit integer.
Next, each operation will turn the smallest element in the array into the largest element. Therefore, after every n consecutive operations, each element in the array will have undergone exactly one multiplication operation.
Thus, after the simulation, for the remaining k operations, the smallest k bmod n elements in the array will undergo \lfloor k / n \rfloor + 1 multiplication operations, while the other elements will undergo \lfloor k / n \rfloor multiplication operations.
Finally, we multiply each element in the array by the corresponding number of multiplication operations and take the result modulo 10^9 + 7. This can be calculated using fast exponentiation.
The time complexity is O(n times log n times log M + n times log k), and the space complexity is O(n). Here, n is the length of the array nums, and M is the maximum value in the array nums.
| Approach | Complexity |
|---|---|
| Min-Heap Method | Time Complexity: O(k * log(n)) where n is the length of nums. |
| Direct Array Manipulation | Time Complexity: O(k * n), where n is the length of nums. |
| Priority Queue (Min-Heap) + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Array Manipulation | O(k * n) | O(1) | Small arrays or small k where a simple simulation is sufficient |
| Min-Heap (Priority Queue) | O(k log n) | O(n) | General case where frequent minimum selection must be efficient |
3266. Final Array State After K Multiplication Operations II | Weekly Leetcode 412 • codingMohan • 1,672 views views
Watch 7 more video solutions →Practice Final Array State After K Multiplication Operations II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor