2295. Replace Elements in an Array

MediumArrayHash TableSimulation
Leetcode Link

Problem Description

In this problem, we are given an array nums which contains n distinct positive integers, meaning all the elements in the array are unique and start from index 0. Additionally, we are provided with a set of m operations, each representing a change we need to apply to the array. Each operation is a pair of integers where the first integer is a number that currently exists in the array and the second integer is the number we want to replace it with. The conditions are such that the first integer definitely exists in the array while the second is guaranteed not to be in the array before the operation is carried out. Our task is to perform all these operations on the array and return the final state of the array after all the replacements have been made.

Key Points:

  • Each element in the array is unique.
  • Each operation consists of replacing an existing element with a new one that is not already in the array.

The challenge is to apply these operations efficiently, keeping in mind that the naive approach of searching for each element to replace would lead to a less optimal solution.

Intuition

The intuition behind the solution is to optimize the search and replace process. If we try to look for the element to replace linearly every time, it would be inefficient, especially for a large array. Therefore, we use a hash map, in Python it's a dictionary, to keep track of the indices of the current elements in the array.

Here’s how we arrive at the solution step by step:

  1. Create a hash map (dictionary) to map each value in the array to its index for constant time access. This allows us to quickly find where the replacement should occur without searching the entire array.

  2. Iterate over the list of operations. For each operation:

    • Find the index of the current value we need to replace (since it exists in the nums array as per the problem's guarantee).
    • Replace the value with the new one in the array.
    • Update the hash map by changing the mapping of the old value to the new value, essentially changing the key while keeping the value (which is the index) the same.

This way, we ensure that all the replacements can be done in linear time relative to the number of operations, leading to an efficient solution.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the solution follows a straightforward approach leveraging a dictionary data structure for fast lookups and updates to the nums array based on the operations provided. Here's how the code brings the intuition to life:

  1. Initialize a dictionary (hash map) named d. Use a dictionary comprehension to map each value v of the array nums to its corresponding index i. This is done in the form of {v: i for i, v in enumerate(nums)}, which will allow constant-time access to the indices of elements we need to update.

  2. Iterate over all the given operations using a for loop. In each iteration, you are given a pair (a tuple in Python) containing two integers: [a, b] where a is the value you need to replace in nums, and b is the value you're going to replace it with.

  3. Inside the loop, access the index of value a directly from the dictionary d – this gives us the exact position in the nums array where replacement is to take place, thus avoiding a full array scan. The operation nums[d[a]] accesses the element we want to replace and sets it to b.

  4. Now, update the dictionary for the new value b to have the same index as a had before. The operation d[b] = d[a] ensures that going forward, you can now find the position of b just as easily as you could find a.

  5. After the loop has processed all operations, we return the modified nums array, which now reflects all the replacements that have been made.

By using a hash map, the solution ensures that lookup and update operations are done in O(1) time, making the overall time complexity of the solution O(m), where m is the number of operations, as each operation involves a constant amount of work.

This approach is efficient and avoids the need for repeated array traversal, which would be necessary if we tried to find elements by value rather than by keeping track of their indices.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Example Walkthrough

Let's consider an example to illustrate the solution approach described above. Suppose we have the following input:

The nums array is [5, 3, 9, 7], and the list of operations is [(5, 10), (3, 15), (9, 20)]. Let's walk through each step of the approach.

  1. We initialize a dictionary named d that will map each number in nums to its index: {5: 0, 3: 1, 9: 2, 7: 3}.

  2. We begin iterating over the list of operations:

    • The first operation is (5, 10). We look up the index of 5 in d, which is 0. We replace the element at index 0 in the nums array with 10. The nums array now looks like [10, 3, 9, 7]. We then update d to reflect the change: {10: 0, 3: 1, 9: 2, 7: 3}.

    • The second operation is (3, 15). We look up the index of 3 in d, which is 1. We replace the element at index 1 in the nums array with 15. The nums array now looks like [10, 15, 9, 7]. We then update d to reflect the change: {10: 0, 15: 1, 9: 2, 7: 3}.

    • The third operation is (9, 20). We look up the index of 9 in d, which is 2. We replace the element at index 2 in the nums array with 20. The nums array now looks like [10, 15, 20, 7]. We then update d to reflect the change: {10: 0, 15: 1, 20: 2, 7: 3}.

  3. After completing all the operations, we end with the final state of the nums array, which is [10, 15, 20, 7].

Following this approach, we have efficiently performed all replacements without having to search through the nums array multiple times, showcasing the benefits of maintaining a hash map to track indices of array elements.

Solution Implementation

1class Solution:
2    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
3        # Create a dictionary "value_to_index" to track the indices
4        # of the elements in "nums" array 
5        value_to_index = {value: index for index, value in enumerate(nums)}
6      
7        # Iterate through each operation in "operations" list
8        for old_value, new_value in operations:
9            # Retrieve the index of the element we're going to change
10            idx = value_to_index[old_value]
11            # Update the element in "nums" at the index to the new_value
12            nums[idx] = new_value
13            # Update the "value_to_index" dictionary to reflect the change
14            # Now "new_value" points to the updated index
15            value_to_index[new_value] = idx
16          
17        # After processing all operations, return the updated "nums" array
18        return nums
19
1class Solution {
2  
3    // This method takes an array of integers and an array of operations
4    // and applies the operations to the array.
5    public int[] arrayChange(int[] nums, int[][] operations) {
6        // Create a HashMap to quickly find the index of each number in 'nums'.
7        Map<Integer, Integer> indexMap = new HashMap<>();
8      
9        // Fill the map with the numbers' values as keys and their indices as values.
10        for (int i = 0; i < nums.length; ++i) {
11            indexMap.put(nums[i], i);
12        }
13      
14        // Iterate through each operation in the operations array.
15        for (int[] operation : operations) {
16            // Extract 'from' and 'to' values from the current operation.
17            int fromValue = operation[0], toValue = operation[1];
18          
19            // Get the index of the 'fromValue' number in the 'nums' array.
20            int indexToUpdate = indexMap.get(fromValue);
21          
22            // Update the number at that index to the 'toValue'.
23            nums[indexToUpdate] = toValue;
24          
25            // Update the map with the new value ('toValue') pointing to the same index.
26            indexMap.put(toValue, indexToUpdate);
27        }
28      
29        // Return the modified 'nums' array with all operations applied.
30        return nums;
31    }
32}
33
1class Solution {
2public:
3    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
4        // Create an unordered_map to keep track of each number's index in the array
5        unordered_map<int, int> indexMap;
6        for (int i = 0; i < nums.size(); ++i) {
7            indexMap[nums[i]] = i;
8        }
9
10        // Loop over operations
11        for (auto& operation : operations) {
12            // Extract the original and new values from the operation
13            int originalValue = operation[0];
14            int newValue = operation[1];
15          
16            // Update the nums array at the index where the original value was found
17            nums[indexMap[originalValue]] = newValue;
18          
19            // Update the indexMap to reflect the index of the new value
20            indexMap[newValue] = indexMap[originalValue];
21        }
22
23        // Return the modified nums array after all operations have been performed
24        return nums;
25    }
26};
27
1function arrayChange(inputArray: number[], operations: number[][]): number[] {
2    // Create a map to store the value and its corresponding index in the input array
3    const indexMap = new Map<number, number>();
4
5    // Populate the map with each number and its index
6    inputArray.forEach((value, index) => {
7        indexMap.set(value, index);
8    });
9
10    // Iterate through the operations
11    for (const [oldValue, newValue] of operations) {
12        // Get the index of the element to be changed (oldValue)
13        const indexToChange = indexMap.get(oldValue);
14
15        // If the index exists, proceed with the update
16        if (indexToChange !== undefined) {
17            // Update the inputArray at the specific index to the newValue
18            inputArray[indexToChange] = newValue;
19
20            // Update the indexMap with the newValue pointing to the same index
21            indexMap.set(newValue, indexToChange);
22        }
23    }
24
25    // Return the modified input array
26    return inputArray;
27}
28
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed by looking at the two major steps in the function: the creation of the dictionary d that maps current values to their indices, and the iteration over the operations list to apply the value changes.

  1. Constructing the dictionary d takes O(n) time, where n is the length of the nums array. This is because it involves iterating over each element once.
  2. Iterating over the operations list takes O(m) time, where m is the number of operations because each operation involves a constant amount of work: updating a value in the list and updating a single entry in the dictionary d.

The total time complexity is the sum of these two parts: O(n + m).

Space Complexity

For space complexity, we consider the extra space used by the algorithm, not including the input and output.

  1. The extra space comes from the dictionary d that maps values to indices, which contains at most n key-value pairs, where n is the length of nums. Thus, the space complexity for the dictionary is O(n).
  2. No additional space that grows with the input size is used during the iteration over operations.

Hence, the total space complexity is O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫