Relocate Marbles
MedPrompt
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.
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
HashSetfrom the inputnumsarray to get the initial unique positions. - Convert this
HashSetinto anArrayListcalledpositions. - Iterate through the
moveFromandmoveToarrays, fromi = 0tomoveFrom.length - 1. - In each iteration, find and remove the element
moveFrom[i]from thepositionslist. 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 thepositionslist. - After the loop finishes, the
positionslist may contain duplicate values because a position could be amoveTodestination multiple times. - To get the unique sorted list, create a new
HashSetfrom thepositionslist to eliminate duplicates, then convert it back to anArrayList. - 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().
import java.util.*; class Solution { public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) { Set<Integer> initialPositions = new HashSet<>(); for (int num : nums) { initialPositions.add(num); } List<Integer> occupiedPositions = new ArrayList<>(initialPositions); for (int i = 0; i < moveFrom.length; i++) { // The remove(Object) operation on an ArrayList is O(N) occupiedPositions.remove(Integer.valueOf(moveFrom[i])); occupiedPositions.add(moveTo[i]); } // Remove duplicates that may have been introduced and sort Set<Integer> finalPositionsSet = new HashSet<>(occupiedPositions); List<Integer> result = new ArrayList<>(finalPositionsSet); Collections.sort(result); return result; }}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.
Solutions
Solution
class Solution {public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) { Set<Integer> pos = new HashSet<>(); for (int x : nums) { pos.add(x); } for (int i = 0; i < moveFrom.length; ++i) { pos.remove(moveFrom[i]); pos.add(moveTo[i]); } List<Integer> ans = new ArrayList<>(pos); ans.sort((a, b)->a - b); return ans; }}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.