Final Array State After K Multiplication Operations I

Difficulty: Easy | Acceptance: 86.90% | Paid: No Topics: Array, Math, Heap (Priority Queue), Simulation

You are given an integer array nums, an integer multiplier, and an integer k.

You can perform the following operation k times:

• Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one with the smallest index.
• Replace the selected element with x * multiplier.

Return the final state of nums after performing all k operations.

• Examples
• Constraints
• Simulation
• Min-Heap

Examples

Input: nums = [2,1,3,5,6], k = 5, multiplier = 2
Output: [8,4,6,5,6]
Explanation:
Operation 1: Select 1 (index 1) -> [2, 2, 3, 5, 6]
Operation 2: Select 2 (index 0) -> [4, 2, 3, 5, 6]
Operation 3: Select 2 (index 1) -> [4, 4, 3, 5, 6]
Operation 4: Select 3 (index 2) -> [4, 4, 6, 5, 6]
Operation 5: Select 4 (index 0) -> [8, 4, 6, 5, 6]

Input: nums = [1,2], k = 3, multiplier = 4
Output: [16,8]
Explanation:
Operation 1: Select 1 (index 0) -> [4, 2]
Operation 2: Select 2 (index 1) -> [4, 8]
Operation 3: Select 4 (index 0) -> [16, 8]

Constraints

- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
- 1 <= k <= 10
- 1 <= multiplier <= 5

Simulation

Intuition Since the constraints for this specific problem (I) are very small (length and k are at most 50), we can simply simulate the process step-by-step. We iterate k times, and in each iteration, we scan the array to find the minimum element and its index, then update it.

Steps

• Loop k times.
• Inside the loop, iterate through nums to find the smallest value. If values are equal, keep the one with the smaller index.
• Multiply the found value by multiplier.
• Return the modified nums.

from typing import List

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        n = len(nums)
        for _ in range(k):
            min_val = float('inf')
            min_idx = -1
            for i in range(n):
                if nums[i] < min_val:
                    min_val = nums[i]
                    min_idx = i
            nums[min_idx] *= multiplier
        return nums

Complexity

• Time: O(K * N)
• Space: O(1)
• Notes: Efficient enough for the given constraints of problem I.

Min-Heap

Intuition To efficiently retrieve the minimum element in each step, we can use a Min-Heap (Priority Queue). This approach is more scalable for larger inputs (like in problem II). We store pairs of (value, index) in the heap. The heap automatically sorts by value, and for ties, by index.

Steps

• Initialize a min-heap and push all (value, index) pairs from nums into it.
• Loop k times.
• Pop the top element (val, idx) from the heap.
• Push (val * multiplier, idx) back into the heap.
• After k operations, the heap contains the final values. Pop all elements and place them back into their respective indices in nums to return the result.

import heapq
from typing import List

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        heap = [(val, i) for i, val in enumerate(nums)]
        heapq.heapify(heap)
        
        for _ in range(k):
            val, idx = heapq.heappop(heap)
            heapq.heappush(heap, (val * multiplier, idx))
            
        res = [0] * len(nums)
        while heap:
            val, idx = heapq.heappop(heap)
            res[idx] = val
        return res

Complexity

• Time: O(K log N)
• Space: O(N)
• Notes: More efficient for larger arrays or higher values of K.