How do you solve Relocate Marbles on LeetCode?

Relocate Marbles (LeetCode #2766) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + m log m) time complexity and O(n) space complexity. Key insight: Using a set allows for efficient tracking of unique positions.

What is the brute force solution for Relocate Marbles?

The brute force approach for Relocate Marbles is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we will iterate through each marble's initial position and simulate each move step by step. This means we will repeatedly check and update the positions of the marbles, which can be inefficient. The optimal Optimal Solution approach improves this to O(n + m log m).

What algorithm or data structure is used to solve Relocate Marbles?

Relocate Marbles uses the following concepts: Array, Hash Table, Sorting, Simulation. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Relocate Marbles?

Clearly explain your thought process before coding. Consider edge cases, such as empty inputs or all marbles moving to the same position. Practice explaining your code as you write it to simulate the interview environment.

What are common mistakes when solving Relocate Marbles?

Not using a set to track unique positions, leading to duplicates. Failing to sort the final result before returning.

#2766

Relocate Marbles

Medium

ArrayHash TableSortingSimulationHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + m log m)
Space	O(1)	O(n)

💡

Intuition

Time O(n + m log m)Space O(n)

In the optimal solution, we can use a set to track the positions of marbles efficiently. Instead of simulating each move, we directly update the set for each move, which allows us to avoid unnecessary iterations.

⚙️

Algorithm

4 steps

1Step 1: Create a set to store unique positions of marbles.
2Step 2: Add all initial positions from nums to the set.
3Step 3: For each move, remove moveFrom[i] from the set if it exists, and add moveTo[i].
4Step 4: Convert the set to a sorted list and return it.

solution.py10 lines

1# Full working Python code
2from collections import defaultdict
3
4def relocateMarbles(nums, moveFrom, moveTo):
5    positions = set(nums)
6    for i in range(len(moveFrom)):
7        if moveFrom[i] in positions:
8            positions.remove(moveFrom[i])
9        positions.add(moveTo[i])
10    return sorted(positions)

ℹ

Complexity note: The time complexity is O(n + m log m), where n is the number of initial positions and m is the number of moves. The set operations (insert and delete) are average O(1), and sorting the final positions takes O(m log m).

1Using a set allows for efficient tracking of unique positions.
2Directly updating positions avoids unnecessary iterations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.