Final Array State After K Multiplication Operations I

EASY

Description

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

Checkout 2 different approaches to solve Final Array State After K Multiplication Operations I. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we are modifying the input array in-place and not using any extra space proportional to the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Final Array State After K Multiplication Operations I. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Final Array State After K Multiplication Operations I

Patterns:

Math

Data Structures:

ArrayHeap (Priority Queue)