Facebook Pixel

3264. Final Array State After K Multiplication Operations I

EasyArrayMathSimulationHeap (Priority Queue)
Leetcode Link

Problem Description

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.

Intuition

The problem asks us to repeatedly take the smallest element from the array nums, multiply it by a given multiplier, and then return it to the array. We need to perform this operation exactly k times. The simplest and most efficient way to extract the minimum element is to use a min-heap (priority queue).

A min-heap allows us to efficiently track and extract the smallest element. By converting the array into a heap structure, we perform k operations where we pop the smallest element, multiply it with multiplier, and push it back into the heap to ensure the heap condition is maintained. The heap also keeps track of indices to handle cases where multiple identical minimum values exist, ensuring we can accurately modify the correct element in nums. After performing the operations, the modified nums array is returned as the result.

Learn more about Math and Heap (Priority Queue) patterns.

Solution Approach

To solve this problem efficiently, we use a min-heap data structure to simulate the required operations:

  1. Initialize the Min-Heap: Begin by creating a list of tuples from nums where each tuple contains a value and its corresponding index (i.e., (x, i)). This allows us to keep track of both the values and their positions. Use the Python heapq module to transform this list into a min-heap. The heap will allow us to always extract the minimum value quickly.

  2. Perform Operations: Iterate k times to perform the required operations:

    • Extract the minimum element from the heap using heappop. This gives us the tuple containing the minimum value and its index.
    • Multiply the extracted minimum value by multiplier.
    • Update nums at the corresponding index with the new multiplied value.
    • Push the updated value (along with its index) back into the heap using heappush. This ensures that the heap property is maintained, and the minimum value is always accessible at the top of the heap.

  3. Return Result: Once all operations are complete, the modified array nums represents the final state and is returned as the output.

This approach efficiently handles the repeated extraction and updating of minimum values by leveraging the properties of the min-heap, providing a time complexity of (O(k \log n)), where (n) is the length of nums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following inputs:

  • nums = [4, 1, 3, 2]
  • k = 2
  • multiplier = 3

We need to perform k = 2 operations, where in each operation, we multiply the minimum value in the array by the multiplier.

Step 1: Initialize the Min-Heap

First, we create a list of tuples where each tuple contains a value from nums and its index:

  • Tuples list: [(4, 0), (1, 1), (3, 2), (2, 3)]

Next, we convert this list into a min-heap using the heapq module. The heap structure will help us efficiently retrieve the smallest value:

  • Initial Min-Heap: [(1, 1), (2, 3), (3, 2), (4, 0)]

Step 2: Perform Operations

Iterate k = 2 times to modify nums as follows:

  • First Operation:

    • Extract the minimum value: (1, 1) from the heap.
    • Compute the new value: 1 * 3 = 3.
    • Update nums at index 1: nums = [4, 3, 3, 2].
    • Push back the updated value into the heap: [(2, 3), (3, 1), (3, 2), (4, 0)].

  • Second Operation:

    • Extract the new minimum value: (2, 3) from the heap.
    • Compute the new value: 2 * 3 = 6.
    • Update nums at index 3: nums = [4, 3, 3, 6].
    • Push back the updated value into the heap: [(3, 1), (4, 0), (3, 2), (6, 3)].

Step 3: Return Result

After completing the operations, the modified array nums is:

  • Final nums: [4, 3, 3, 6]

This array is the final state of nums after performing the k operations using the specified approach.

Solution Implementation

1from typing import List
2from heapq import heappush, heappop, heapify
3
4class Solution:
5    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
6        # Create a priority queue with each element as a tuple (value, index)
7        priority_queue = [(value, index) for index, value in enumerate(nums)]
8      
9        # Transform the list into a heap
10        heapify(priority_queue)
11      
12        # Perform k operations
13        for _ in range(k):
14            # Extract the smallest element from the heap
15            _, index = heappop(priority_queue)
16          
17            # Multiply the extracted element by the multiplier
18            nums[index] *= multiplier
19          
20            # Push the updated element back into the heap
21            heappush(priority_queue, (nums[index], index))
22      
23        # Return the final state of nums
24        return nums
25
1import java.util.PriorityQueue;
2
3class Solution {
4    public int[] getFinalState(int[] nums, int k, int multiplier) {
5        // Create a priority queue that orders indices based on the value of nums at those indices.
6        // If two values are the same, order them by the index itself to ensure stability.
7        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((index1, index2) -> {
8            return nums[index1] - nums[index2] == 0 ? index1 - index2 : nums[index1] - nums[index2];
9        });
10
11        // Initialize the priority queue with all indices from the nums array.
12        for (int i = 0; i < nums.length; i++) {
13            priorityQueue.offer(i);
14        }
15
16        // Perform the operation k times.
17        while (k-- > 0) {
18            // Remove the index of the smallest element from the queue.
19            int index = priorityQueue.poll();
20            // Multiply the value at this index by the multiplier.
21            nums[index] *= multiplier;
22            // Add the index back into the priority queue to update its ordering.
23            priorityQueue.offer(index);
24        }
25
26        // Return the modified array.
27        return nums;
28    }
29}
30
1#include <vector>
2#include <queue>
3
4// This class provides a solution to modify a vector of integers.
5class Solution {
6public:
7    // This method modifies the vector 'nums' by increasing the value of elements in 'k' steps.
8    // In each step, it multiplies the largest element by 'multiplier'.
9    // The method returns the final state of the vector 'nums'.
10    std::vector<int> getFinalState(std::vector<int>& nums, int k, int multiplier) {
11        // Custom comparator for the priority queue, sorting mainly by value,
12        // and by index when values are equal.
13        auto cmp = [&nums](int i, int j) {
14            return nums[i] == nums[j] ? i > j : nums[i] > nums[j];
15        };
16
17        // Declare a priority queue (min-heap) that uses the custom comparator.
18        std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
19
20        // Populate the priority queue with indices of the vector 'nums'.
21        for (int i = 0; i < nums.size(); ++i) {
22            pq.push(i);
23        }
24
25        // Perform 'k' operations where the largest element is multiplied by 'multiplier'.
26        while (k--) {
27            // Get the index of the largest element.
28            int i = pq.top();
29            pq.pop();
30
31            // Multiply the element at that index by 'multiplier'.
32            nums[i] *= multiplier;
33
34            // Push the updated index back into the priority queue.
35            pq.push(i);
36        }
37
38        // Return the final modified vector.
39        return nums;
40    }
41};
42
1// A simple priority queue implementation
2interface PriorityQueue<T> {
3    // Compares two elements in the queue
4    compare: (a: T, b: T) => number;
5    // Adds an element to the queue
6    enqueue: (element: T) => void;
7    // Removes and returns the highest-priority element
8    dequeue: () => T | undefined;
9    // Returns the number of elements in the queue
10    size: () => number;
11}
12
13// Helper function to create a priority queue
14function createPriorityQueue<T>(compare: (a: T, b: T) => number): PriorityQueue<T> {
15    const items: T[] = [];
16
17    // Insert element into the priority queue
18    const enqueue = (element: T) => {
19        items.push(element);
20        items.sort(compare);
21    };
22
23    // Remove and return the highest-priority element
24    const dequeue = () => {
25        return items.shift();
26    };
27
28    // Returns the number of elements in the queue
29    const size = () => items.length;
30
31    return { compare, enqueue, dequeue, size };
32}
33
34function getFinalState(nums: number[], k: number, multiplier: number): number[] {
35    // Create priority queue with a custom comparator for indices
36    const pq = createPriorityQueue<number>((i, j) => (nums[i] === nums[j] ? i - j : nums[i] - nums[j]));
37
38    // Populate the priority queue with indices of the array
39    for (let i = 0; i < nums.length; i++) {
40        pq.enqueue(i);
41    }
42
43    // Process k elements from the queue, multiplying their values
44    while (k > 0) {
45        const i = pq.dequeue();
46        if (i !== undefined) {
47            nums[i] *= multiplier;
48            pq.enqueue(i);
49        }
50        k--;
51    }
52
53    return nums;
54}
55

Time and Space Complexity

The time complexity of the code is O((n + k) \times \log n), where n is the length of the array nums, and k is the number of iterations to perform. This is because:

  1. Creating the initial priority queue with heapify(pq) takes O(n) time.
  2. For each of the k iterations:
    • Extracting the minimum element with heappop(pq) takes O(\log n).
    • Updating the element in nums and pushing it back into the priority queue with heappush(pq) takes O(\log n).

Thus, the loop contributes O(k \times \log n) to the time complexity.

Combining these gives a total time complexity of O((n + k) \times \log n).

The space complexity is O(n), primarily due to the space required for the priority queue pq since it holds n elements, each as a tuple (x, i).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More