Problem of The Day: Final Array State After K Multiplication Operations I

Problem Statement

Continuous Subarrays

Explanation

Intuition

The intuition is to efficiently manipulate the smallest element repeatedly.
Instead of scanning the entire array each time to find the smallest element, we utilize a min-heap, which provides direct access to the smallest element in O(log n) time.

Approach

1. Initialize a Min-Heap:
   Place all elements (value, index) into a min-heap. The heap keeps track of elements in ascending order, ensuring the smallest element is always at the top.

2. Perform k Operations:

   • Extract the smallest element from the heap.
   • Multiply it by the given multiplier.
   • Push the new value back into the heap.

   Repeating this k times ensures that we have successively transformed the smallest values.

3. Reconstruct the Final Array: After k operations, the heap contains the transformed elements. Extract each element and place it back into the original array using the stored index.

Complexity

• Time Complexity:

  • Building the heap initially: \(O(n)\)
  • Each of the k steps involves one heap pop and one heap push: \(O(\log n)\) per step.
    Total: \(O(n + k \log n)\)

• Space Complexity:
  We use a heap that stores all elements: \(O(n)\)

Code

import heapq
from typing import List

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        min_heap = []
        # Build the min-heap from all elements
        for i, num in enumerate(nums):
            heapq.heappush(min_heap, [num, i])

        # Perform k operations
        while k > 0:
            val, i = heapq.heappop(min_heap)
            heapq.heappush(min_heap, [val * multiplier, i])
            k -= 1

        # Reconstruct the final array from heap
        while min_heap:
            val, i = heapq.heappop(min_heap)
            nums[i] = val

        return nums

Editorial

Approach 1: K Full Array Scans for Minimum Element Multiplication

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int):
        n = len(nums)

        for _ in range(k):
            # Find the index of the smallest element in the array
            min_index = 0
            for i in range(n):
                if nums[i] < nums[min_index]:
                    min_index = i

            # Multiply the smallest element by the multiplier
            nums[min_index] *= multiplier

        return nums

Approach 2: Heap-Optimized K Minimum Value Multiplication

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int):
        pq = [(val, i) for i, val in enumerate(nums)]
        heapify(pq)

        for _ in range(k):
            _, i = heappop(pq)
            nums[i] *= multiplier
            heappush(pq, (nums[i], i))

        return nums