Scale Engineer

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
ArrayHeap (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.

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;    }}

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.

Solutions

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;  }}

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 →

Next problem