Problem Statement (LeetCode 3264)

You are given an integer array nums, an integer k, and an integer multiplier. You need to perform k sequential operations on nums. In each operation:

• Find the minimum value x in nums. If multiple occurrences share the minimum value, select the one that appears first (lowest index).
• Replace the selected minimum value x in-place with x * multiplier.

Return the integer array denoting the final state of nums after performing all k multiplication operations.

Algorithmic Approach: Lexicographical Min-Heap

A naive scan across nums on each of the k steps requires $\mathcal{O}(n)$ comparisons per operation, yielding $\mathcal{O}(k \cdot n)$ overall time. We can optimize repeated minimum extraction to $\mathcal{O}(\log n)$ per operation by maintaining a min-heap (priority_queue) of (value, index) pairs.

Why Lexicographical Tie-Breaking Works Automatically

When storing tuples (value, index) in a standard C++ priority_queue configured with std::greater<std::tuple<int, int>>, tuple comparison evaluates the first element (value) and automatically breaks ties using the second element (index). Consequently, when two elements share the exact same value, the element with the smaller original array index is guaranteed to sit higher in the heap.

Dry-Run Execution Trace

Consider nums = [2, 3, 1, 5, 1], k = 2, and multiplier = 4:

C++17 Implementation Using std::priority_queue

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
    // Min-heap storing pairs of (value, index) with lexicographical tie-breaking
    priority_queue<
        tuple<int, int>,
        vector<tuple<int, int>>,
        greater<tuple<int, int>>
    > minHeap;

    // Step 1: Push all elements along with their original indices
    for (int i = 0; i < static_cast<int>(nums.size()); i++) {
        minHeap.push({nums[i], i});
    }

    // Step 2: Perform k multiplication operations
    for (int step = 0; step < k; step++) {
        auto [value, index] = minHeap.top();
        minHeap.pop();

        nums[index] = value * multiplier;
        minHeap.push({nums[index], index});
    }

    return nums;
}

int main() {
    vector<int> nums = {2, 3, 1, 5, 1};
    int k = 2;
    int multiplier = 4;

    vector<int> result = getFinalState(nums, k, multiplier);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

TypeScript Implementation

In TypeScript/JavaScript environments, we can implement a compact binary min-heap comparator that orders nodes by a.val !== b.val ? a.val - b.val : a.idx - b.idx:

interface HeapNode {
  val: number;
  idx: number;
}

function compareNodes(a: HeapNode, b: HeapNode): number {
  return a.val !== b.val ? a.val - b.val : a.idx - b.idx;
}

export function getFinalState(nums: number[], k: number, multiplier: number): number[] {
  const heap: HeapNode[] = nums.map((val, idx) => ({ val, idx }));

  const siftDown = (startIdx: number): void => {
    let idx = startIdx;
    const length = heap.length;
    while (true) {
      let smallest = idx;
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;

      if (left < length && compareNodes(heap[left], heap[smallest]) < 0) {
        smallest = left;
      }
      if (right < length && compareNodes(heap[right], heap[smallest]) < 0) {
        smallest = right;
      }
      if (smallest === idx) break;
      [heap[idx], heap[smallest]] = [heap[smallest], heap[idx]];
      idx = smallest;
    }
  };

  // Build heap in O(n) time
  for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i--) {
    siftDown(i);
  }

  // Execute k multiplication updates in O(k log n) time
  for (let op = 0; op < k; op++) {
    heap[0].val *= multiplier;
    nums[heap[0].idx] = heap[0].val;
    siftDown(0);
  }

  return nums;
}

Time & Space Complexity Analysis

• Time Complexity: $\mathcal{O}((n + k) \log n)$ in C++ when pushing $n$ elements individually (or $\mathcal{O}(n + k \log n)$ when heapifying in-place as shown in the TypeScript implementation). Each of the $k$ operations performs a top-element update and logarithmic sift-down in $\mathcal{O}(\log n)$ time.
• Space Complexity: $\mathcal{O}(n)$ auxiliary space to store the $n$ (value, index) pairs inside the binary min-heap.