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
innums
. If there are multiple occurrences of the minimum value, select the one that appears first. - Replace the selected minimum value
x
withx * 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:
- Push all elements of
nums
into the min-heap. Each element is stored as a tuple(value, index)
(to preserve the index). - 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 withmultiplier
. - Push the updated value
(new_value, index)
back into the heap.
- After all
k
operations, return the modifiednums
array.
Priority Queue Configuration:
- Since we want to retrieve the smallest element, we configure
priority_queue
to behave as a min-heap usinggreater<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:
- 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.
- All elements in
- 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 thenums
array. - The updated value, along with the same index, is reinserted into the heap to maintain the order of elements.
- For each operation, the smallest value from the heap is fetched (using
- Final State:
- After
k
operations, the arraynums
is modified, and we return it.
- After
Complexity Analysis:
- 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 ton
, the runtime is dominated by O(n log n).
- Building the initial heap: O(n log n) (inserting
- Space Complexity:
- The priority queue (min-heap) uses O(n) space to store all the elements.