# Relocate Marbles
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/relocate-marbles)
Canonical: https://scaleengineer.com/dsa/problems/relocate-marbles
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
You are given a **0-indexed** integer array `nums` representing the initial positions of some marbles. You are also given two **0-indexed** integer arrays `moveFrom` and `moveTo` of **equal** length.

Throughout `moveFrom.length` steps, you will change the positions of the marbles. On the `ith` step, you will move **all** marbles at position `moveFrom[i]` to position `moveTo[i]`.

After completing all the steps, return _the sorted list of **occupied** positions_.

**Notes:**

* We call a position **occupied** if there is at least one marble in that position.
* There may be multiple marbles in a single position.

**Example 1:**

**Input:** nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
**Output:** [5,6,8,9]
**Explanation:** Initially, the marbles are at positions 1,6,7,8.
At the i = 0th step, we move the marbles at position 1 to position 2. Then, positions 2,6,7,8 are occupied.
At the i = 1st step, we move the marbles at position 7 to position 9. Then, positions 2,6,8,9 are occupied.
At the i = 2nd step, we move the marbles at position 2 to position 5. Then, positions 5,6,8,9 are occupied.
At the end, the final positions containing at least one marbles are [5,6,8,9].

**Example 2:**

**Input:** nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]
**Output:** [2]
**Explanation:** Initially, the marbles are at positions [1,1,3,3].
At the i = 0th step, we move all the marbles at position 1 to position 2. Then, the marbles are at positions [2,2,3,3].
At the i = 1st step, we move all the marbles at position 3 to position 2. Then, the marbles are at positions [2,2,2,2].
Since 2 is the only occupied position, we return [2].

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= moveFrom.length <= 105`
* `moveFrom.length == moveTo.length`
* `1 <= nums[i], moveFrom[i], moveTo[i] <= 109`
* The test cases are generated such that there is at least a marble in `moveFrom[i]` at the moment we want to apply the `ith` move.

# Approaches
## Brute-Force Simulation using a List
This approach directly simulates the process described in the problem. We use a `List` (specifically, an `ArrayList`) to keep track of the occupied marble positions. For each move, we find the `moveFrom` position in our list, remove it, and add the `moveTo` position. While straightforward, this method is inefficient because removing an element from an `ArrayList` by value requires a linear scan of the list, making it slow for large numbers of positions or moves.
**Time:** O(N + M * K + K log K), where N is `nums.length`, M is `moveFrom.length`, and K is the number of unique positions. The `M * K` term dominates because for each of the M moves, we perform a list removal which takes O(K) time. This is generally too slow for the given constraints. · **Space:** O(K), where K is the number of unique positions. In the worst case, K can be equal to the length of `nums`, so it's O(N).
**Pros:** The logic is simple to understand as it directly models the problem statement.
**Cons:** The time complexity is poor due to the linear time cost of removing an element from an `ArrayList`.; For large inputs, this approach will likely result in a 'Time Limit Exceeded' error.
### Explanation
First, we need to get the initial set of unique occupied positions. A `HashSet` is convenient for this. We populate a `HashSet` with elements from `nums` and then convert it into an `ArrayList`. 

Next, we process the moves. We loop through the `moveFrom` and `moveTo` arrays. In each step, we remove the `moveFrom[i]` position from our list and add the `moveTo[i]` position. The `remove(Object)` method on an `ArrayList` has to search for the object, which takes time proportional to the list's size. 

After all moves are processed, our list contains the final positions. However, it might contain duplicates (e.g., if multiple marbles are moved to the same new position) and it's not sorted. To satisfy the output requirements, we convert the list into a `HashSet` to remove duplicates, then create a new `ArrayList` from this set, and finally, sort it using `Collections.sort()`.

```java
import java.util.*;

class Solution {
    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
        Set<Integer> initialPositions = new HashSet<>();
        for (int num : nums) {
            initialPositions.add(num);
        }
        List<Integer> occupiedPositions = new ArrayList<>(initialPositions);

        for (int i = 0; i < moveFrom.length; i++) {
            // The remove(Object) operation on an ArrayList is O(N)
            occupiedPositions.remove(Integer.valueOf(moveFrom[i]));
            occupiedPositions.add(moveTo[i]);
        }

        // Remove duplicates that may have been introduced and sort
        Set<Integer> finalPositionsSet = new HashSet<>(occupiedPositions);
        List<Integer> result = new ArrayList<>(finalPositionsSet);
        Collections.sort(result);
        return result;
    }
}
```
### Algorithm
- Create a `HashSet` from the input `nums` array to get the initial unique positions.
- Convert this `HashSet` into an `ArrayList` called `positions`.
- Iterate through the `moveFrom` and `moveTo` arrays, from `i = 0` to `moveFrom.length - 1`.
- In each iteration, find and remove the element `moveFrom[i]` from the `positions` list. This operation (`list.remove(Object)`) has a time complexity of O(K), where K is the current size of the list, as it may require scanning the list.
- Add the element `moveTo[i]` to the end of the `positions` list.
- After the loop finishes, the `positions` list may contain duplicate values because a position could be a `moveTo` destination multiple times.
- To get the unique sorted list, create a new `HashSet` from the `positions` list to eliminate duplicates, then convert it back to an `ArrayList`.
- Finally, sort this new list and return it.

## Optimized Simulation using a HashSet
A much more efficient approach uses a `HashSet` to store the occupied positions. The key advantage of a `HashSet` is that `add`, `remove`, and `contains` operations have an average time complexity of O(1). This allows us to process each move very quickly, avoiding the expensive linear scans required by a list.
**Time:** O(N + M + K log K), where N is `nums.length`, M is `moveFrom.length`, and K is the number of unique final positions. This breaks down into O(N) for initialization, O(M) for processing moves, and O(K log K) for the final sort. This is very efficient and well within the time limits. · **Space:** O(K), where K is the number of unique positions. This is used to store the positions in the `HashSet` and the final `ArrayList`. In the worst case, K is at most `nums.length`, so the complexity is O(N).
**Pros:** Highly efficient time complexity, making it suitable for large inputs.; The code is clean and directly reflects the logic of maintaining a set of items.
**Cons:** Slightly higher memory overhead compared to a list due to the nature of hash tables, though the asymptotic complexity is the same.
### Explanation
This optimized solution leverages the performance characteristics of a `HashSet`. We begin by populating a `HashSet` with the initial positions from the `nums` array. This gives us the unique starting positions in O(N) time, where N is the length of `nums`.

Next, we iterate through the `moveFrom` and `moveTo` arrays. For each `i`, we perform two simple operations on our set: `occupiedPositions.remove(moveFrom[i])` and `occupiedPositions.add(moveTo[i])`. Since the problem guarantees that `moveFrom[i]` is an occupied position at the time of the move, we don't need to check for its existence before removal. Both `remove` and `add` on a `HashSet` are average-case O(1) operations. Therefore, processing all M moves takes O(M) time.

After all moves are complete, the `HashSet` holds the final set of unique occupied positions. The final step is to convert this set to a list and sort it to match the required output format. This conversion and sorting takes O(K log K) time, where K is the number of final unique positions.

```java
import java.util.*;

class Solution {
    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
        Set<Integer> occupiedPositions = new HashSet<>();
        for (int pos : nums) {
            occupiedPositions.add(pos);
        }

        for (int i = 0; i < moveFrom.length; i++) {
            int from = moveFrom[i];
            int to = moveTo[i];
            
            // remove() and add() on HashSet are O(1) on average
            occupiedPositions.remove(from);
            occupiedPositions.add(to);
        }

        List<Integer> result = new ArrayList<>(occupiedPositions);
        Collections.sort(result);
        return result;
    }
}
```
### Algorithm
- Create a `HashSet<Integer>` to store the occupied positions.
- Iterate through the initial `nums` array and add each position to the `HashSet`. The set will automatically handle any duplicate positions.
- Iterate through the `moveFrom` and `moveTo` arrays from `i = 0` to `moveFrom.length - 1`.
- For each move, remove `moveFrom[i]` from the set and add `moveTo[i]` to the set. These operations are, on average, O(1).
- After iterating through all the moves, the `HashSet` will contain the final, unique set of occupied positions.
- Convert the `HashSet` into an `ArrayList`.
- Sort the `ArrayList` using `Collections.sort()`.
- Return the sorted list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
    Set<Integer> pos = new HashSet<>();
    for (int x : nums) {
      pos.add(x);
    }
    for (int i = 0; i < moveFrom.length; ++i) {
      pos.remove(moveFrom[i]);
      pos.add(moveTo[i]);
    }
    List<Integer> ans = new ArrayList<>(pos);
    ans.sort((a, b)->a - b);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> relocateMarbles(vector<int> &nums, vector<int> &moveFrom,
                              vector<int> &moveTo) {
    unordered_set<int> pos(nums.begin(), nums.end());
    for (int i = 0; i < moveFrom.size(); ++i) {
      pos.erase(moveFrom[i]);
      pos.insert(moveTo[i]);
    }
    vector<int> ans(pos.begin(), pos.end());
    sort(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]: pos = set(nums) for f, t in zip(moveFrom, moveTo): pos . remove(f) pos . add(t) return sorted(pos)

```