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

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

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.