Relocate Marbles — Solution in Python, Java & C++
Relocate Marbles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.
Relocate Marbles is a medium coding problem on arrays, hash table and sorting, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Simulation
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums lists the starting positions of some marbles — several marbles may share a position. You are also given two equal-length arrays moveFrom and moveTo.
Perform the moves in order: in step i, every marble currently at position moveFrom[i] moves to position moveTo[i]. The tests guarantee that moveFrom[i] holds at least one marble at the moment step i is applied.
After all the steps, return the list of occupied positions (each once) sorted ascending.
Example 1
Input: nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
Output: [5,6,8,9]
Explanation: 1 moves to 2, 7 moves to 9, then the marble now at 2 moves to 5.
Example 2
Input: nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]
Output: [2]
Explanation: All four marbles gather at position 2.
Example 3
Input: nums = [4], moveFrom = [4], moveTo = [4]
Output: [4]
Explanation: A move onto the same position leaves it occupied.
Constraints
1 <= nums.length <= 10^51 <= moveFrom.length <= 10^5moveFrom.length == moveTo.length1 <= nums[i], moveFrom[i], moveTo[i] <= 10^9moveFrom[i] is occupied when step i is applied
Hints for Relocate Marbles
Hint 1
Individual marbles do not matter — only which positions are occupied.
Hint 2
Keep a set of occupied positions. A step empties
moveFrom[i]and fillsmoveTo[i].Hint 3
Remove before you add, so a step whose source and target coincide leaves the position occupied. Sort the set at the end.
How to solve Relocate Marbles
Since all marbles at a position move together, the state is just the set of occupied positions. Each step is a delete followed by an insert.
Approach
- Insert every value of
numsinto a set. - For each step
i, deletemoveFrom[i]from the set, then insertmoveTo[i]. - Return the set's elements in ascending order.
Why it works
A step takes every marble at moveFrom[i] away, so that position becomes empty (whatever its multiplicity), and at least one marble arrives at moveTo[i], so that position becomes occupied. No other position changes. Doing the delete first gives the right state when moveFrom[i] == moveTo[i].
Complexity
- Time —
O((n + m) log(n + m)) - Space —
O(n + m)
Pitfalls
- Inserting before deleting empties a position that a self-move should leave occupied.
- Tracking marble counts is unnecessary — and a count map still has to drop the source key entirely, not decrement it once.
- The answer must be sorted and free of duplicates.
Reference solution
Python
from typing import List
def relocateMarbles(nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
occupied = set(nums)
for f, t in zip(moveFrom, moveTo):
occupied.discard(f)
occupied.add(t)
return sorted(occupied)Java
public static int[] relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
TreeSet<Integer> occupied = new TreeSet<>();
for (int v : nums) occupied.add(v);
for (int i = 0; i < moveFrom.length; i++) {
occupied.remove(moveFrom[i]);
occupied.add(moveTo[i]);
}
int[] out = new int[occupied.size()];
int k = 0;
for (int v : occupied) out[k++] = v;
return out;
}C++
vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
set<int> occupied(nums.begin(), nums.end());
for (size_t i = 0; i < moveFrom.size(); i++) {
occupied.erase(moveFrom[i]);
occupied.insert(moveTo[i]);
}
return vector<int>(occupied.begin(), occupied.end());
}JavaScript
var relocateMarbles = function(nums, moveFrom, moveTo) {
var occupied = new Set(nums);
for (var i = 0; i < moveFrom.length; i++) {
occupied.delete(moveFrom[i]);
occupied.add(moveTo[i]);
}
var out = [];
occupied.forEach(function(v) { out.push(v); });
out.sort(function(a, b) { return a - b; });
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets