Final Array State After K Multiplication Operations

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.

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

Approach Using a Min-Heap

We use a priority queue (min-heap) that stores pairs (value, index) to efficiently find the smallest number in the array along with its index.

Steps:

1. Push all elements of nums into the min-heap. Each element is stored as a tuple (value, index) (to preserve the index).
2. Perform k operations:
   • Extract the smallest element (top of the heap) from the min-heap.
   • Update the value at the extracted index in nums by multiplying it with multiplier.
   • Push the updated value (new_value, index) back into the heap.
3. After all k operations, return the modified nums array.

Priority Queue Configuration:

• Since we want to retrieve the smallest element, we configure priority_queue to behave as a min-heap using greater<tuple<int, int>>.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
    // Min-heap to store pairs of (value, index)
    priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>> minHeap;

    // Step 1: Push all elements into the min-heap
    for (int i = 0; i < nums.size(); i++) {
        minHeap.push({nums[i], i});
    }

    // Step 2: Perform k operations
    for (int i = 0; i < k; i++) {
        // Extract the smallest element from the min-heap
        auto [value, index] = minHeap.top(); // Get the top element (smallest)
        minHeap.pop(); // Remove it from the heap

        // Update the value in the original array
        nums[index] = value * multiplier;

        // Push the updated value back into the min-heap
        minHeap.push({nums[index], index});
    }

    // Step 3: Return the modified array
    return nums;
}

int main() {
    vector<int> nums = {2, 3, 1, 5, 1}; // Example array
    int k = 2;                          // Number of operations
    int multiplier = 4;                 // Multiplier

    vector<int> result = getFinalState(nums, k, multiplier);

    // Output the result
    for (int num : result) {
        cout << num << " ";
    }

    return 0;
}

Explanation of the Code:

1. Heap Initialization:
   • All elements in nums are pushed into the min-heap along with their respective indices. This ensures that when we extract the minimum element, we also know its index in the original array.
2. Perform k Operations:
   • For each operation, the smallest value from the heap is fetched (using minHeap.top()).
   • This value is updated (multiplied by multiplier) in the nums array.
   • The updated value, along with the same index, is reinserted into the heap to maintain the order of elements.
3. Final State:
   • After k operations, the array nums is modified, and we return it.

Complexity Analysis:

1. Time Complexity:
   • Building the initial heap: O(n log n) (inserting n elements into the heap).
   • For each of the k operations:
     • Extract the minimum: O(log n)
     • Reinsert the updated value: O(log n).
   • Total: O(n log n + k log n).
   • In most cases, if k is small relative to n, the runtime is dominated by O(n log n).
2. Space Complexity:
   • The priority queue (min-heap) uses O(n) space to store all the elements.