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 in nums.
  • operations[i][1] does not exist in nums.

Return the array obtained after applying all the operations.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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 <= 10^5
  • All the values of nums are distinct.
  • operations[i].length == 2
  • 1 <= nums[i], operations[i][0], operations[i][1] <= 10^6
  • 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.

Solution

Method 1 - Hash Map for Index Tracking

Intuition

To efficiently replace elements in the array, we need to quickly find the index of the number to be replaced. Using a hash map from value to index allows O(1) updates for each operation.

Approach

  1. Build a hash map from value to index for the initial nums array.
  2. For each operation [old, new]:
    • Find the index of old in nums using the map.
    • Replace nums[index] with new.
    • Update the map: remove old, add new with the same index.
  3. Return the modified nums array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
    unordered_map<int, int> pos;
    for (int i = 0; i < nums.size(); ++i) pos[nums[i]] = i;
    for (auto& op : operations) {
        int idx = pos[op[0]];
        nums[idx] = op[1];
        pos[op[1]] = idx;
        pos.erase(op[0]);
    }
    return nums;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func arrayChange(nums []int, operations [][]int) []int {
    pos := make(map[int]int)
    for i, v := range nums {
        pos[v] = i
    }
    for _, op := range operations {
        idx := pos[op[0]]
        nums[idx] = op[1]
        pos[op[1]] = idx
        delete(pos, op[0])
    }
    return nums
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
public class Solution {
    public int[] arrayChange(int[] nums, int[][] operations) {
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = 0; i < nums.length; i++) pos.put(nums[i], i);
        for (int[] op : operations) {
            int idx = pos.get(op[0]);
            nums[idx] = op[1];
            pos.put(op[1], idx);
            pos.remove(op[0]);
        }
        return nums;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

fun arrayChange(nums: IntArray, operations: Array<IntArray>): IntArray {
    val pos = mutableMapOf<Int, Int>()
    for (i in nums.indices) pos[nums[i]] = i
    for (op in operations) {
        val idx = pos[op[0]]!!
        nums[idx] = op[1]
        pos[op[1]] = idx
        pos.remove(op[0])
    }
    return nums
}
1
2
3
4
5
6
7

def arrayChange(nums, operations):
    pos = {v: i for i, v in enumerate(nums)}
    for old, new in operations:
        idx = pos.pop(old)
        nums[idx] = new
        pos[new] = idx
    return nums
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

use std::collections::HashMap;
fn array_change(nums: &mut [i32], operations: &[[i32; 2]]) -> Vec<i32> {
    let mut pos: HashMap<i32, usize> = nums.iter().enumerate().map(|(i, &v)| (v, i)).collect();
    for op in operations {
        let idx = pos.remove(&op[0]).unwrap();
        nums[idx] = op[1];
        pos.insert(op[1], idx);
    }
    nums.to_vec()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function arrayChange(nums: number[], operations: number[][]): number[] {
    const pos = new Map<number, number>();
    nums.forEach((v, i) => pos.set(v, i));
    for (const [oldVal, newVal] of operations) {
        const idx = pos.get(oldVal)!;
        nums[idx] = newVal;
        pos.set(newVal, idx);
        pos.delete(oldVal);
    }
    return nums;
}

Complexity

  • ⏰ Time complexity: O(n + m), where n = nums.length and m = operations.length.
  • 🧺 Space complexity: O(n), for the value-to-index map.