- `1 <= nums.length <= 100`
- `1 <= nums[i] <= 100`
- `1 <= k <= 10`
- `1 <= multiplier <= 5`

// Brute Force
class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        for (int i = 0; i < k; i++) {
            int minIndex = 0;
            for (int j = 1; j < nums.size(); j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            nums[minIndex] *= multiplier;
        }
        return nums;
    }
};

// Min Heap

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

        for (int i = 0; i < n; ++i) {
            pq.push({nums[i], i});
        }

        while (k > 0) {
            auto [val, idx] = pq.top();
            pq.pop();
            val = (val * multiplier);
            pq.push({val, idx});
            k--;
        }
        vector<int> result(n);
        while (!pq.empty()) {
            auto [val, idx] = pq.top();
            pq.pop();
            result[idx] = val;
        }

        return result;
    }
};

| Algorithm | Time Complexity | Space Complexity |
| --------- | --------------- | ---------------- |
| Brute     | O(kn)           | O(1)             |
| Min Heap  | O(nlogn)        | O(n)             |

- In brute force we need to find the minimum element in the array
  then multiply it with the multiplier.
- First traverse the entire array to find the index of the minimum element.
- Then multiply the element at that index with the multiplier.

- In the min heap approach, we can use a min heap to store elements and their indices.
- We can pop the top element from the heap and multiply it with the multiplier.
- Then push the new element back into the heap.
- Repeat this process for k times.
- Finally, we can construct the final array from the heap.

- For the brute force approach

  - Iterate over the array for k times.
    - Find the index of the minimum element in the array.
    - Multiply the element at that index with the multiplier.
  - Return the final array.

- For the min heap approach
  - Initialize a min heap `pq` of type `pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>`.
    - Iterate over the array and push the elements along with their indices to the heap.
    - Iterate from `0` to `k`:
      - Get the top element from the heap and store it in `val` and `idx`.
      - Multiply the `val` with the multiplier.
      - Push the new element back into the heap.
    - Initialize a vector `result` of size `n`.
    - Iterate over the heap and store the elements in the `result`.
    - Return the `result`.