#2766

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Relocate Marbles

Relocate marbles to new positions in an array by simulating moves, and return sorted occupied positions.

Problem Statement

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. Each element of moveFrom represents a position where marbles are initially located, and each element of moveTo represents the new position where these marbles should be moved.

Throughout moveFrom.length steps, you will change the positions of the marbles. On the ith step, you will move all marbles from position moveFrom[i] to position moveTo[i]. After completing all the steps, return the sorted list of positions that are occupied by at least one marble.

Examples

Example 1

Input: nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]

Output: [5,6,8,9]

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]

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 <= 105
1 <= moveFrom.length <= 105
moveFrom.length == moveTo.length
1 <= 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 the ith move.

Solution Approach

Array Scanning

This solution first scans the initial positions of the marbles in nums and stores them in a set for efficient lookups. This avoids the need to track duplicates in subsequent moves, as sets automatically manage unique entries.

Simulate Marble Movement

Next, simulate each move step-by-step by iterating through moveFrom and moveTo. For each step, remove the marble from moveFrom[i] and add it to moveTo[i]. This step ensures marbles are moved as instructed.

Sorting the Result

After all moves are complete, the remaining positions are sorted. The sorted list ensures that the final output is in the correct order of occupied positions, as required by the problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used to track and simulate the movements. If using a set to manage unique positions, the time complexity is O(n + m log m), where n is the length of nums and m is the number of unique final positions. Sorting the final list of positions requires O(m log m) time, and each move takes constant time with a set lookup.

What Interviewers Usually Probe

Can the candidate efficiently handle updates to the positions of multiple marbles in each move?
Does the candidate consider using a set or hash map to manage the unique positions of marbles?
Is the candidate able to optimize the sorting step to avoid unnecessary computation?

Common Pitfalls or Variants

Common pitfalls

Failing to account for the possibility of multiple marbles being moved to the same position.
Not using efficient data structures like sets to handle unique positions and optimize the move process.
Overcomplicating the sorting step or failing to sort the final result efficiently.

Follow-up variants

Handle a case where nums, moveFrom, and moveTo have large sizes and test for performance.
Consider scenarios where marbles can move from a position to the same position multiple times, ensuring no unnecessary changes are made.
Explore different ways of sorting the final list, such as using a priority queue or quicksort for optimization.

FAQ

How can I solve the 'Relocate Marbles' problem efficiently?

By using array scanning combined with a set or hash map to manage unique positions, you can simulate the marble movements efficiently, and then sort the final list.

What is the time complexity for 'Relocate Marbles'?

The time complexity is O(n + m log m), where n is the length of nums and m is the number of unique final positions after all moves.

Can this problem be solved using sorting?

Sorting is used at the end to return the list of occupied positions in sorted order, but the main challenge is efficiently simulating the marble movements using array scanning and hash lookup.

What is the purpose of using a set in the solution?

A set is used to efficiently manage unique positions of marbles, preventing duplicates and ensuring that only unique positions are considered in the final result.

What are some common mistakes in solving 'Relocate Marbles'?

Common mistakes include failing to manage duplicate positions correctly, not using sets for efficient lookups, and overcomplicating the sorting step.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    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)

Continue Practicing

#2593 find score of an array after marking all elements #3080 mark elements on array by performing queries #2402 meeting rooms iii