LeetCode 2766: Relocate Marbles Solution

Master LeetCode problem 2766 (Relocate Marbles), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2766. Relocate Marbles

Medium

Array Hash Table Sorting Simulation

Problem Explanation

Explanation:

To solve this problem, we can simulate the movement of marbles based on the given moveFrom and moveTo arrays. We can use a HashMap to keep track of the marbles at each position. Initially, we populate the HashMap with the marbles at their initial positions. Then, for each step, we move the marbles from moveFrom[i] to moveTo[i] by updating the HashMap. Finally, we collect the occupied positions and return them in sorted order.

Initialize a HashMap to store marbles at positions.
Populate the HashMap with marbles at initial positions.
For each step, update the positions of marbles using moveFrom and moveTo arrays.
Collect occupied positions from the HashMap and return them in sorted order.

Time Complexity: O(n) where n is the length of the moveFrom array. Space Complexity: O(n) where n is the number of occupied positions.

Solution Code

import java.util.*;

class Solution {
    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
        Map<Integer, Integer> positions = new HashMap<>();
        for (int num : nums) {
            positions.put(num, positions.getOrDefault(num, 0) + 1);
        }
        
        for (int i = 0; i < moveFrom.length; i++) {
            int from = moveFrom[i];
            int to = moveTo[i];
            if (positions.containsKey(from)) {
                int count = positions.get(from);
                if (count == 1) {
                    positions.remove(from);
                } else {
                    positions.put(from, count - 1);
                }
                positions.put(to, positions.getOrDefault(to, 0) + 1);
            }
        }
        
        List<Integer> result = new ArrayList<>(positions.keySet());
        Collections.sort(result);
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2766 (Relocate Marbles)?

This page provides optimized solutions for LeetCode problem 2766 (Relocate Marbles) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2766 (Relocate Marbles)?

The time complexity for LeetCode 2766 (Relocate Marbles) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2766 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2766 in Java, C++, or Python.

Back to LeetCode Solutions