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.

Examples

Example 1:

1
2
3

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:

1
2
3

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 [1̲6̲, 8]

Constraints:

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

Here is the naive approach:

  1. Initial Setup: Given an array nums, an integer k, and an integer multiplier, we need to find the minimum element in nums and replace it with its product with multiplier. This process is done k times.
  2. Finding the Minimum: We need to find the minimum element and its first occurrence. This can be achieved by iterating through the array.
  3. Replace the Element: Replace the found minimum element by multiplying it with multiplier.
  4. Repeat: Repeat the above steps k times.
  5. Optimization: Ensure that the process efficiently handles the array and doesn’t result in redundant searches.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        for (int i = 0; i < k; i++) {
            int minIdx = 0;
            for (int j = 1; j < nums.length; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            nums[minIdx] *= multiplier;
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        for _ in range(k):
            min_idx = 0
            for i in range(1, len(nums)):
                if nums[i] < nums[min_idx]:
                    min_idx = i
            nums[min_idx] *= multiplier
        return nums

Complexity

  • ⏰ Time complexity: O(k * n), where each of the k operations involves scanning the entire array of size n to find the minimum value.
  • 🧺 Space complexity: O(1)

Method 2 - Using Minheap

Here is the approach:

  1. Heap Creation: Use a list comprehension to create a heap of (value, index) tuples.
  2. Heapify: Convert the list to a min-heap in place.
  3. Perform k Operations: Use a while loop to perform the operations k times:
    • Extract the minimum element by popping from the heap.
    • Update the value in the original nums array.
    • Push the updated value back into the heap.
  4. Return Final State: After performing all operations, the nums array contains the final state and is returned directly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        // Creating a PriorityQueue with a custom comparator for (value, index) pairs
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        
        // Adding elements to the heap as (value, index) pairs
        for (int i = 0; i < nums.length; i++) {
            minHeap.offer(new int[] { nums[i], i });
        }
        
        // Perform k operations
        while (k > 0) {
            int[] min = minHeap.poll();
            int num = min[0];
            int idx = min[1];
            
            // Update the value in the nums array
            nums[idx] = num * multiplier;
            
            // Push the new value back into the heap
            minHeap.offer(new int[] { nums[idx], idx });
            k--;
        }
        
        return nums;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        // Creating a PriorityQueue with a custom comparator for (value, index) pairs
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        
        // Adding elements to the heap as (value, index) pairs
        minHeap.addAll(IntStream.range(0, nums.length)
                                .mapToObj(i -> new int[]{nums[i], i})
                                .toList());
        
        // Perform k operations
        while (k > 0) {
            int[] min = minHeap.poll();
            int num = min[0];
            int idx = min[1];
            
            // Update the value in the nums array
            nums[idx] = num * multiplier;
            
            // Push the new value back into the heap
            minHeap.offer(new int[] { nums[idx], idx });
            k--;
        }
        
        return nums;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:

        # Creating a heap of (number, index) pairs
        heap = [(num, i) for i, num in enumerate(nums)]
        heapq.heapify(heap)

        # Perform k operations
        while k > 0:
            num, idx = heapq.heappop(heap)
            # Update the value in the array
            nums[idx] = num * multiplier
            # Push the new value back into the heap
            heapq.heappush(heap, (nums[idx], idx))
            k -= 1

        return nums

Complexity

  • ⏰ Time complexity: O(n + k log n)
  • 🧺 Space complexity: O(n)