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

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6

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 <= 10^5
  • 1 <= moveFrom.length <= 10^5
  • moveFrom.length == moveTo.length
  • 1 <= nums[i], moveFrom[i], moveTo[i] <= 10^9
  • 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.

Solution

Method 1 – Hash Set Simulation

Intuition

We only care about which positions are occupied, not how many marbles are at each position. We can use a set to track all occupied positions, and for each move, remove the source position and add the destination position.

Approach

  1. Add all initial positions from nums to a set.
  2. For each move, if the source position is in the set, remove it and add the destination position.
  3. At the end, return the sorted list of positions in the set.

Code

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

#include <set>
class Solution {
public:
    vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
        set<int> s(nums.begin(), nums.end());
        int n = moveFrom.size();
        for (int i = 0; i < n; ++i) {
            if (s.count(moveFrom[i])) {
                s.erase(moveFrom[i]);
                s.insert(moveTo[i]);
            }
        }
        return vector<int>(s.begin(), s.end());
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import "sort"
func relocateMarbles(nums, moveFrom, moveTo []int) []int {
    s := map[int]struct{}{}
    for _, x := range nums {
        s[x] = struct{}{}
    }
    for i := range moveFrom {
        if _, ok := s[moveFrom[i]]; ok {
            delete(s, moveFrom[i])
            s[moveTo[i]] = struct{}{}
        }
    }
    ans := make([]int, 0, len(s))
    for x := range s {
        ans = append(ans, x)
    }
    sort.Ints(ans)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) s.add(x);
        for (int i = 0; i < moveFrom.length; ++i) {
            if (s.contains(moveFrom[i])) {
                s.remove(moveFrom[i]);
                s.add(moveTo[i]);
            }
        }
        List<Integer> ans = new ArrayList<>(s);
        Collections.sort(ans);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun relocateMarbles(nums: IntArray, moveFrom: IntArray, moveTo: IntArray): List<Int> {
        val s = nums.toMutableSet()
        for (i in moveFrom.indices) {
            if (s.contains(moveFrom[i])) {
                s.remove(moveFrom[i])
                s.add(moveTo[i])
            }
        }
        return s.sorted()
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def relocateMarbles(self, nums: list[int], moveFrom: list[int], moveTo: list[int]) -> list[int]:
        s = set(nums)
        for f, t in zip(moveFrom, moveTo):
            if f in s:
                s.remove(f)
                s.add(t)
        return sorted(s)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

use std::collections::HashSet;
impl Solution {
    pub fn relocate_marbles(nums: Vec<i32>, move_from: Vec<i32>, move_to: Vec<i32>) -> Vec<i32> {
        let mut s: HashSet<i32> = nums.into_iter().collect();
        for (&f, &t) in move_from.iter().zip(move_to.iter()) {
            if s.contains(&f) {
                s.remove(&f);
                s.insert(t);
            }
        }
        let mut ans: Vec<i32> = s.into_iter().collect();
        ans.sort();
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    relocateMarbles(nums: number[], moveFrom: number[], moveTo: number[]): number[] {
        const s = new Set(nums);
        for (let i = 0; i < moveFrom.length; ++i) {
            if (s.has(moveFrom[i])) {
                s.delete(moveFrom[i]);
                s.add(moveTo[i]);
            }
        }
        return Array.from(s).sort((a, b) => a - b);
    }
}

Complexity

  • ⏰ Time complexity: O(n + m + k log k), where n = len(nums), m = len(moveFrom), k = number of unique occupied positions at the end. Each move and set operation is O(1) on average, and sorting the final set is O(k log k).
  • 🧺 Space complexity: O(k), for the set of occupied positions.