LeetCode Entry
3264. Final Array State After K Multiplication Operations I
Mutliply k minimums
3264. Final Array State After K Multiplication Operations I easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/834
Problem TLDR
Mutliply k minimums #easy
Intuition
The problem size is small, the brute force works.
One improvement is to use a heap.
Approach
- will bucket sort work?
Complexity
-
Time complexity: \(O(n^2)\) or nlog(n)
-
Space complexity: \(O(1)\) or O(n)
Code
fun getFinalState(nums: IntArray, k: Int, multiplier: Int) = nums.apply {
for (i in 1..k) nums[indexOf(min())] *= multiplier
}
pub fn get_final_state(mut nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
let mut h = BinaryHeap::from_iter(nums.iter().enumerate().map(|(i, &x)| (-x, -(i as i32))));
for i in 0..k {
let (x, i) = h.pop().unwrap();
nums[(-i) as usize] *= multiplier;
h.push((x * multiplier, i));
}; nums
}
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
while (k--) {
int j = 0;
for (int i = 0; i < nums.size(); ++i) if (nums[i] < nums[j]) j = i;
nums[j] *= multiplier;
} return nums;
}