Description
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.
Solution
This problem could be solved with a hash map, recording the number of the locations of the marbles and the number of marbles at that location. Iterate through moveFrom and moveTo array for the corresponding moves and we should get the result by sorting the keys of the hash map.
Seeing the constraints on nums is 1 <= nums.length <= 10^5, sorting the keys shouldn’t cause TLE.
Implementation
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) {
vector<int> output;
unordered_map<int, int> m; // location, # marbles
for (int i: nums) m[i]++;
for (int i = 0; i < moveFrom.size(); i++) {
int num = m[moveFrom[i]];
m.erase(moveFrom[i]);
m[moveTo[i]] += num;
}
for (auto p: m) {
output.push_back(p.first);
}
sort(output.begin(), output.end());
return output;
}
};