We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Relocate Marbles

Difficulty: Medium

Problem Description

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.

Key Insights

  • We need to track the positions of marbles as they are moved from one position to another.
  • A position is considered occupied if at least one marble is present there.
  • Using a set data structure can help efficiently manage occupied positions, as it automatically handles duplicates.

Space and Time Complexity

Time Complexity: O(n + m log m) where n is the number of moves and m is the number of unique occupied positions after all moves. Space Complexity: O(m) for the set of occupied positions.

Solution

To solve this problem, we will use a set to keep track of the occupied positions of marbles. We will iterate through the moveFrom and moveTo arrays simultaneously. For each move, we will remove the position in moveFrom from our set (if it exists) and add the position in moveTo. After processing all moves, we will convert the set to a list, sort it, and return it. This approach efficiently handles duplicate positions and ensures that we only keep unique occupied positions.

Code Solutions

def relocateMarbles(nums, moveFrom, moveTo):
    occupied_positions = set(nums)  # Initialize the set with the initial positions of marbles
    
    for from_pos, to_pos in zip(moveFrom, moveTo):
        if from_pos in occupied_positions:
            occupied_positions.remove(from_pos)  # Remove the marbles from the moveFrom position
        occupied_positions.add(to_pos)  # Add the marbles to the moveTo position
    
    return sorted(occupied_positions)  # Return the sorted list of occupied positions
← Back to All Questions