LeetCode 2295. Replace Elements in an Array Solution in Java, C++, Python & More | Explanation + Code

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 nums. Then, we iterate through the operation array operations. For each operation [x, y], we replace the number at index d[x] in nums with y, and update the index of y in d to d[x].

Finally, we return 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 nums and the operation array operations, respectively.

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)