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:
x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.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:
| Operation | Result |
|---|---|
| After operation 1 | [2, 2, 3, 5, 6] |
| After operation 2 | [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 | [16, 8] |
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= k <= 101 <= multiplier <= 5This approach involves simply iterating through the array to find the minimum element and multiplying it by the multiplier. This process is repeated for k times. It's straightforward due to the relatively small constraints (nums.length <= 100).
The function finalArrayState takes an array, its size, the number of operations (k), and a multiplier. It iteratively finds the minimum value in the array and multiplies it by the multiplier. This process is repeated k times, updating the array in-place.
C++
Java
Python
C#
JavaScript
Time Complexity: O(k * n), where n is the number of elements in the array, because for each of k iterations, we search through the array to find the minimum.
Space Complexity: O(1), as we do not use extra space apart from basic variables.
In this approach, a min-heap (priority queue) is used to efficiently retrieve the minimum element. The heap is updated on every multiplication operation, ensuring that the minimum value is always at the root.
The function uses a min-heap, built with tuples containing the element and its index. This allows the heap to manage duplicate values correctly and to quickly access and update the minimum value. It ensures the constraint of selecting the first occurrence of a minimum value by utilizing the index in conjunction with the heap operations.
Java
Time Complexity: O(n + k log n), where n is the size of the array for the heapify operation, and k log n for the subsequent heap operations on each element.
Space Complexity: O(n) because a heap stores all elements and additional structure is used for managing index tracking.
| Approach | Complexity |
|---|---|
| Simple Iteration Approach | Time Complexity: O(k * n), where n is the number of elements in the array, because for each of k iterations, we search through the array to find the minimum. |
| Using Min-Heap (Priority Queue) | Time Complexity: O(n + k log n), where n is the size of the array for the heapify operation, and k log n for the subsequent heap operations on each element. |
Final Array State After K Multiplication Operations I - Leetcode 3264 - Python • NeetCodeIO • 3,204 views views
Watch 9 more video solutions →Practice Final Array State After K Multiplication Operations I with our built-in code editor and test cases.
Practice on FleetCode