Skip to main content
Talentd

Final Array State After K Multiplication Operations II - Solution & Explanation

HardArrayHeap (Priority Queue)Simulation13 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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:

  • Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.
  • Replace the selected minimum value 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 <= 104
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109
  • 1 <= multiplier <= 106

Approach Overview

Problem 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.

Approach 1: Min-Heap Method

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(k * log(n)) where n is the length of nums.
Space Complexity: O(n) for the heap.

Try this approach in the editor →

Approach 2: Direct Array Manipulation

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.

Code

JavaC

Java

C

Complexity

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.

Try this approach in the editor →

Approach 3: Priority Queue (Min-Heap) + Simulation

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Min-Heap Method

Time Complexity: O(k * log(n)) where n is the length of nums.
Space Complexity: O(n) for the heap.

Direct Array Manipulation

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.

Priority Queue (Min-Heap) + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Array ManipulationO(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

Video Solution

3266. Final Array State After K Multiplication Operations II | Weekly Leetcode 412 • codingMohan • 1,706 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Final Array State After K Multiplication Operations II easy or hard?
LeetCode classifies this problem as Hard with a low acceptance rate around 13%. The difficulty comes from correctly simulating repeated updates while keeping the minimum selection efficient using data structures like heaps.
Final Array State After K Multiplication Operations II Python/Java solution
In Python, the solution typically uses the heapq module to implement a min-heap storing (value, index) pairs. In Java, PriorityQueue provides the same functionality with a custom comparator. Both implementations repeatedly pop the minimum element, update it, and push it back for k operations.
How to solve Final Array State After K Multiplication Operations II in O(k log n)?
Maintain a min-heap containing pairs of (value, index). For each of the k operations, remove the smallest element from the heap, multiply it by the given multiplier, and insert the updated value back. After all operations finish, the array reflects the final state. Heap operations ensure each update runs in O(log n).
What is the best approach for Final Array State After K Multiplication Operations II?
The most efficient approach uses a min-heap (priority queue). Store each element along with its index in the heap, repeatedly extract the smallest value, multiply it by the given multiplier, and push it back. This reduces the cost of finding the minimum from O(n) per operation to O(log n), giving an overall complexity of O(k log n).
Is Final Array State After K Multiplication Operations II asked at Google/Amazon/Meta?
Heap and simulation problems similar to this frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Interviewers use them to evaluate priority queue usage, algorithmic optimization, and the ability to convert a brute-force simulation into a more efficient approach.
What data structure is used in Final Array State After K Multiplication Operations II?
A min-heap (priority queue) is the key data structure. It allows constant access to the smallest element and efficient updates after multiplication. Arrays are still used to store the final values, while the heap manages ordering during simulation.
What is the time complexity of Final Array State After K Multiplication Operations II?
The optimal solution using a min-heap runs in O(k log n) time because each operation performs one heap pop and one push. A naive simulation that scans the array every time takes O(k * n). Space complexity for the heap approach is O(n).

Ready to solve this problem?

Practice Final Array State After K Multiplication Operations II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays