Final Array State After K Multiplication Operations I

easy heap priority queue simulation

Problem

Given an array nums, an integer k, and an integer multiplier, perform k operations. Each operation finds the minimum value x in nums (the first one on ties) and replaces it with x × multiplier. Return the final array.

Inputnums = [2,1,3,5,6], k = 5, multiplier = 2

Output[8,4,6,5,6]

1→2, 2→4, 2→4, 3→6, 4→8 over the 5 ops ⇒ [8,4,6,5,6].

nums (comma-separated, positive)

k (operations)

multiplier

import heapq
def getFinalState(nums, k, multiplier):
    # min-heap of (value, index); ties break by smaller index
    heap = [(v, i) for i, v in enumerate(nums)]
    heapq.heapify(heap)
    for _ in range(k):
        v, i = heapq.heappop(heap)        # current minimum
        heapq.heappush(heap, (v * multiplier, i))
    for v, i in heap:                      # write values back
        nums[i] = v
    return nums

function getFinalState(nums, k, multiplier) {
  // min-heap (sorted array) of [value, index]; ties break by index
  const heap = nums.map((v, i) => [v, i]);
  const cmp = (a, b) => a[0] - b[0] || a[1] - b[1];
  heap.sort(cmp);
  for (let op = 0; op < k; op++) {
    const [v, i] = heap.shift();          // current minimum
    const node = [v * multiplier, i];
    let p = heap.findIndex(e => cmp(e, node) > 0);
    if (p === -1) p = heap.length;
    heap.splice(p, 0, node);              // re-insert in order
  }
  for (const [v, i] of heap) nums[i] = v; // write values back
  return nums;
}

int[] getFinalState(int[] nums, int k, int multiplier) {
    // min-heap of {value, index}; ties break by smaller index
    PriorityQueue<int[]> heap = new PriorityQueue<>(
        (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    for (int i = 0; i < nums.length; i++) heap.offer(new int[]{nums[i], i});
    for (int op = 0; op < k; op++) {
        int[] cur = heap.poll();          // current minimum
        cur[0] *= multiplier;
        heap.offer(cur);                  // push it back
    }
    while (!heap.isEmpty()) {              // write values back
        int[] e = heap.poll();
        nums[e[1]] = e[0];
    }
    return nums;
}

vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
    // min-heap of (value, index); pair orders by value then index
    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<>> heap;
    for (int i = 0; i < nums.size(); i++) heap.push({nums[i], i});
    for (int op = 0; op < k; op++) {
        auto [v, i] = heap.top(); heap.pop();   // current minimum
        heap.push({v * multiplier, i});         // push it back
    }
    while (!heap.empty()) {                      // write values back
        auto [v, i] = heap.top(); heap.pop();
        nums[i] = v;
    }
    return nums;
}

Explanation

Every operation needs the current minimum, and on ties we must take the one with the smallest index. A min-heap of (value, index) pairs gives exactly that: comparing by value first and index second means the heap top is always the right element to multiply.

We build the heap once from all (value, index) pairs. Then we repeat k times: pop the top (the minimum), multiply its value by multiplier, and push the new pair back — keeping its original index so it lands in the same slot when we are done.

The index in each pair is the key trick. Because it travels with the value, ties resolve toward the earlier position automatically, and at the end we can scatter every value back to its home: nums[i] = v.

Each pop and push is O(log n), so k operations cost O(k log n) — far better than scanning the whole array for the minimum every time.

Example: nums=[2,1,3,5,6], k=5, multiplier=2. The minima picked in order are 1, 2, 2, 3, 4, becoming 2, 4, 4, 6, 8. The final array is [8,4,6,5,6].

Time: O((n + k) log n) Space: O(n)