Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2295.html
2295. Replace Elements in an Array
- Difficulty: Medium.
- Related Topics: Array, Hash Table, Simulation.
- Similar Questions: Find All Numbers Disappeared in an Array.
Problem
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 innums
. -
operations[i][1]
does not exist innums
.
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 innums
when applying theith
operation. -
operations[i][1]
will not exist innums
when applying theith
operation.
Solution (Java, C++, Python)
-
class Solution { public int[] arrayChange(int[] nums, int[][] operations) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int[] operation : operations) { int index = map.get(operation[0]); nums[index] = operation[1]; map.put(operation[1], index); } return nums; } } ############ class Solution { public int[] arrayChange(int[] nums, int[][] operations) { Map<Integer, Integer> d = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { d.put(nums[i], i); } for (var op : operations) { int a = op[0], b = op[1]; nums[d.get(a)] = b; d.put(b, d.get(a)); } return nums; } }
-
class Solution: def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]: d = {v: i for i, v in enumerate(nums)} for a, b in operations: nums[d[a]] = b d[b] = d[a] return nums ############ # 2295. Replace Elements in an Array # https://leetcode.com/problems/replace-elements-in-an-array/ class Solution: def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]: mp = {x:i for i, x in enumerate(nums)} for a, b in operations: currIndex = mp[a] nums[currIndex] = b mp[b] = currIndex return nums
-
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 a = op[0], b = op[1]; nums[d[a]] = b; d[b] = d[a]; } return nums; } };
-
func arrayChange(nums []int, operations [][]int) []int { d := map[int]int{} for i, v := range nums { d[v] = i } for _, op := range operations { a, b := op[0], op[1] nums[d[a]] = b d[b] = d[a] } return nums }
-
function arrayChange(nums: number[], operations: number[][]): number[] { const d = new Map(nums.map((v, i) => [v, i])); for (const [a, b] of operations) { nums[d.get(a)] = b; d.set(b, d.get(a)); } return nums; }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).