Final Array State After K Multiplication Operations I

EasyArrayMathHeap (Priority Queue)Simulation

Solution

Solution1: Brute Force

function getFinalState(nums: number[], k: number, multiplier: number): number[] {
  while (0 < k) {
    let [minValue, minIndex] = [Number.MAX_SAFE_INTEGER, -1];
    nums.forEach((num, i) => {
      if (num < minValue) {
        minValue = num;
        minIndex = i;
      }
    });
    nums[minIndex] *= multiplier;
    k -= 1;
  }
  return nums;
}

Complexity

  • Time: O(K * N)
  • Space: O(1)

Solution2: Heap

import { Heap } from '@algorithm/lib';
 
export function getFinalState(nums: number[], k: number, multiplier: number): number[] {
  const heap = new Heap<[number, number]>((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));
  nums.forEach((num, i) => {
    heap.push([num, i]);
  });
 
  while (0 < k) {
    const [minValue, minIndex] = heap.pop()!;
    nums[minIndex] = minValue * multiplier;
    heap.push([minValue * multiplier, minIndex]);
    k -= 1;
  }
  return nums;
}

Complexity

  • Time: O(K * logN)
  • Space: O(N)