Skip to content

2295. Replace Elements in an Array

Description

You are given a 0-indexed array nums that consists of n distinct positive integers. Apply m operations to this array, where in the ith operation you replace the number operations[i][0] with operations[i][1].

It is guaranteed that in the ith operation:

  • operations[i][0] exists in nums.
  • operations[i][1] does not exist in nums.

Return the array obtained after applying all the operations.

 

Example 1:

Input: nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
Output: [3,2,7,1]
Explanation: We perform the following operations on nums:
- Replace the number 1 with 3. nums becomes [3,2,4,6].
- Replace the number 4 with 7. nums becomes [3,2,7,6].
- Replace the number 6 with 1. nums becomes [3,2,7,1].
We return the final array [3,2,7,1].

Example 2:

Input: nums = [1,2], operations = [[1,3],[2,1],[3,2]]
Output: [2,1]
Explanation: We perform the following operations to nums:
- Replace the number 1 with 3. nums becomes [3,2].
- Replace the number 2 with 1. nums becomes [3,1].
- Replace the number 3 with 2. nums becomes [2,1].
We return the array [2,1].

 

Constraints:

  • n == nums.length
  • m == operations.length
  • 1 <= n, m <= 105
  • All the values of nums are distinct.
  • operations[i].length == 2
  • 1 <= nums[i], operations[i][0], operations[i][1] <= 106
  • operations[i][0] will exist in nums when applying the ith operation.
  • operations[i][1] will not exist in nums when applying the ith operation.

Solutions

Solution 1: Hash Table

First, we use a hash table \(d\) to record the indices of each number in the array \(\textit{nums}\). Then, we iterate through the operation array \(\textit{operations}\). For each operation \([x, y]\), we replace the number at index \(d[x]\) in \(\textit{nums}\) with \(y\), and update the index of \(y\) in \(d\) to \(d[x]\).

Finally, we return \(\textit{nums}\).

The time complexity is \(O(n + m)\), and the space complexity is \(O(n)\). Here, \(n\) and \(m\) are the lengths of the array \(\textit{nums}\) and the operation array \(\textit{operations}\), respectively.

1
2
3
4
5
6
7
class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        d = {x: i for i, x in enumerate(nums)}
        for x, y in operations:
            nums[d[x]] = y
            d[y] = d[x]
        return nums

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int[] arrayChange(int[] nums, int[][] operations) {
        int n = nums.length;
        Map<Integer, Integer> d = new HashMap<>(n);
        for (int i = 0; i < n; ++i) {
            d.put(nums[i], i);
        }
        for (var op : operations) {
            int x = op[0], y = op[1];
            nums[d.get(x)] = y;
            d.put(y, d.get(x));
        }
        return nums;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        unordered_map<int, int> d;
        for (int i = 0; i < nums.size(); ++i) {
            d[nums[i]] = i;
        }
        for (auto& op : operations) {
            int x = op[0], y = op[1];
            nums[d[x]] = y;
            d[y] = d[x];
        }
        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func arrayChange(nums []int, operations [][]int) []int {
    d := map[int]int{}
    for i, x := range nums {
        d[x] = i
    }
    for _, op := range operations {
        x, y := op[0], op[1]
        nums[d[x]] = y
        d[y] = d[x]
    }
    return nums
}

1
2
3
4
5
6
7
8
function arrayChange(nums: number[], operations: number[][]): number[] {
    const d: Map<number, number> = new Map(nums.map((x, i) => [x, i]));
    for (const [x, y] of operations) {
        nums[d.get(x)!] = y;
        d.set(y, d.get(x)!);
    }
    return nums;
}

Comments