Watch 7 video solutions for Relocate Marbles, a medium level problem involving Array, Hash Table, Sorting. This walkthrough by Prakhar Agrawal has 368 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Example 1:
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:
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 <= 1051 <= moveFrom.length <= 105moveFrom.length == moveTo.length1 <= nums[i], moveFrom[i], moveTo[i] <= 109moveFrom[i] at the moment we want to apply the ith move.Problem Overview: You start with marbles placed at several integer positions. A list of operations moves all marbles from one position to another. After applying every move, return the sorted list of positions that still contain at least one marble.
The tricky part is that multiple marbles can start at the same location and moves may repeatedly relocate them. Instead of simulating each marble individually, the goal is to track which positions currently contain marbles and update them efficiently after each operation.
Approach 1: Use a Set to Track Occupied Positions (O(n log n) time, O(n) space)
The simplest strategy tracks only whether a position currently contains marbles. Store all positions from nums in a hash set. For each operation, remove moveFrom[i] from the set and insert moveTo[i]. This works because the problem ultimately asks for the unique positions that contain marbles, not the number of marbles at each position.
Hash set operations like insertion and deletion run in average O(1) time, so processing all moves is linear. After applying all operations, convert the set to a list and sort it to produce the final output. Sorting dominates the runtime, giving O(n log n) time complexity and O(n) space.
This approach relies heavily on fast lookups from a hash table and works well when you only care about the presence of marbles at each location. It is the most concise implementation and commonly used in interviews.
Approach 2: Using Counting Strategy (O(n log n) time, O(n) space)
A more explicit simulation stores the number of marbles at each position. Use a hash map where the key is the position and the value is the marble count. First iterate through nums and increment counts. Then process each move: transfer the count from moveFrom[i] to moveTo[i]. This mirrors the actual marble relocation process.
If the destination already has marbles, simply add the counts together. Remove the source position after transferring its marbles to keep the structure clean. This approach models the operation precisely and is helpful if the problem later requires tracking exact quantities rather than just positions.
Like the set approach, updates take O(1) on average due to the hash table. Finally, extract the remaining keys and sort them, giving overall O(n log n) time and O(n) space. The algorithm is essentially a controlled simulation of marble movement.
Recommended for interviews: The set-based approach is usually preferred. It shows that you recognized the key insight: only the final occupied positions matter. Implementing it requires just a few hash operations and a final sort. Mentioning the counting approach demonstrates deeper reasoning about the problem model and shows you can extend the solution if marble quantities become relevant.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set to Track Occupied Positions | O(n log n) | O(n) | Best general solution when only final occupied positions matter |
| Counting Hash Map Strategy | O(n log n) | O(n) | Useful when marble counts per position must be preserved or extended |