LeetCode 954: Array of Doubled Pairs Solution

Master LeetCode problem 954 (Array of Doubled Pairs), 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.

954. Array of Doubled Pairs

Medium

Array Hash Table Greedy Sorting

Problem Explanation

Explanation:

To solve this problem, we need to be able to reorder the array such that for every pair of elements arr[2 * i] and arr[2 * i + 1], the second element is twice the first element. We can achieve this by following these steps:

Count the frequency of each element in the array.
Sort the unique elements of the array in ascending order.
For each unique element in the sorted array, do the following:
- If the frequency of that element is greater than the frequency of its double, return false.
- Otherwise, update the frequency of the double of that element.
If all elements are successfully processed, return true.

Time Complexity: O(n log n) where n is the length of the array. Space Complexity: O(n) where n is the length of the array.

Solution Code

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        Arrays.sort(arr);
        for (int num : arr) {
            if (freq.get(num) == 0) {
                continue;
            }
            if (num < 0) {
                if (num % 2 != 0 || freq.getOrDefault(num / 2, 0) <= 0) {
                    return false;
                }
            } else {
                if (freq.getOrDefault(num * 2, 0) <= 0) {
                    return false;
                }
            }
            freq.put(num, freq.get(num) - 1);
            freq.put(num * 2, freq.get(num * 2) - 1);
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 954 (Array of Doubled Pairs)?

This page provides optimized solutions for LeetCode problem 954 (Array of Doubled Pairs) 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 954 (Array of Doubled Pairs)?

The time complexity for LeetCode 954 (Array of Doubled Pairs) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 954 on DevExCode?

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

Back to LeetCode Solutions