LeetCode 2766 - Relocate Marbles

LeetCode Problem 2766

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting, Simulation

Solution

Problem Understanding

The problem gives us an array nums representing the positions of marbles on a number line. Multiple marbles may exist at the same position, so nums can contain duplicates. We are also given two arrays, moveFrom and moveTo, which describe a sequence of move operations.

For each index i, we must move every marble currently located at position moveFrom[i] to position moveTo[i]. The important detail is that the move affects all marbles at that position simultaneously. After all moves are completed, we need to return the sorted list of positions that still contain at least one marble.

The output only cares about occupied positions, not how many marbles are present at each position. This observation is extremely important because it means we do not actually need to track marble counts individually. We only need to know whether a position is occupied or not.

The constraints are large:

• nums.length can be up to 10^5
• moveFrom.length can also be up to 10^5
• Position values can be as large as 10^9

These limits tell us that any approach that repeatedly scans the entire array or simulates each marble individually could become too slow. We need an algorithm close to linear time.

There are several important edge cases to keep in mind:

• Multiple marbles may start at the same position.
• Different positions may eventually merge into the same destination.
• A destination position may already contain marbles before a move occurs.
• Positions can become empty after marbles move away.
• The problem guarantees that whenever we process moveFrom[i], that position currently contains at least one marble.

Because we only need occupied positions, a set becomes a natural data structure choice.

Approaches

Brute Force Approach

A straightforward approach would explicitly track every marble individually. We could store all marble positions in a list and, for each move operation, scan through the entire list looking for marbles located at moveFrom[i]. Whenever we find one, we update its position to moveTo[i].

This approach is correct because it faithfully simulates the exact marble movements described in the problem. After all operations, we could collect the unique occupied positions and sort them.

However, this solution is too slow. If we have n marbles and m operations, then for every operation we potentially scan all marbles. This leads to O(n * m) time complexity, which can reach 10^10 operations in the worst case.

Optimal Approach

The key insight is that the problem only asks for occupied positions, not marble counts.

Suppose position 5 contains one marble or one thousand marbles. From the perspective of the final answer, both situations are identical because position 5 is simply occupied.

This means we can represent the entire state using a hash set of occupied positions.

For each move operation:

• Remove moveFrom[i] from the set because all marbles leave that position.
• Add moveTo[i] to the set because marbles now occupy the destination.

At the end, we sort the set and return the result.

Hash sets provide average O(1) insertion and deletion, so the entire simulation becomes very efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(n)	Simulates every marble individually
Optimal	O(n + m + k log k)	O(k)	Tracks only occupied positions using a hash set

Here, k represents the number of unique occupied positions at the end.

Algorithm Walkthrough

1. Initialize a hash set called occupied using the values from nums.

We use a set because duplicate positions do not matter for the final answer. A position is either occupied or not occupied. 2. Iterate through the move operations using both moveFrom and moveTo.

For each operation:

• Remove moveFrom[i] from the set.
• Add moveTo[i] to the set.

Removing the source position reflects that all marbles have left that location. Adding the destination position reflects that marbles now occupy the new location. 3. After processing all moves, convert the set into a sorted list.

The problem requires the occupied positions to be returned in ascending order. 4. Return the sorted result.

Why it works

The algorithm maintains the invariant that the set always contains exactly the currently occupied positions.

Initially, the set correctly represents the occupied positions from nums. During each operation, all marbles move from one position to another, so the source position becomes unoccupied and the destination becomes occupied. Updating the set with one removal and one insertion perfectly models this behavior.

Since every operation preserves the correctness of the set representation, the final sorted set contains exactly the occupied positions after all moves.

Python Solution

from typing import List

class Solution:
    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
        occupied = set(nums)

        for source, destination in zip(moveFrom, moveTo):
            occupied.remove(source)
            occupied.add(destination)

        return sorted(occupied)

The implementation begins by creating a set from nums. This immediately removes duplicates and leaves us with only the occupied positions.

Next, we iterate through moveFrom and moveTo simultaneously using zip. For each operation, we remove the source position from the set and add the destination position.

The problem guarantees that the source position is occupied at the time of the move, so calling remove is always safe.

Finally, we sort the set before returning it because the output must be in ascending order.

Go Solution

package main

import "sort"

func relocateMarbles(nums []int, moveFrom []int, moveTo []int) []int {
	occupied := make(map[int]bool)

	for _, position := range nums {
		occupied[position] = true
	}

	for i := 0; i < len(moveFrom); i++ {
		delete(occupied, moveFrom[i])
		occupied[moveTo[i]] = true
	}

	result := make([]int, 0, len(occupied))

	for position := range occupied {
		result = append(result, position)
	}

	sort.Ints(result)

	return result
}

The Go solution uses a map[int]bool to simulate a hash set because Go does not provide a built in set type.

The delete function removes the source position efficiently, and assigning true inserts the destination position.

After processing all operations, we iterate through the map keys to build the result slice, then sort it using sort.Ints.

Unlike Python, Go requires explicit slice construction and sorting utilities, but the overall algorithm remains identical.

Worked Examples

Example 1

Input:

nums = [1,6,7,8]
moveFrom = [1,7,2]
moveTo = [2,9,5]

Initial occupied positions:

{1,6,7,8}

Step	Move	Occupied Positions After Move
Initial	None	{1,6,7,8}
1	1 → 2	{2,6,7,8}
2	7 → 9	{2,6,8,9}
3	2 → 5	{5,6,8,9}

Sorted result:

[5,6,8,9]

Example 2

Input:

nums = [1,1,3,3]
moveFrom = [1,3]
moveTo = [2,2]

Initial occupied positions:

{1,3}

Notice that duplicates disappear because we only track occupied positions.

Step	Move	Occupied Positions After Move
Initial	None	{1,3}
1	1 → 2	{2,3}
2	3 → 2	{2}

Sorted result:

[2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m + k log k)	Building the set takes O(n), processing moves takes O(m), sorting final positions takes O(k log k)
Space	O(k)	The hash set stores the occupied positions

The dominant operations are the set updates and the final sorting step. Hash set insertion and deletion are average O(1) operations, which makes the simulation efficient even for large inputs. The sorting cost depends only on the number of unique occupied positions.

Test Cases

from typing import List

class Solution:
    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
        occupied = set(nums)

        for source, destination in zip(moveFrom, moveTo):
            occupied.remove(source)
            occupied.add(destination)

        return sorted(occupied)

solution = Solution()

# Example 1 from the problem statement
assert solution.relocateMarbles(
    [1, 6, 7, 8],
    [1, 7, 2],
    [2, 9, 5]
) == [5, 6, 8, 9]

# Example 2 with duplicate marble positions
assert solution.relocateMarbles(
    [1, 1, 3, 3],
    [1, 3],
    [2, 2]
) == [2]

# Single marble with one move
assert solution.relocateMarbles(
    [5],
    [5],
    [10]
) == [10]

# Destination already occupied
assert solution.relocateMarbles(
    [1, 2],
    [1],
    [2]
) == [2]

# Multiple chained moves
assert solution.relocateMarbles(
    [1],
    [1, 2, 3],
    [2, 3, 4]
) == [4]

# No duplicate occupied positions after moves
assert solution.relocateMarbles(
    [4, 4, 5],
    [4],
    [5]
) == [5]

# Large position values
assert solution.relocateMarbles(
    [10**9],
    [10**9],
    [1]
) == [1]

# Multiple independent moves
assert solution.relocateMarbles(
    [1, 2, 3],
    [1, 3],
    [4, 5]
) == [2, 4, 5]

Test	Why
[1,6,7,8] example	Validates standard move simulation
[1,1,3,3] example	Validates handling duplicates
Single marble move	Tests smallest valid input
Move into occupied position	Ensures merging works correctly
Chained moves	Ensures sequential state updates are correct
Duplicate collapse	Verifies positions are tracked uniquely
Large values	Confirms handling of large coordinates
Independent moves	Tests multiple unrelated relocations

Edge Cases

One important edge case occurs when multiple marbles occupy the same position initially. A naive implementation might incorrectly treat duplicates as separate occupied positions in the final answer. Using a set automatically collapses duplicates into a single occupied position, which matches the problem requirements.

Another important case happens when marbles move into a position that is already occupied. For example, if position 1 moves into position 2 while 2 already contains marbles, the final result should still contain only one occurrence of 2. The hash set naturally handles this because sets only store unique values.

A third tricky case involves chained movements. A position created by one move may later become the source of another move. For example, position 1 may move to 2, and then 2 may move to 3. The algorithm handles this correctly because the set is updated after every operation, so each subsequent move sees the current state of occupied positions.

Another subtle case is when all occupied positions eventually merge into a single location. The algorithm still works because every move removes one occupied position and potentially adds another, eventually leaving only one value in the set.