Final Array State After K Multiplication Operations I

Easy

#2897Time: 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.

Patterns

Math

Data structures

Array Heap (Priority Queue)

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

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

Walkthrough

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.

1class Solution {2    public int[] getFinalArray(int[] nums, int k, int multiplier) {3        int n = nums.length;4        for (int i = 0; i < k; i++) {5            int minIndex = -1;6            int minValue = Integer.MAX_VALUE;7 8            // Find the first occurrence of the minimum value9            for (int j = 0; j < n; j++) {10                if (nums[j] < minValue) {11                    minValue = nums[j];12                    minIndex = j;13                }14            }15 16            // Update the value at the found index17            if (minIndex != -1) {18                nums[minIndex] = nums[minIndex] * multiplier;19            }20        }21        return nums;22    }23}

Complexity

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.

Trade-offs

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.

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.

Algorithm

1. Create a Min-Heap (Priority Queue) that stores pairs of (value, index).
1. The heap's comparator should order elements first by value (ascending) and then by index (ascending) for tie-breaking.
1. Populate the heap by iterating through the input nums array and adding (nums[i], i) for each element.
1. 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.
1. After k operations, create a new result array of the same size as nums.
1. Dequeue all elements from the heap and place each value in the result array at its corresponding index.
1. Return the result array.

Walkthrough

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:

Initialize and populate the priority queue with (value, index) pairs from the input nums array.
Loop k times: extract the minimum element, calculate its new value, and insert the new (newValue, originalIndex) pair back into the queue.
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.

1import java.util.PriorityQueue;2 3class Solution {4    public int[] getFinalArray(int[] nums, int k, int multiplier) {5        int n = nums.length;6        // PriorityQueue stores pairs of {value, index}7        // Comparator sorts by value, then by index for ties.8        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {9            if (a[0] != b[0]) {10                return a[0] - b[0]; // Compare by value11            }12            return a[1] - b[1]; // Compare by index for tie-breaking13        });14 15        // Add all initial elements to the priority queue16        for (int i = 0; i < n; i++) {17            pq.add(new int[]{nums[i], i});18        }19 20        // Perform k operations21        for (int i = 0; i < k; i++) {22            // Get the element with the minimum value23            int[] minElement = pq.poll();24            int value = minElement[0];25            int index = minElement[1];26            27            // Calculate the new value28            int newValue = value * multiplier;29            30            // Add the updated element back to the queue31            pq.add(new int[]{newValue, index});32        }33 34        // Reconstruct the final array from the priority queue35        int[] result = new int[n];36        while (!pq.isEmpty()) {37            int[] e = pq.poll();38            result[e[1]] = e[0];39        }40 41        return result;42    }43}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] getFinalState(int[] nums, int k, int multiplier) {4    PriorityQueue<Integer> pq = new PriorityQueue<>(5        (i, j)->nums[i] - nums[j] == 0 ? i - j : nums[i] - nums[j]);6    for (int i = 0; i < nums.length; i++) {7      pq.offer(i);8    }9    while (k-- > 0) {10      int i = pq.poll();11      nums[i] *= multiplier;12      pq.offer(i);13    }14    return nums;15  }16}

1class Solution {2public:3  vector<int> getFinalState(vector<int> &nums, int k, int multiplier) {4    auto cmp = [&nums](int i, int j) {5      return nums[i] == nums[j] ? i > j : nums[i] > nums[j];6    };7    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);8    for (int i = 0; i < nums.size(); ++i) {9      pq.push(i);10    }11    while (k--) {12      int i = pq.top();13      pq.pop();14      nums[i] *= multiplier;15      pq.push(i);16    }17    return nums;18  }19};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem