#954

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Array of Doubled Pairs

Given an array of even length, check if it can be reordered to satisfy a specific doubling condition.

Problem Statement

Given an integer array arr of even length, return true if it is possible to reorder arr such that for every index i where 0 <= i < len(arr) / 2, the condition arr[2 * i + 1] = 2 * arr[2 * i] holds true. Otherwise, return false.

For example, given arr = [3,1,3,6], it is impossible to reorder the array to satisfy the condition, and the output should be false. The task involves checking if such a reordering is possible using efficient techniques like hash lookup and array scanning.

Examples

Example 1

Input: arr = [3,1,3,6]

Output: false

Example details omitted.

Example 2

Input: arr = [2,1,2,6]

Output: false

Example details omitted.

Example 3

Input: arr = [4,-2,2,-4]

Output: true

We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Constraints

2 <= arr.length <= 3 * 104
arr.length is even.
-105 <= arr[i] <= 105

Solution Approach

Sort and Use Hash Map

First, sort the array in ascending order. Then, use a hash map to store the frequency of each element. This allows quick access to check if a valid pair exists for each element in the sorted array, ensuring that for each element, its double exists in the array.

Greedy Pairing with Sorting

After sorting, try to greedily pair each element with its double. For each element, check if its double exists in the hash map with a remaining frequency greater than zero. If such a pair cannot be found for any element, return false.

Efficient Frequency Management

Use a hash map to manage the frequency of elements. Every time a pair is found, decrease the frequency of both the current element and its double. This ensures that each element and its double are used exactly once.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N)

The time complexity is dominated by the sorting step, which is O(N log N). The space complexity is O(N) due to the storage required for the hash map to track element frequencies.

What Interviewers Usually Probe

Can the candidate efficiently solve the problem with an optimal time complexity?
Does the candidate understand the importance of sorting and hash lookups for this problem?
Is the candidate able to handle both positive and negative numbers correctly in the array?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle negative numbers, which can cause incorrect results when pairing elements.
Not efficiently updating the frequencies of elements after pairing, leading to incorrect answers.
Trying to brute force the problem without using sorting or a hash map for efficient lookups.

Follow-up variants

Allowing odd-length arrays as input and adjusting the logic to handle such cases.
Extending the problem to handle arrays with more complex relationships between elements.
Optimizing the solution to handle very large arrays with constraints closer to arr.length <= 10^5.

FAQ

What is the main approach to solving the Array of Doubled Pairs problem?

The main approach is sorting the array and using a hash map to track element frequencies. Then, attempt to greedily pair each element with its double.

How does sorting help with the Array of Doubled Pairs problem?

Sorting the array ensures that you process smaller elements first, which makes it easier to find their corresponding doubles using hash lookups.

Can negative numbers be part of the array in the Array of Doubled Pairs problem?

Yes, negative numbers can be part of the array, and the solution must correctly pair them with their corresponding doubles, such as -2 with -4.

What is the time complexity of the Array of Doubled Pairs solution?

The time complexity is O(N log N) due to the sorting step, followed by a linear scan of the array using a hash map for lookups.

What is the space complexity of the Array of Doubled Pairs solution?

The space complexity is O(N) because of the hash map used to store the frequencies of array elements.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        freq = Counter(arr)
        if freq[0] & 1:
            return False
        for x in sorted(freq, key=abs):
            if freq[x << 1] < freq[x]:
                return False
            freq[x << 1] -= freq[x]
        return True

Continue Practicing

#1054 distant barcodes #846 hand of straights #1090 largest values from labels