Relocate Marbles

Medium
1801.

Relocate Marbles

Relocate Marbles is a medium coding problem on arrays, hash table and sorting, asked in Amazon interviews.

nums lists the starting positions of some marbles — several marbles may share a position. You are also given two equal-length arrays moveFrom and moveTo.

Perform the moves in order: in step i, every marble currently at position moveFrom[i] moves to position moveTo[i]. The tests guarantee that moveFrom[i] holds at least one marble at the moment step i is applied.

After all the steps, return the list of occupied positions (each once) sorted ascending.

Example 1

Input
nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
Output
[5,6,8,9]
Explanation
1 moves to 2, 7 moves to 9, then the marble now at 2 moves to 5.

Example 2

Input
nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]
Output
[2]
Explanation
All four marbles gather at position 2.

Example 3

Input
nums = [4], moveFrom = [4], moveTo = [4]
Output
[4]
Explanation
A move onto the same position leaves it occupied.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= moveFrom.length <= 10^5
  • moveFrom.length == moveTo.length
  • 1 <= nums[i], moveFrom[i], moveTo[i] <= 10^9
  • moveFrom[i] is occupied when step i is applied
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} moveFrom
 * @param {number[]} moveTo
 * @return {number[]}
 */
var relocateMarbles = function(nums, moveFrom, moveTo) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Relocate Marbles — Solution in Python, Java & C++

Relocate Marbles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.

Relocate Marbles is a medium coding problem on arrays, hash table and sorting, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Sorting, Simulation
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums lists the starting positions of some marbles — several marbles may share a position. You are also given two equal-length arrays moveFrom and moveTo.

Perform the moves in order: in step i, every marble currently at position moveFrom[i] moves to position moveTo[i]. The tests guarantee that moveFrom[i] holds at least one marble at the moment step i is applied.

After all the steps, return the list of occupied positions (each once) sorted ascending.

Example 1

Input: nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
Output: [5,6,8,9]
Explanation: 1 moves to 2, 7 moves to 9, then the marble now at 2 moves to 5.

Example 2

Input: nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]
Output: [2]
Explanation: All four marbles gather at position 2.

Example 3

Input: nums = [4], moveFrom = [4], moveTo = [4]
Output: [4]
Explanation: A move onto the same position leaves it occupied.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= moveFrom.length <= 10^5
  • moveFrom.length == moveTo.length
  • 1 <= nums[i], moveFrom[i], moveTo[i] <= 10^9
  • moveFrom[i] is occupied when step i is applied

Hints for Relocate Marbles

  1. Hint 1

    Individual marbles do not matter — only which positions are occupied.

  2. Hint 2

    Keep a set of occupied positions. A step empties moveFrom[i] and fills moveTo[i].

  3. Hint 3

    Remove before you add, so a step whose source and target coincide leaves the position occupied. Sort the set at the end.

How to solve Relocate Marbles

Since all marbles at a position move together, the state is just the set of occupied positions. Each step is a delete followed by an insert.

Approach

  1. Insert every value of nums into a set.
  2. For each step i, delete moveFrom[i] from the set, then insert moveTo[i].
  3. Return the set's elements in ascending order.

Why it works

A step takes every marble at moveFrom[i] away, so that position becomes empty (whatever its multiplicity), and at least one marble arrives at moveTo[i], so that position becomes occupied. No other position changes. Doing the delete first gives the right state when moveFrom[i] == moveTo[i].

Complexity

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

Pitfalls

  • Inserting before deleting empties a position that a self-move should leave occupied.
  • Tracking marble counts is unnecessary — and a count map still has to drop the source key entirely, not decrement it once.
  • The answer must be sorted and free of duplicates.

Reference solution

Python

from typing import List

def relocateMarbles(nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
    occupied = set(nums)
    for f, t in zip(moveFrom, moveTo):
        occupied.discard(f)
        occupied.add(t)
    return sorted(occupied)

Java

public static int[] relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
    TreeSet<Integer> occupied = new TreeSet<>();
    for (int v : nums) occupied.add(v);
    for (int i = 0; i < moveFrom.length; i++) {
        occupied.remove(moveFrom[i]);
        occupied.add(moveTo[i]);
    }
    int[] out = new int[occupied.size()];
    int k = 0;
    for (int v : occupied) out[k++] = v;
    return out;
}

C++

vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
    set<int> occupied(nums.begin(), nums.end());
    for (size_t i = 0; i < moveFrom.size(); i++) {
        occupied.erase(moveFrom[i]);
        occupied.insert(moveTo[i]);
    }
    return vector<int>(occupied.begin(), occupied.end());
}

JavaScript

var relocateMarbles = function(nums, moveFrom, moveTo) {
    var occupied = new Set(nums);
    for (var i = 0; i < moveFrom.length; i++) {
        occupied.delete(moveFrom[i]);
        occupied.add(moveTo[i]);
    }
    var out = [];
    occupied.forEach(function(v) { out.push(v); });
    out.sort(function(a, b) { return a - b; });
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets