3264. Final Array State After K Multiplication Operations I - Explanation

Problem Link

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 : [2, 2, 3, 5, 6] -> [4, 2, 3, 5, 6] -> [4, 4, 3, 5, 6] -> [4, 4, 6, 5, 6] -> [8, 4, 6, 5, 6]

Example 2:

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

Output: [16,8]

Explanation: [4, 2] -> [4, 8] -> [16, 8]

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Simulation

Intuition

The problem asks us to repeatedly find the minimum element and multiply it by a given multiplier. A straightforward approach is to simulate exactly what the problem describes: for each of the k operations, scan through the array to find the smallest element (choosing the first occurrence if there are ties), then multiply that element by the multiplier.

Algorithm

1. Repeat the following k times:
   • Find the index of the minimum element in the array. If there are duplicates, pick the smallest index.
   • Multiply the element at that index by multiplier.
2. Return the modified array.

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

Time & Space Complexity

• Time complexity: $O(n * k)$
• Space complexity: $O(1)$ extra space.

Where $n$ is the size of the input array, and $k$ is the number of operations.

---

2. Min-Heap

Intuition

Instead of scanning the entire array each time to find the minimum, we can use a min-heap (priority queue) to efficiently retrieve the smallest element. The heap keeps elements sorted by their value, and when values are equal, by their index. After extracting the minimum, we multiply it, update the result array, and push the updated value back into the heap.

Algorithm

1. Create a copy of the input array to store results.
2. Build a min-heap containing pairs of (value, index) for each element.
3. Repeat k times:
   • Pop the minimum element from the heap.
   • Multiply the corresponding value in the result array by multiplier.
   • Push the updated (new_value, index) back into the heap.
4. Return the result array.

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

        min_heap = [(num, i) for i, num in enumerate(nums)]
        heapq.heapify(min_heap)

        for _ in range(k):
            num, i = heapq.heappop(min_heap)
            res[i] *= multiplier
            heapq.heappush(min_heap, (res[i], i))

        return res

Time & Space Complexity

• Time complexity:

  • $O(n + k \log n)$ in Python.
  • $O(n \log n + k \log n)$ in other languages.

• Space complexity: $O(n)$

Where $n$ is the size of the input array, and $k$ is the number of operations.