Final Array State After K Multiplication Operations I

Leetcode Problem:

• Final Array State After K Multiplication Operations I

Summary

• This solution performs k operations on the input array nums
• In each operation, it finds the minimum value in nums and replaces it with the minimum value multiplied by a given multiplier.

Approach

• The solution uses a min-heap data structure to efficiently find the minimum value in the array
• It first pushes all elements of the array into the heap
• Then, it performs k operations by popping the minimum element from the heap, multiplying it by the multiplier, and pushing it back into the heap
• This process is repeated k times to achieve the final state of the array.

Complexity

• O(k log n) where n is the size of the input array, as each operation involves popping from the heap and pushing back into the heap, which takes log n time, and k operations are performed.

Explanation

• The solution uses a min-heap to efficiently find the minimum element in the array
• The min-heap is implemented using a binary heap data structure
• The cmp function used to compare elements in the heap is defined as a lambda function that compares the indices of the elements in the array if the values are equal
• This ensures that the smallest index is always at the root of the heap
• The getFinalState function first pushes all elements of the input array into the heap
• Then, it performs k operations by popping the minimum element from the heap, multiplying it by the multiplier, and pushing it back into the heap
• This process is repeated k times to achieve the final state of the array.

Solution Code:

struct _node{
    int idx;
    int val;
};

template 
struct _heap{
    int size;
    T arr[101];
    function cmp;
    _heap(){
        size = 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx >> 1], arr[idx])){
            T t = arr[idx >> 1];
            arr[idx >> 1] = arr[idx];
            arr[idx] = t;
            idx >>= 1;
        }
    }
    T pop(){
        T ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j >= size) break;
            if(j+1 < size && cmp(arr[j], arr[j+1])){
                j++;
            }
            if(cmp(arr[i], arr[j])){
                T t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
};

class Solution {
public:
    _heap h;
    vector getFinalState(vector& nums, int k, int multiplier) {
        h.cmp = [&nums](int a, int b){
            if(nums[a] != nums[b]){
                return nums[a] > nums[b];
            }
            return a > b;
        };
        for(int i = 0 ; i < nums.size(); i++){
            h.push(i);
        }
        while(k--){
            int idx = h.pop();
            nums[idx] *= multiplier;
            h.push(idx);
        }
        return nums;
    }
};