Relocate Marbles

Relocate Marbles

What is this problem about?

The Relocate Marbles problem gives you starting marble positions and a list of moves: each move shifts all marbles at a given position to another position. Find the final set of occupied positions. This medium coding problem uses a set to track positions, applying moves efficiently. The array, hash table, sorting, and simulation interview pattern is demonstrated.

Why is this asked in interviews?

Amazon asks this to test set-based simulation: tracking which positions are occupied as marbles move. The key insight is that when you move marbles from one position, multiple marbles can stack — the set removes the source and adds the destination.

Algorithmic pattern used

Set tracking + simulation. Maintain a set of occupied positions. For each move (from, to): if from == to, skip. Else: remove from from set (all marbles here move together), add to. Return sorted list of final set.

Example explanation

nums=[1,6,7,8], moves=[[1,2],[6,8],[8,5]].

• Start: {1,6,7,8}.
• Move 1→2: {2,6,7,8}.
• Move 6→8: {2,7,8} (8 was already there — add merges).
• Move 8→5: {2,5,7}. Sorted: [2,5,7].

Common mistakes candidates make

• Not handling from==to (skip if same position).
• Using a list instead of set (O(n) remove instead of O(1)).
• Not recognizing that multiple marbles can stack at a position.
• Sorting at each step instead of only at the end.

Interview preparation tip

Set-based simulation problems model "which positions are occupied" efficiently. When all marbles at a position move together, simply remove the source and add the destination. Stack merging is automatic with sets. Practice similar "track occupied cells" simulations using sets. Final sorting is O(k log k) where k = number of final positions — only sort once at the end.