Problem Description

You have an array nums that represents the initial positions of marbles. You need to perform a series of moves on these marbles using two arrays: moveFrom and moveTo (both of equal length).

For each step i from 0 to moveFrom.length - 1, you move all marbles currently at position moveFrom[i] to position moveTo[i].

After completing all moves, return a sorted list of all positions that contain at least one marble.

Key points to understand:

• Multiple marbles can exist at the same position
• When you move marbles from position moveFrom[i], you move ALL marbles at that position
• A position is considered "occupied" if it has at least one marble
• The final answer should be a sorted list of unique occupied positions

Example walkthrough: If nums = [1, 6, 7, 8], moveFrom = [1, 7, 2], and moveTo = [2, 9, 5]:

• Initially, marbles are at positions: {1, 6, 7, 8}
• Step 1: Move all marbles from position 1 to position 2 → positions: {2, 6, 7, 8}
• Step 2: Move all marbles from position 7 to position 9 → positions: {2, 6, 8, 9}
• Step 3: Move all marbles from position 2 to position 5 → positions: {5, 6, 8, 9}
• Return sorted: [5, 6, 8, 9]

The solution uses a set to track occupied positions. For each move operation, it removes the source position from the set and adds the destination position, effectively simulating the movement of all marbles from one position to another. Finally, it returns the sorted list of occupied positions.

Intuition

The key insight is that we don't need to track individual marbles or how many marbles are at each position. We only care about which positions are occupied after all moves are completed.

Think about what happens during a move operation: when we move all marbles from position moveFrom[i] to position moveTo[i], position moveFrom[i] becomes empty (unoccupied) and position moveTo[i] becomes occupied. If moveTo[i] was already occupied, it remains occupied with more marbles.

This leads us to realize that we can treat positions as either "occupied" or "unoccupied" - a binary state. A set data structure perfectly captures this, where presence in the set means the position is occupied.

The movement operation becomes simple:

1. Remove the source position from our set (it's now empty)
2. Add the destination position to our set (it's now occupied)

If the destination was already in the set, adding it again doesn't change anything (set property), which correctly models the behavior of adding more marbles to an already occupied position.

Why does this work? Because when we move ALL marbles from a position, that position definitely becomes empty. And the destination definitely becomes occupied, regardless of whether it was occupied before. The actual count of marbles doesn't matter for our final answer - we just need to know which positions have at least one marble.

This transforms a potentially complex marble-tracking problem into a simple set operation problem: start with initial positions, apply a series of remove/add operations, then return the sorted result.

Learn more about Sorting patterns.

Solution Approach

The solution uses a hash table (implemented as a Python set) to efficiently track occupied positions throughout the marble movements.

Step-by-step implementation:

1. Initialize the position set: Create a set pos from the nums array. This gives us all initially occupied positions in O(n) time, where n is the length of nums.

   pos = set(nums)

2. Process each move operation: Iterate through moveFrom and moveTo arrays simultaneously using zip(). For each pair (f, t):

   • Remove position f from the set (since all marbles at this position are moved away)
   • Add position t to the set (since marbles are moved here)

   for f, t in zip(moveFrom, moveTo):
       pos.remove(f)
       pos.add(t)

3. Return sorted result: Convert the set to a sorted list and return it.

   return sorted(pos)

Why this works:

• The remove(f) operation ensures position f is no longer marked as occupied after moving all marbles away from it
• The add(t) operation ensures position t is marked as occupied after receiving marbles
• If position t was already occupied, add(t) has no effect (set property), which is correct since the position remains occupied
• The set automatically handles duplicates, giving us unique occupied positions

Time Complexity: O(n + m + k log k), where:

• n = length of nums (initial set creation)
• m = length of moveFrom/moveTo (processing moves)
• k = number of final occupied positions (sorting)

Space Complexity: O(n) for storing the position set.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• nums = [3, 3, 5] (initial marble positions)
• moveFrom = [3, 5]
• moveTo = [7, 6]

Step 1: Initialize the position set

pos = set([3, 3, 5]) = {3, 5}

Note that even though we have two marbles at position 3, the set only stores unique positions. We now have positions 3 and 5 marked as occupied.

Step 2: Process first move (moveFrom[0]=3, moveTo[0]=7)

• Remove position 3 from the set: pos.remove(3) → pos = {5}
• Add position 7 to the set: pos.add(7) → pos = {5, 7}

After this move, all marbles that were at position 3 (both of them) have moved to position 7. Position 3 is now empty.

Step 3: Process second move (moveFrom[1]=5, moveTo[1]=6)

• Remove position 5 from the set: pos.remove(5) → pos = {7}
• Add position 6 to the set: pos.add(6) → pos = {6, 7}

The marble at position 5 has moved to position 6. Position 5 is now empty.

Step 4: Return sorted result

return sorted(pos) = sorted({6, 7}) = [6, 7]

Final Answer: [6, 7]

This example demonstrates how the set-based approach elegantly handles:

• Multiple marbles at the same position (two marbles at position 3)
• Tracking only occupied positions without counting individual marbles
• Efficient position updates through simple set operations

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + m) where n is the length of array nums and m is the length of moveFrom/moveTo arrays.

• Creating the initial set from nums: O(n)
• The loop iterates m times, and each iteration:
  • remove(f): O(1) average case for set removal
  • add(t): O(1) average case for set addition
• Sorting the final set: O(k × log k) where k is the size of the final set, and k ≤ n + m
• The dominant operation is sorting, which in the worst case is O((n + m) × log(n + m))
• However, if we consider m as proportional to or less than n, the complexity simplifies to O(n × log n)

Space Complexity: O(n)

• The set pos stores at most n + m unique positions, but typically stores around n elements
• The sorted list returned also contains at most n elements
• If we consider m as proportional to or less than n, the space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. KeyError when removing non-existent positions

The most critical pitfall in this solution is assuming that moveFrom[i] always exists in the current set of positions. If a position in moveFrom doesn't currently have any marbles, calling remove() will raise a KeyError.

Problem scenario:

nums = [1, 2, 3]
moveFrom = [1, 4]  # Position 4 doesn't have any marbles!
moveTo = [5, 6]

# This will crash with KeyError when trying to remove position 4
marble_positions.remove(4)  # KeyError: 4

Solution: Use discard() instead of remove(), or check existence before removing:

# Option 1: Using discard() - doesn't raise error if element doesn't exist
for from_position, to_position in zip(moveFrom, moveTo):
    marble_positions.discard(from_position)  # Safe removal
    marble_positions.add(to_position)

# Option 2: Check before removing
for from_position, to_position in zip(moveFrom, moveTo):
    if from_position in marble_positions:
        marble_positions.remove(from_position)
    marble_positions.add(to_position)

2. Assuming moveFrom and moveTo have no overlaps within the same step

While the current solution handles this correctly, developers might overthink the scenario where moveFrom[i] == moveTo[i] (moving marbles to the same position). The solution works because:

• remove() happens first, removing the position
• add() happens second, adding it back
• Net effect: position remains occupied (correct behavior)

3. Not handling the case where destination already has marbles

Some might incorrectly think they need to track marble counts at each position. The problem only asks for positions with at least one marble, not the count. Using a set correctly abstracts this - adding to an existing position has no effect, which is exactly what we want.

Incorrect approach (unnecessary complexity):

# Unnecessarily tracking counts
marble_counts = {}
for pos in nums:
    marble_counts[pos] = marble_counts.get(pos, 0) + 1
# ... complex logic to update counts during moves

The set-based approach elegantly avoids this complexity by focusing only on position occupancy, not marble counts.