3555. Final Array State After K Multiplication Operations I¶

Difficulty: Easy

LeetCode Problem View on GitHub

3555. Final Array State After K Multiplication Operations I

Easy

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:

Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.
Replace the selected minimum value 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 <= 100
1 <= nums[i] <= 100
1 <= k <= 10
1 <= multiplier <= 5

Solution¶

class Solution {
    static class Pair {
        int ind;
        int ele;
        public Pair(int ind, int ele) {
            this.ind = ind;
            this.ele = ele;
        }
        @Override
        public String toString() {
            return "(" + ind + " " + ele + ")";
        }
    }
    static class custom_sort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            int op1 =  Integer.compare(first.ele, second.ele);
            if (op1 != 0) return op1;
            return Integer.compare(first.ind, second.ind);
        }
    }
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        int n = nums.length;
        PriorityQueue<Pair> pq = new PriorityQueue<>(new custom_sort());
        for (int i = 0; i < n; i++) pq.offer(new Pair(i, nums[i]));
        while (k-->0) {
            Pair current = pq.poll();
            current.ele = current.ele * multiplier;
            pq.offer(current);
        }
        int res[] = new int[n];
        while (pq.size() > 0) {
            res[pq.peek().ind] = pq.peek().ele;
            pq.poll();
        }
        return res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here