Leetcode 2766: Relocate Marbles

Input: The input consists of the following arrays: nums (the initial marble positions), moveFrom (the positions from which marbles are moved), and moveTo (the positions to which marbles are moved).

Example: nums = [4, 5, 6, 7], moveFrom = [4, 7, 5], moveTo = [6, 8, 7]

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= moveFrom.length <= 10^5

• moveFrom.length == moveTo.length

• 1 <= nums[i], moveFrom[i], moveTo[i] <= 10^9

Output: Return the sorted list of unique positions where at least one marble exists after all moves are completed.

Example: For nums = [4, 5, 6, 7], moveFrom = [4, 7, 5], moveTo = [6, 8, 7], the output is [6, 7, 8].

Constraints:

• The output is a list of unique positions sorted in ascending order.

Goal: The goal is to track all the positions where marbles are placed after each move and return the sorted list of unique positions.

Steps:

• Create a set to store all occupied positions initially using the nums array.

• For each move, transfer marbles from moveFrom[i] to moveTo[i], updating the set of occupied positions.

• Finally, sort and return the positions.

Goal: The constraints ensure that the problem handles arrays of sizes up to 10^5 efficiently.

Steps:

• 1 <= nums.length <= 10^5

• 1 <= moveFrom.length <= 10^5

• moveFrom.length == moveTo.length

• 1 <= nums[i], moveFrom[i], moveTo[i] <= 10^9

Assumptions:

• There will always be at least one marble in the positions specified by moveFrom during the corresponding move.

• Input: For nums = [4, 5, 6, 7], moveFrom = [4, 7, 5], moveTo = [6, 8, 7]

• Explanation: Initially, the marbles are at positions [4, 5, 6, 7]. After each move, the marbles are relocated as described in the example. The final occupied positions are [6, 7, 8].

• Input: For nums = [2, 3, 3, 6], moveFrom = [3, 2], moveTo = [4, 5]

• Explanation: Initially, the marbles are at positions [2, 3, 3, 6]. After each move, the marbles are relocated, and the final occupied positions are [4, 5, 6].

Approach: The solution involves tracking the marbles' positions using a set and performing the moves sequentially while updating the set of occupied positions.

Observations:

• Using a set allows us to efficiently track unique positions occupied by marbles.

• Since we only care about unique positions, a set data structure is ideal for this problem.

Steps:

• Initialize a set to store the unique marble positions from the nums array.

• For each move, check if the position in moveFrom has marbles, then move them to moveTo and update the set.

• At the end, return the sorted list of unique positions.

Empty Inputs:

• The problem constraints ensure that nums, moveFrom, and moveTo are never empty, so no need to handle empty inputs.

Large Inputs:

• Ensure the solution can handle up to 10^5 elements in nums, moveFrom, and moveTo.

Special Values:

• If all marbles end up in one position, the result will be a list with just that position.

Constraints:

• The solution must run efficiently with time complexity close to O(n log n) due to the sorting step at the end.

vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
    map<int, int> mp;  
    for(auto n: nums) mp[n] = 1;
    for(int i = 0; i < moveFrom.size(); ++i){
        if(mp[moveFrom[i]] && moveFrom[i] != moveTo[i]) {
            mp[moveTo[i]] = 1;  mp[moveFrom[i]] = 0;
        }
    }
    vector<int> ans;
    for(auto m: mp) if(m.second) ans.push_back(m.first);
    return ans;
}

1 : Function Definition

vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {

Defines the function `relocateMarbles`, which takes three vectors: `nums` (initial marble positions), `moveFrom` (positions to move from), and `moveTo` (positions to move to). It returns a vector with the final positions of the marbles.

2 : Variable Initialization

    map<int, int> mp;

Initializes a map `mp` to track the marble positions, where the key is the position and the value is a flag indicating whether the position is occupied by a marble.

3 : Mark Initial Positions

    for(auto n: nums) mp[n] = 1;

Iterates through the `nums` vector to mark all the initial marble positions in the `mp` map by setting their corresponding values to 1.

4 : Iterate Over Moves

    for(int i = 0; i < moveFrom.size(); ++i){

Starts a loop to iterate through the `moveFrom` and `moveTo` vectors, processing each pair of positions to move a marble.

5 : Check Valid Move

        if(mp[moveFrom[i]] && moveFrom[i] != moveTo[i]) {

Checks if a marble exists at the position `moveFrom[i]` and if the move is not to the same position (i.e., the `moveFrom` and `moveTo` positions are different).

6 : Update Positions

            mp[moveTo[i]] = 1;  mp[moveFrom[i]] = 0;

If the move is valid, updates the `mp` map: sets the destination position `moveTo[i]` to 1 (marble is placed there) and sets the source position `moveFrom[i]` to 0 (marble is removed).

7 : Prepare Final Answer

    vector<int> ans;

Initializes an empty vector `ans` to store the final positions of the marbles after all moves.

8 : Collect Final Positions

    for(auto m: mp) if(m.second) ans.push_back(m.first);

Iterates through the `mp` map and adds the positions (keys) that have a marble (value is 1) to the `ans` vector.

9 : Return Final Positions

    return ans;

Returns the final list of positions of the marbles in the `ans` vector, which will be in ascending order due to the map's sorting of keys.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The worst case is determined by the sorting of unique positions at the end, where n is the number of unique positions.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is determined by the set storing the unique positions, which in the worst case can store all positions from nums.

Leetcode 2766: Relocate Marbles

Explore →