Relocate Marbles solution and explanation
4 more videos on this problem
Leetcode BiWeekly contest 108 - Medium - Relocate MarblesPrakhar Agrawal · 5:18 · 368 views
Relocate Marbles | Leetcode 2766 | Set | C++Tech Courses · 7:43 · 218 views
2766. Relocate Marbles (Leetcode Medium)Programming Live with Larry · 6:17 · 179 views
6469. Relocate Marbles | Leetcode Biweekly Contest 108 | Solution Code In Comment.Optimization · 0:14 · 173 views
2766. Relocate Marbles || Leetcode biweekly contest 108 || C++ || HindiCS warriors · 7:06 · 76 views
The problem
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:
- We call a position occupied if there is at least one marble in that position.
- There may be multiple marbles in a single position.
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] <= 109- The test cases are generated such that there is at least a marble in
moveFrom[i]at the moment we want to apply theithmove.
Approach overview
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 1: Approach 1: Use a Set to Track Occupied Positions
We can utilize a set to keep track of occupied positions. Initially, we insert all numbers from the nums array to the set. Then, for each move, we perform the following operations:
- Remove
moveFrom[i]from the set. - Add
moveTo[i]to the set.
This ensures that we always have the current occupied positions. Finally, we convert the set to a sorted list, which gives our result.
def relocateMarbles(nums, moveFrom, moveTo):
occupied = set(nums)
for frm, to in zip(moveFrom, moveTo):
if frm in occupied:
occupied.discard(frm)
occupied.add(to)
return sorted(occupied)import java.util.*;
public class Solution {
public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
Set<Integer> occupied = new HashSet<>();
for (int num : nums) {
occupied.add(num);
}
for (int i = 0; i < moveFrom.length; i++) {
if (occupied.contains(moveFrom[i])) {
occupied.remove(moveFrom[i]);
occupied.add(moveTo[i]);
}
}
List<Integer> result = new ArrayList<>(occupied);
Collections.sort(result);
return result;
}
}#include <vector>
#include <set>
#include <algorithm>
std::vector<int> relocateMarbles(std::vector<int>& nums, std::vector<int>& moveFrom, std::vector<int>& moveTo) {
std::set<int> occupied(nums.begin(), nums.end());
for (size_t i = 0; i < moveFrom.size(); ++i) {
if (occupied.count(moveFrom[i])) {
occupied.erase(moveFrom[i]);
occupied.insert(moveTo[i]);
}
}
return std::vector<int>(occupied.begin(), occupied.end());
}function relocateMarbles(nums, moveFrom, moveTo) {
let occupied = new Set(nums);
for (let i = 0; i < moveFrom.length; i++) {
if (occupied.has(moveFrom[i])) {
occupied.delete(moveFrom[i]);
occupied.add(moveTo[i]);
}
}
return Array.from(occupied).sort((a, b) => a - b);
}#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b); }
void relocateMarbles(int* nums, int numsSize, int* moveFrom, int* moveTo, int movesSize, int* returnSize) {
int maxVal = 1000000000;
int* counter = calloc(maxVal + 1, sizeof(int));
for (int i = 0; i < numsSize; ++i) {
counter[nums[i]] = 1;
}
for (int i = 0; i < movesSize; ++i) {
if (counter[moveFrom[i]]) {
counter[moveFrom[i]] = 0;
counter[moveTo[i]] = 1;
}
}
int* result = malloc(numsSize * sizeof(int));
*returnSize = 0;
for (int i = 0; i <= maxVal; ++i) {
if (counter[i]) {
result[(*returnSize)++] = i;
}
}
free(counter);
qsort(result, *returnSize, sizeof(int), compare);
for (int i = 0; i < *returnSize; ++i) {
printf("%d ", result[i]);
}
free(result);
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> RelocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
HashSet<int> occupied = new HashSet<int>(nums);
for (int i = 0; i < moveFrom.Length; i++) {
if (occupied.Contains(moveFrom[i])) {
occupied.Remove(moveFrom[i]);
occupied.Add(moveTo[i]);
}
}
List<int> result = new List<int>(occupied);
result.Sort();
return result;
}
}We initialize a set with positions from nums. For each move, if the moveFrom position is in the set, it is removed and the moveTo position is added. The final set is then converted to a sorted list and returned.
Time Complexity: O(N + M log M), where N is the length of nums and M is the length of moveFrom.
Space Complexity: O(M), where M is the number of unique positions occupied.
Approach 2: Approach 2: Using Counting Strategy
Another approach uses a counting strategy utilizing an array to maintain a count of marbles at each position. We iterate over each initial position to increment counts. For each move, we adjust the counts according to the move directions and conclude by finding all indices having non-zero counts.
from collections import defaultdict
def relocateMarbles(nums, moveFrom, moveTo):
count = defaultdict(int)
for num in nums:
count[num] += 1
for frm, to in zip(moveFrom, moveTo):
if count[frm] > 0:
count[to] += count[frm]
count[frm] = 0
occupied = [pos for pos, cnt in count.items() if cnt > 0]
return sorted(occupied)import java.util.*;
public class Solution {
public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
Map<Integer, Integer> counter = new HashMap<>();
for (int num : nums) {
counter.put(num, counter.getOrDefault(num, 0) + 1);
}
for (int i = 0; i < moveFrom.length; i++) {
if (counter.containsKey(moveFrom[i]) && counter.get(moveFrom[i]) > 0) {
counter.put(moveTo[i], counter.getOrDefault(moveTo[i], 0) + counter.get(moveFrom[i]));
counter.put(moveFrom[i], 0);
}
}
List<Integer> occupied = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
if (entry.getValue() > 0) {
occupied.add(entry.getKey());
}
}
Collections.sort(occupied);
return occupied;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
std::vector<int> relocateMarbles(std::vector<int>& nums, std::vector<int>& moveFrom, std::vector<int>& moveTo) {
std::unordered_map<int, int> counter;
for (int num : nums) {
counter[num]++;
}
for (size_t i = 0; i < moveFrom.size(); ++i) {
if (counter[moveFrom[i]] > 0) {
counter[moveTo[i]] += counter[moveFrom[i]];
counter[moveFrom[i]] = 0;
}
}
std::vector<int> result;
for (auto& pair : counter) {
if (pair.second > 0) {
result.push_back(pair.first);
}
}
std::sort(result.begin(), result.end());
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> RelocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
Dictionary<int, int> counter = new Dictionary<int, int>();
foreach (int num in nums) {
if (!counter.ContainsKey(num))
counter[num] = 0;
counter[num]++;
}
for (int i = 0; i < moveFrom.Length; i++) {
if (counter.ContainsKey(moveFrom[i]) && counter[moveFrom[i]] > 0) {
if (!counter.ContainsKey(moveTo[i]))
counter[moveTo[i]] = 0;
counter[moveTo[i]] += counter[moveFrom[i]];
counter[moveFrom[i]] = 0;
}
}
List<int> result = new List<int>();
foreach (var pair in counter) {
if (pair.Value > 0) {
result.Add(pair.Key);
}
}
result.Sort();
return result;
}
}We use a defaultdict to count marbles at each position. For each move, the counts are transferred from the 'from' position to the 'to' position. Non-zero counts at the end denote the occupied positions, which are sorted and returned.
Time Complexity: O(N + M + K log K), where K is the number of unique positions occupied.
Space Complexity: O(K)
Approach 3: Hash Table
Let's use a hash table pos to record all stone positions. Initially, pos contains all elements of nums. Then we iterate through moveFrom and moveTo. Each time, we remove moveFrom[i] from pos and add moveTo[i] to pos. Finally, we sort the elements in pos and return.
The time complexity is O(n times log n) and the space complexity is O(n). Here, n is the length of array nums.
function relocateMarbles(nums: number[], moveFrom: number[], moveTo: number[]): number[] {
const pos: Set<number> = new Set(nums);
for (let i = 0; i < moveFrom.length; i++) {
pos.delete(moveFrom[i]);
pos.add(moveTo[i]);
}
return [...pos].sort((a, b) => a - b);
}func relocateMarbles(nums []int, moveFrom []int, moveTo []int) (ans []int) {
pos := map[int]bool{}
for _, x := range nums {
pos[x] = true
}
for i, f := range moveFrom {
t := moveTo[i]
pos[f] = false
pos[t] = true
}
for x, ok := range pos {
if ok {
ans = append(ans, x)
}
}
sort.Ints(ans)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use a Set to Track Occupied Positions | Time Complexity: O(N + M log M), where N is the length of nums and M is the length of moveFrom. |
| Approach 2: Using Counting Strategy | Time Complexity: O(N + M + K log K), where K is the number of unique positions occupied. |
| Hash Table | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Relocate Marbles easy or hard?
Relocate Marbles is rated Medium but behaves closer to an easy-to-medium simulation problem. The main challenge is recognizing that only the final occupied positions matter, allowing a simple hash set solution with a final sorting step.
Relocate Marbles Python/Java solution
Python and Java implementations usually use a HashSet (Java) or set (Python) to store positions. For each move operation, remove the source position and add the destination. After processing all moves, convert the set to a list and sort it before returning the result.
How to solve Relocate Marbles in O(n)?
The move simulation itself runs in O(n) using a hash set or hash map to update positions in constant time. However, the problem requires the result to be sorted, which introduces an O(n log n) sorting step. Without the sorting requirement, the algorithm would be linear.
What is the best approach for Relocate Marbles?
The most efficient approach tracks occupied positions using a hash set. Insert all initial positions, then for every move remove moveFrom[i] and insert moveTo[i]. Each update is O(1) on average, and the final step sorts the remaining positions, giving overall O(n log n) time and O(n) space.
Is Relocate Marbles asked at Google/Amazon/Meta?
Relocate Marbles represents a typical hash table and simulation problem commonly seen in technical interviews. Variations of position tracking, relocation simulation, and hash-based state updates frequently appear at companies like Amazon, Google, and Meta.
What data structure is used in Relocate Marbles?
The primary data structure is a hash set or hash map. A set efficiently tracks which positions currently contain marbles, while a hash map can store the exact count of marbles at each position. Both allow constant-time insert, delete, and lookup operations.
What is the time complexity of Relocate Marbles?
The overall complexity is O(n log n). Processing all move operations takes O(n) because hash set or hash map updates are constant time on average. The final sorting of the remaining marble positions dominates the runtime.