[LeetCode] Relocate Marbles

2766. Relocate Marbles

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
unordered_map<int, int> freq;
for(auto n : nums) freq[n] += 1;
for(int i = 0; i < moveFrom.size(); i++) {
int f = moveFrom[i], t = moveTo[i];
if(f == t) continue;
if(freq.count(f)) {
freq[t] += freq[f];
freq.erase(f);
}
}
vector<int> res;
for(auto [k,v] : freq) {
res.push_back(k);
}
sort(begin(res), end(res));
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2023/07/09/PS/LeetCode/relocate-marbles/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.