Final Array State After K Multiplication Operations I

How it works

Instead of scanning the entire array each time to find the minimum, we can use a min-heap (priority queue) to efficiently retrieve the smallest element. The heap keeps elements sorted by their value, and when values are equal, by their index. After extracting the minimum, we multiply it, update the result array, and push the updated value back into the heap.

Steps

1. Create a copy of the input array to store results.
2. Build a min-heap containing pairs of (value, index) for each element.
3. Repeat k times:
   • Pop the minimum element from the heap.
   • Multiply the corresponding value in the result array by multiplier.
   • Push the updated (new_value, index) back into the heap.
4. Return the result array.

Complexity

• Time complexity:
  • O(n + k log n) in Python.
  • O(n log n + k log n) in other languages.

• Space complexity: O(n)

Where n is the size of the input array, and k is the number of operations.

Things to watch for

Incorrect Tie-Breaking for Minimum Element

When multiple elements share the minimum value, the problem requires selecting the one with the smallest index. Failing to handle this tie-breaking rule correctly will produce wrong results. Always scan from left to right and keep track of the first occurrence of the minimum.

Modifying Heap Values Without Re-Heapifying

When using a heap-based approach, some implementations store indices and compare using the current array values. After multiplying an element, you must properly update the heap by removing and reinserting the index, or the heap property will be violated and subsequent minimum extractions will be incorrect.

from typing import List
import heapq

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

        min_heap = [(num, i) for i, num in enumerate(nums)]
        heapq.heapify(min_heap)

        for _ in range(k):
            num, i = heapq.heappop(min_heap)
            res[i] *= multiplier
            heapq.heappush(min_heap, (res[i], i))

        return res

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        int n = nums.size();
        vector<int> res = nums;

        auto cmp = [&](int a, int b) {
            if (res[a] != res[b]) return res[a] > res[b];
            return a > b;
        };
        priority_queue<int, vector<int>, decltype(cmp)> minHeap(cmp);

        for (int i = 0; i < n; i++) {
            minHeap.push(i);
        }

        for (int _ = 0; _ < k; _++) {
            int i = minHeap.top();
            minHeap.pop();
            res[i] *= multiplier;
            minHeap.push(i);
        }

        return res;
    }
};