# Final Array State After K Multiplication Operations I
**Difficulty:** EASY
[External](https://leetcode.com/problems/final-array-state-after-k-multiplication-operations-i)
Canonical: https://scaleengineer.com/dsa/problems/final-array-state-after-k-multiplication-operations-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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.

**Example 1:**

**Input:** nums = \[2,1,3,5,6\], k = 5, multiplier = 2

**Output:** \[8,4,6,5,6\]

**Explanation:**

| Operation         | Result            |
| ----------------- | ----------------- |
| After operation 1 | \[2, 2, 3, 5, 6\] |
| After operation 2 | \[4, 2, 3, 5, 6\] |
| After operation 3 | \[4, 4, 3, 5, 6\] |
| After operation 4 | \[4, 4, 6, 5, 6\] |
| After operation 5 | \[8, 4, 6, 5, 6\] |

**Example 2:**

**Input:** nums = \[1,2\], k = 3, multiplier = 4

**Output:** \[16,8\]

**Explanation:**

| Operation         | Result    |
| ----------------- | --------- |
| After operation 1 | \[4, 2\]  |
| After operation 2 | \[4, 8\]  |
| After operation 3 | \[16, 8\] |

**Constraints:**

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

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It iterates `k` times, and in each iteration, it scans the entire array to find the first occurrence of the minimum value and then updates it.
**Time:** O(k * n), where `n` is the number of elements in `nums`. For each of the `k` operations, we perform a linear scan of the array of size `n` to find the minimum element. · **Space:** O(1), as we are modifying the input array in-place and not using any extra space proportional to the input size.
**Pros:** Simple to understand and implement.; Low memory overhead as it modifies the array in-place.
**Cons:** Inefficient for large inputs, as it requires scanning the entire array in each of the `k` operations.
### Explanation
This method directly translates the problem statement into code. We loop `k` times to perform the `k` operations. In each operation, we iterate through the entire `nums` array to find the minimum value and its first index. The tie-breaking rule (selecting the one that appears first) is naturally handled by iterating from the beginning of the array and only updating the minimum index when a strictly smaller value is found. Once the target element is identified, we update its value by multiplying it with the `multiplier`. This process is repeated `k` times on the same array.

```java
class Solution {
    public int[] getFinalArray(int[] nums, int k, int multiplier) {
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            int minIndex = -1;
            int minValue = Integer.MAX_VALUE;

            // Find the first occurrence of the minimum value
            for (int j = 0; j < n; j++) {
                if (nums[j] < minValue) {
                    minValue = nums[j];
                    minIndex = j;
                }
            }

            // Update the value at the found index
            if (minIndex != -1) {
                nums[minIndex] = nums[minIndex] * multiplier;
            }
        }
        return nums;
    }
}
```
### Algorithm
- 1. Repeat the following process `k` times.
- 2. Initialize `minIndex` to -1 and `minValue` to a very large number (e.g., `Integer.MAX_VALUE`).
- 3. Iterate through the `nums` array from left to right (index `j` from 0 to `n-1`).
- 4. If the current element `nums[j]` is less than `minValue`, update `minValue` to `nums[j]` and `minIndex` to `j`.
- 5. After the inner loop completes, `minIndex` will hold the index of the first occurrence of the minimum value.
- 6. Update the array at the found index: `nums[minIndex] = nums[minIndex] * multiplier`.
- 7. After the outer loop of `k` iterations finishes, return the modified `nums` array.

## Optimized Approach using Min-Heap
A more efficient approach uses a Min-Heap (Priority Queue) to quickly find the minimum element. To handle the tie-breaking rule (first occurrence), we store pairs of `(value, index)` in the heap.
**Time:** O((n+k) log n). Building the heap by adding `n` elements takes O(n log n). Each of the `k` operations involves one extraction and one insertion, both taking O(log n), for a total of O(k log n). Reconstructing the final array takes another O(n log n). · **Space:** O(n), to store the `n` elements (as pairs of value and index) in the priority queue and for the result array.
**Pros:** More efficient than the brute-force approach for larger inputs.; Finding the minimum element is a fast O(log n) operation.
**Cons:** Requires extra space for the heap.; Slightly more complex to implement due to the custom data structure (or pair) and comparator.
### Explanation
To optimize the process of finding the minimum element in each step, we can use a Min-Heap, which is implemented as a `PriorityQueue` in Java. A standard heap on values alone isn't sufficient because we need to track the original index of each element to handle the tie-breaking rule and to reconstruct the final array.
Therefore, we store pairs of `(value, index)` in the priority queue. We define a custom comparator for the priority queue to first sort elements by their `value` in ascending order. If two elements have the same value, the comparator then sorts them by their `index` in ascending order. This ensures that if multiple elements have the same minimum value, the one with the smallest original index will be at the top of the heap.
The overall algorithm is as follows:
1.  Initialize and populate the priority queue with `(value, index)` pairs from the input `nums` array.
2.  Loop `k` times: extract the minimum element, calculate its new value, and insert the new `(newValue, originalIndex)` pair back into the queue.
3.  After all operations, the priority queue contains the final state. We then create a result array and populate it by extracting all elements from the queue and placing them at their respective original indices.

```java
import java.util.PriorityQueue;

class Solution {
    public int[] getFinalArray(int[] nums, int k, int multiplier) {
        int n = nums.length;
        // PriorityQueue stores pairs of {value, index}
        // Comparator sorts by value, then by index for ties.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0]; // Compare by value
            }
            return a[1] - b[1]; // Compare by index for tie-breaking
        });

        // Add all initial elements to the priority queue
        for (int i = 0; i < n; i++) {
            pq.add(new int[]{nums[i], i});
        }

        // Perform k operations
        for (int i = 0; i < k; i++) {
            // Get the element with the minimum value
            int[] minElement = pq.poll();
            int value = minElement[0];
            int index = minElement[1];
            
            // Calculate the new value
            int newValue = value * multiplier;
            
            // Add the updated element back to the queue
            pq.add(new int[]{newValue, index});
        }

        // Reconstruct the final array from the priority queue
        int[] result = new int[n];
        while (!pq.isEmpty()) {
            int[] e = pq.poll();
            result[e[1]] = e[0];
        }

        return result;
    }
}
```
### Algorithm
- 1. Create a Min-Heap (Priority Queue) that stores pairs of `(value, index)`.
- 2. The heap's comparator should order elements first by `value` (ascending) and then by `index` (ascending) for tie-breaking.
- 3. Populate the heap by iterating through the input `nums` array and adding `(nums[i], i)` for each element.
- 4. Perform the multiplication operation `k` times:
  - a. Extract the minimum element `(value, index)` from the heap using `poll()`.
  - b. Calculate the new value: `newValue = value * multiplier`.
  - c. Insert the new pair `(newValue, index)` back into the heap.
- 5. After `k` operations, create a new result array of the same size as `nums`.
- 6. Dequeue all elements from the heap and place each `value` in the `result` array at its corresponding `index`.
- 7. Return the `result` array.

# Solutions
### Java

```java
class Solution {
public
  int[] getFinalState(int[] nums, int k, int multiplier) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(
        (i, j)->nums[i] - nums[j] == 0 ? i - j : nums[i] - nums[j]);
    for (int i = 0; i < nums.length; i++) {
      pq.offer(i);
    }
    while (k-- > 0) {
      int i = pq.poll();
      nums[i] *= multiplier;
      pq.offer(i);
    }
    return nums;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getFinalState(vector<int> &nums, int k, int multiplier) {
    auto cmp = [&nums](int i, int j) {
      return nums[i] == nums[j] ? i > j : nums[i] > nums[j];
    };
    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    for (int i = 0; i < nums.size(); ++i) {
      pq.push(i);
    }
    while (k--) {
      int i = pq.top();
      pq.pop();
      nums[i] *= multiplier;
      pq.push(i);
    }
    return nums;
  }
};

```

### Python

```python
class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]: pq = [(x, i) for i, x in enumerate(nums)] heapify(pq) for _ in range(k): _, i = heappop(pq) nums[i] *= multiplier heappush(pq, (nums[i], i)) return nums

```