# Replace Elements in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/replace-elements-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/replace-elements-in-an-array
**Data structures:** Array, Hash Table
---
## 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_.

**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.

# Approaches
## Brute Force with Linear Scan
This approach directly simulates the process described in the problem. For each operation, it iterates through the entire `nums` array to find the element that needs to be replaced and then updates it. This is the most straightforward but also the least efficient method.
**Time:** O(n * m), where `n` is the length of `nums` and `m` is the number of operations. For each of the `m` operations, we may have to scan the entire `nums` array of size `n` in the worst case. · **Space:** O(1), as we are modifying the input array in-place and not using any additional data structures that scale with the input size.
**Pros:** Simple to understand and implement.; Space-efficient, as it uses constant extra space, O(1), by modifying the array in-place.
**Cons:** Extremely inefficient for large inputs, with a quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The algorithm iterates through each operation provided in the `operations` array. For a given operation `[old_val, new_val]`, it performs a linear scan on the `nums` array from beginning to end. When it finds an element `nums[i]` that matches `old_val`, it replaces this element with `new_val`. Because the problem guarantees that elements are distinct, the inner loop can be terminated as soon as the element is found and replaced. This process is repeated for all `m` operations.

```java
class Solution {
    public int[] replaceElements(int[] nums, int[][] operations) {
        for (int[] op : operations) {
            int oldVal = op[0];
            int newVal = op[1];
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == oldVal) {
                    nums[i] = newVal;
                    break; // Elements are distinct, so we can stop searching.
                }
            }
        }
        return nums;
    }
}
```
### Algorithm
- Iterate through each operation `[old_val, new_val]` in the `operations` array.
- For each operation, perform a linear scan on the `nums` array from index `i = 0` to `n-1`.
- If `nums[i]` is equal to `old_val`, update `nums[i]` to `new_val`.
- Since all elements in `nums` are distinct, you can break the inner loop after finding and replacing the element.
- After all `m` operations are processed, return the modified `nums` array.

## Optimized Approach using a Hash Map
To improve performance, we can optimize the search for the element to be replaced. Instead of a linear scan which takes O(n) time, we can use a hash map to achieve an average search time of O(1). We first pre-process the `nums` array to store each number and its corresponding index in a hash map. This allows for quick lookups and updates.
**Time:** O(n + m), where `n` is the length of `nums` and `m` is the number of operations. It takes O(n) to build the initial map and O(m) to process all operations (O(1) for each operation). · **Space:** O(n), for the hash map which stores `n` key-value pairs corresponding to the elements in the `nums` array.
**Pros:** Highly efficient time complexity, suitable for large inputs.; The lookup, update, and removal operations in the hash map are all O(1) on average.
**Cons:** Requires extra space to store the hash map, which is proportional to the number of elements in `nums`.
### Explanation
This approach consists of two main phases: a pre-processing phase and an operations phase.

**1. Pre-processing:**
- Create a hash map, let's call it `valToIndexMap`.
- Iterate through the initial `nums` array. For each element `nums[i]`, store the mapping from the value to its index in the hash map: `valToIndexMap.put(nums[i], i)`.

**2. Processing Operations:**
- Iterate through each operation `[old_val, new_val]` in the `operations` array.
- For each operation, find the index of `old_val` by looking it up in the `valToIndexMap`. This is an O(1) operation on average: `int index = valToIndexMap.get(old_val)`.
- Update the `nums` array at the retrieved index: `nums[index] = new_val`.
- Update the `valToIndexMap` to reflect the change. Remove the old value's entry and add the new value's entry: `valToIndexMap.remove(old_val); valToIndexMap.put(new_val, index);`.

After processing all operations, the `nums` array is in its final state and can be returned.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] replaceElements(int[] nums, int[][] operations) {
        Map<Integer, Integer> valToIndexMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            valToIndexMap.put(nums[i], i);
        }

        for (int[] op : operations) {
            int oldVal = op[0];
            int newVal = op[1];

            // Get the index of the old value in O(1) average time
            int index = valToIndexMap.get(oldVal);

            // Update the array
            nums[index] = newVal;

            // Update the map to maintain consistency
            valToIndexMap.remove(oldVal);
            valToIndexMap.put(newVal, index);
        }

        return nums;
    }
}
```
### Algorithm
- Create a `HashMap` to store the mapping from each number in `nums` to its index.
- Populate the map by iterating through `nums`. This takes O(n) time.
- Iterate through each operation `[old_val, new_val]` in `operations`.
- Use the map to get the index of `old_val` in O(1) average time.
- Update the element at that index in `nums` with `new_val`.
- Update the map by removing the entry for `old_val` and adding an entry for `new_val` with the same index.
- Return the modified `nums` array.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```