💬 Discord
Sign In
NeetCode #526LC-3264EasyHeap / Priority Queue
← Back to All Problems

#526 · #3264 · Final Array State After K Multiplication Operations I(K 次乘运算后的最终数组 I)

📌 Problem Statement & Constraints

You are given an integer array nums, an integer k and a multiplier multiplier. Repeat k times: find the minimum value in nums (ties broken by the smallest index) and replace it with value * multiplier. Return the final array. Constraints: 1 <= nums.length <= 100, 1 <= nums[i], multiplier <= 100, 1 <= k <= 10.

💡 Core Algorithmic Approaches

  1. A min-heap keyed by (value, index) gives the minimum with the correct tie-break in O(log n).
  2. After multiplying, push the updated pair back.
  3. The heap must be rebuilt each time only if the values change -- pushing the new pair is enough since the heap order is maintained.
  4. Note that the array must also be updated, since the heap stores copies of the values.

💻 Benchmark Python3 Implementation

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        import heapq
        h = [(v, i) for i, v in enumerate(nums)]
        heapq.heapify(h)                   # ties break on the index
        for _ in range(k):
            v, i = heapq.heappop(h)
            v *= multiplier
            nums[i] = v                    # keep the array in sync
            heapq.heappush(h, (v, i))
        return nums

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + k log n): one heapify plus k heap operations.
💾 Space Complexity
O(n) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Storing only the values: the index is needed both for the tie-break and to write back into nums.
  • Forgetting to update nums: the heap holds copies, so the array would be stale.
  • Re-heapifying each iteration: unnecessary; pushing the updated pair restores the invariant.
  • Using min(nums) and nums.index(...): O(n) per iteration and the tie-break is implicit.