Relocate Marbles

Med

#2483Time: O(N + M * K + K log K), where N is `nums.length`, M is `moveFrom.length`, and K is the number of unique positions. The `M * K` term dominates because for each of the M moves, we perform a list removal which takes O(K) time. This is generally too slow for the given constraints.Space: O(K), where K is the number of unique positions. In the worst case, K can be equal to the length of `nums`, so it's O(N).

Algorithms

Sorting

Data structures

Array Hash Table

Prompt

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 i^th 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 <= 10⁵
1 <= moveFrom.length <= 10⁵
moveFrom.length == moveTo.length
1 <= nums[i], moveFrom[i], moveTo[i] <= 10⁹
The test cases are generated such that there is at least a marble in moveFrom[i] at the moment we want to apply the i^th move.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We use a List (specifically, an ArrayList) to keep track of the occupied marble positions. For each move, we find the moveFrom position in our list, remove it, and add the moveTo position. While straightforward, this method is inefficient because removing an element from an ArrayList by value requires a linear scan of the list, making it slow for large numbers of positions or moves.

Algorithm

Create a HashSet from the input nums array to get the initial unique positions.
Convert this HashSet into an ArrayList called positions.
Iterate through the moveFrom and moveTo arrays, from i = 0 to moveFrom.length - 1.
In each iteration, find and remove the element moveFrom[i] from the positions list. This operation (list.remove(Object)) has a time complexity of O(K), where K is the current size of the list, as it may require scanning the list.
Add the element moveTo[i] to the end of the positions list.
After the loop finishes, the positions list may contain duplicate values because a position could be a moveTo destination multiple times.
To get the unique sorted list, create a new HashSet from the positions list to eliminate duplicates, then convert it back to an ArrayList.
Finally, sort this new list and return it.

Walkthrough

First, we need to get the initial set of unique occupied positions. A HashSet is convenient for this. We populate a HashSet with elements from nums and then convert it into an ArrayList.

Next, we process the moves. We loop through the moveFrom and moveTo arrays. In each step, we remove the moveFrom[i] position from our list and add the moveTo[i] position. The remove(Object) method on an ArrayList has to search for the object, which takes time proportional to the list's size.

After all moves are processed, our list contains the final positions. However, it might contain duplicates (e.g., if multiple marbles are moved to the same new position) and it's not sorted. To satisfy the output requirements, we convert the list into a HashSet to remove duplicates, then create a new ArrayList from this set, and finally, sort it using Collections.sort().

1import java.util.*;2 3class Solution {4    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {5        Set<Integer> initialPositions = new HashSet<>();6        for (int num : nums) {7            initialPositions.add(num);8        }9        List<Integer> occupiedPositions = new ArrayList<>(initialPositions);10 11        for (int i = 0; i < moveFrom.length; i++) {12            // The remove(Object) operation on an ArrayList is O(N)13            occupiedPositions.remove(Integer.valueOf(moveFrom[i]));14            occupiedPositions.add(moveTo[i]);15        }16 17        // Remove duplicates that may have been introduced and sort18        Set<Integer> finalPositionsSet = new HashSet<>(occupiedPositions);19        List<Integer> result = new ArrayList<>(finalPositionsSet);20        Collections.sort(result);21        return result;22    }23}

Complexity

Time

O(N + M * K + K log K), where N is `nums.length`, M is `moveFrom.length`, and K is the number of unique positions. The `M * K` term dominates because for each of the M moves, we perform a list removal which takes O(K) time. This is generally too slow for the given constraints.

Space

O(K), where K is the number of unique positions. In the worst case, K can be equal to the length of `nums`, so it's O(N).

Trade-offs

Pros

The logic is simple to understand as it directly models the problem statement.

Cons

The time complexity is poor due to the linear time cost of removing an element from an ArrayList.
For large inputs, this approach will likely result in a 'Time Limit Exceeded' error.

A much more efficient approach uses a HashSet to store the occupied positions. The key advantage of a HashSet is that add, remove, and contains operations have an average time complexity of O(1). This allows us to process each move very quickly, avoiding the expensive linear scans required by a list.

Algorithm

Create a HashSet<Integer> to store the occupied positions.
Iterate through the initial nums array and add each position to the HashSet. The set will automatically handle any duplicate positions.
Iterate through the moveFrom and moveTo arrays from i = 0 to moveFrom.length - 1.
For each move, remove moveFrom[i] from the set and add moveTo[i] to the set. These operations are, on average, O(1).
After iterating through all the moves, the HashSet will contain the final, unique set of occupied positions.
Convert the HashSet into an ArrayList.
Sort the ArrayList using Collections.sort().
Return the sorted list.

Walkthrough

This optimized solution leverages the performance characteristics of a HashSet. We begin by populating a HashSet with the initial positions from the nums array. This gives us the unique starting positions in O(N) time, where N is the length of nums.

Next, we iterate through the moveFrom and moveTo arrays. For each i, we perform two simple operations on our set: occupiedPositions.remove(moveFrom[i]) and occupiedPositions.add(moveTo[i]). Since the problem guarantees that moveFrom[i] is an occupied position at the time of the move, we don't need to check for its existence before removal. Both remove and add on a HashSet are average-case O(1) operations. Therefore, processing all M moves takes O(M) time.

After all moves are complete, the HashSet holds the final set of unique occupied positions. The final step is to convert this set to a list and sort it to match the required output format. This conversion and sorting takes O(K log K) time, where K is the number of final unique positions.

1import java.util.*;2 3class Solution {4    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {5        Set<Integer> occupiedPositions = new HashSet<>();6        for (int pos : nums) {7            occupiedPositions.add(pos);8        }9 10        for (int i = 0; i < moveFrom.length; i++) {11            int from = moveFrom[i];12            int to = moveTo[i];13            14            // remove() and add() on HashSet are O(1) on average15            occupiedPositions.remove(from);16            occupiedPositions.add(to);17        }18 19        List<Integer> result = new ArrayList<>(occupiedPositions);20        Collections.sort(result);21        return result;22    }23}

Complexity

Time

O(N + M + K log K), where N is `nums.length`, M is `moveFrom.length`, and K is the number of unique final positions. This breaks down into O(N) for initialization, O(M) for processing moves, and O(K log K) for the final sort. This is very efficient and well within the time limits.

Space

O(K), where K is the number of unique positions. This is used to store the positions in the `HashSet` and the final `ArrayList`. In the worst case, K is at most `nums.length`, so the complexity is O(N).

Trade-offs

Pros

Highly efficient time complexity, making it suitable for large inputs.
The code is clean and directly reflects the logic of maintaining a set of items.

Cons

Slightly higher memory overhead compared to a list due to the nature of hash tables, though the asymptotic complexity is the same.

Solutions

Solution

1class Solution {2public3  List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {4    Set<Integer> pos = new HashSet<>();5    for (int x : nums) {6      pos.add(x);7    }8    for (int i = 0; i < moveFrom.length; ++i) {9      pos.remove(moveFrom[i]);10      pos.add(moveTo[i]);11    }12    List<Integer> ans = new ArrayList<>(pos);13    ans.sort((a, b)->a - b);14    return ans;15  }16}

1class Solution {2public:3  vector<int> relocateMarbles(vector<int> &nums, vector<int> &moveFrom,4                              vector<int> &moveTo) {5    unordered_set<int> pos(nums.begin(), nums.end());6    for (int i = 0; i < moveFrom.size(); ++i) {7      pos.erase(moveFrom[i]);8      pos.insert(moveTo[i]);9    }10    vector<int> ans(pos.begin(), pos.end());11    sort(ans.begin(), ans.end());12    return ans;13  }14};

1class Solution:2    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]: pos = set(nums) for f, t in zip(moveFrom, moveTo): pos . remove(f) pos . add(t) return sorted(pos)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem