335. Array of Doubled Pairs
Medium
Absolute-Value Frequency Matching
Hashing
Problem
Given an integer array arr of even length, return true if it can be reordered so that for every pair of adjacent conceptual elements, one value is exactly twice the other. Equivalently, every value must be matched with its double.
Examples
Example 1
Input: [3,1,3,6]
Output: false
Example 2
Input: [2,1,2,6]
Output: false
Example 3
Input: [4,-2,2,-4]
Output: true
Constraints
� 2 <= arr.length <= 30000
� arr.length is even.
� -100000 <= arr[i] <= 100000
Hints
?? Count every value.
?? Negative numbers make ordinary ascending processing tricky.
?? Process values in increasing order of absolute value and match x with 2 * x.
Expected Complexity
Time: O(n log n)
Space: O(n)
Follow-up
Why does sorting by absolute value correctly handle negative numbers?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[3,1,3,6]Expected
false