[4̲, 2, 3, 5, 6]After operation 3[4, 4̲, 3, 5, 6]After operation 4[4, 4, 6̲, 5, 6]After operation 5[8̲, 4, 6, 5, 6]

Example 2:

Input: nums = [1,2], k = 3, multiplier = 4
Output: [16,8]
Explanation:

Operation	Result
After operation 1	`[4̲, 2]`
After operation 2	`[4, 8̲]`
After operation 3	`[1̲6̲, 8]`

Constraints:

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

1b:T1656,

Method 1 - Naive

Here is the naive approach:

Initial Setup: Given an array nums, an integer k, and an integer multiplier, we need to find the minimum element in nums and replace it with its product with multiplier. This process is done k times.
Finding the Minimum: We need to find the minimum element and its first occurrence. This can be achieved by iterating through the array.
Replace the Element: Replace the found minimum element by multiplying it with multiplier.
Repeat: Repeat the above steps k times.
Optimization: Ensure that the process efficiently handles the array and doesn't result in redundant searches.

Code

[{"language":"Java","code":"class Solution {\n    public int[] getFinalState(int[] nums, int k, int multiplier) {\n        for (int i = 0; i < k; i++) {\n            int minIdx = 0;\n            for (int j = 1; j < nums.length; j++) {\n                if (nums[j] < nums[minIdx]) {\n                    minIdx = j;\n                }\n            }\n            nums[minIdx] *= multiplier;\n        }\n        return nums;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:\n        for _ in range(k):\n            min_idx = 0\n            for i in range(1, len(nums)):\n                if nums[i] < nums[min_idx]:\n                    min_idx = i\n            nums[min_idx] *= multiplier\n        return nums","lang":"python"}]

Complexity

⏰ Time complexity: O(k * n), where each of the k operations involves scanning the entire array of size n to find the minimum value.
🧺 Space complexity: O(1)

Method 2 - Using Minheap

Here is the approach:

Heap Creation: Use a list comprehension to create a heap of (value, index) tuples.
Heapify: Convert the list to a min-heap in place.
Perform k Operations: Use a while loop to perform the operations k times:
- Extract the minimum element by popping from the heap.
- Update the value in the original nums array.
- Push the updated value back into the heap.
Return Final State: After performing all operations, the nums array contains the final state and is returned directly.

Code

[{"language":"Java","code":"class Solution {\n    public int[] getFinalState(int[] nums, int k, int multipli

Related Tags