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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Relocate Marbles

Number: 2834

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of initial marble positions and two arrays moveFrom and moveTo representing sequential moves, at each step all marbles at the position moveFrom[i] are moved to moveTo[i]. After performing all moves, return the sorted list of positions that have at least one marble.

Key Insights

  • Use a hash map (or dictionary) to count the number of marbles at each position.
  • Simulate each move by transferring the count from moveFrom[i] to moveTo[i].
  • After processing all moves, the keys of the hash map represent the occupied positions.
  • Sorting the keys will give the final sorted list of occupied positions.

Space and Time Complexity

Time Complexity: O(n + m + k log k), where n is the length of nums, m is the number of moves, and k is the number of unique occupied positions. Space Complexity: O(n + m) for the hash map tracking marble counts.

Solution

We initialize a hash map to track the marble count at each position using the initial array nums. For each move defined by moveFrom and moveTo, the marbles at moveFrom[i] are transferred to moveTo[i] by adjusting counts in the map. After processing all moves, the keys of the hash map are the occupied positions, which are then sorted to produce the final result.

Code Solutions

# Python solution for "Relocate Marbles"
def relocate_marbles(nums, moveFrom, moveTo):
    # Create a dictionary to count marbles at each position
    marble_count = {}
    for pos in nums:
        marble_count[pos] = marble_count.get(pos, 0) + 1
    
    # Execute each move by transferring counts
    for frm, to in zip(moveFrom, moveTo):
        count = marble_count.get(frm, 0)
        # Remove the marbles from the source position
        if count:
            del marble_count[frm]
            # Add the marbles to the destination position
            marble_count[to] = marble_count.get(to, 0) + count
    
    # Return sorted list of occupied (non-zero count) positions
    return sorted(marble_count.keys())

# Example usage:
nums = [1, 6, 7, 8]
moveFrom = [1, 7, 2]
moveTo = [2, 9, 5]
print(relocate_marbles(nums, moveFrom, moveTo))  # Expected Output: [5, 6, 8, 9]
← Back to All Questions