[Leetcode/Heap] 3264. Final Array State After K Multiplication Operations I

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        n = len(nums)
        # Build a heap of (value, index) for index tracking
        heap = [(nums[i], i) for i in range(n)]
        heapq.heapify(heap)
        
        for _ in range(k):
            while True:
                val, idx = heapq.heappop(heap)
                # Check if the heap value matches the current nums[idx]
                if val == nums[idx]:
                    nums[idx] *= multiplier
                    # Push updated value back to heap
                    heapq.heappush(heap, (nums[idx], idx))
                    break  # Exit inner while loop for next operation
                    
        return nums

• heap = [(nums[i], i) for i in range(n)]
  • Build a list of tuples (value, index) for each element.
  • This helps us track which value came from which index in nums.
• heapq.heapify(heap)
  • Turn the list into a min-heap, where the smallest value (by value) is always on top.
  • We build a min-heap where each element is a tuple (value, index):

heap = [(2, 0), (1, 1), (3, 2), (5, 3), (6, 4)]

## After heapq.heapify(heap) → heap structure internally is:
[(1, 1), (2, 0), (3, 2), (5, 3), (6, 4)] # (The heap ensures the smallest value is always at the top.)