Skip to main content
Talentd

Array of Doubled Pairs - Solution & Explanation

MediumArrayHash TableGreedySorting7 min readAsked at: Google
Practice this problem

Problem Statement

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: arr = [4,-2,2,-4]
Output: true
Explanation: 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

Approach Overview

Problem Overview: You receive an integer array arr. The task is to check whether the array can be reordered so that for every element x, there exists another element 2x. Each number must be used exactly once in a pair. Negative numbers and zeros make the pairing logic trickier, which is why ordering and careful counting are required.

Approach 1: Sorting and Counting (Time: O(n log n), Space: O(n))

This approach combines sorting with frequency counting using a hash table. First count the frequency of each number in a map. Then sort the array by absolute value so smaller magnitudes are processed before their doubles. This order is critical because pairing a number early ensures its double still exists later.

Iterate through the sorted array. For each value x, check if its count is already zero (already paired). If not, verify that 2 * x exists in the frequency map with a positive count. Decrease the counts for both x and 2x. If the double is missing, the array cannot form valid doubled pairs.

The key insight is processing numbers by absolute value. Without this ordering, negative numbers could incorrectly consume values needed for other pairs. Sorting guarantees that when you try to match x, its double has not been prematurely used. This strategy is considered a classic greedy pairing technique.

Approach 2: Two-pointer Technique (Time: O(n log n), Space: O(1) to O(n))

This method starts by sorting the array. After sorting, the algorithm attempts to match smaller numbers with their doubles using two scanning indices. One pointer tracks candidate base numbers while the second searches ahead for elements equal to double the current value.

As the pointers move, matched elements are marked or skipped so they are not reused. If the second pointer finds 2 * arr[i], the pair is recorded and both pointers move forward. If the search pointer advances past possible matches without finding the double, the pairing fails.

This approach emphasizes sequential scanning rather than explicit frequency maps. It works best when the array is already sorted or when memory usage should stay minimal. However, the implementation becomes more delicate when duplicates or negative numbers appear, which is why many engineers prefer the counting approach for clarity.

Recommended for interviews: The sorting + hash counting solution is what most interviewers expect. It demonstrates control over hash map frequency tracking and careful ordering logic. Showing a brute pairing idea first can communicate intuition, but implementing the greedy counting approach shows strong problem-solving skills and handles edge cases like negatives and zeros correctly.

Approach 1: Approach 1: Sorting and Counting

Sort the array and use a map (or dictionary) to count the occurrences of each number. For each number in the sorted array, try to pair it with its double. If a number cannot be paired, return false. Handle zeroes separately as they need pairs to be zero as well.

The function first counts the frequency of each integer in the array using Counter. It then sorts the array by the absolute values of its elements. For each element x in the sorted array, it checks if there's a corresponding 2 * x to make a valid pair. If not possible, it returns false. The function returns true if all elements can be paired appropriately.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(N log N), due to the sorting step. Space Complexity: O(N), needed for the Counter map.

Try this approach in the editor →

Approach 2: Approach 2: Two-pointer Technique

Sort the array and use a two-pointer approach to try and form valid pairs. One pointer will start from the beginning and the other from the end or some valid position. Carefully manage cases with negative numbers and zero separately, since their pairing rules are distinct.

This JavaScript solution uses a map for frequency counting and sorts the keys by their absolute values. It tries to match each value with double that value, reducing count accordingly, and returns false if a pair isn’t possible.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(N log N), due to sorting. Space Complexity: O(N), for storing counts in a map.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Counting

Time Complexity: O(N log N), due to the sorting step. Space Complexity: O(N), needed for the Counter map.

Approach 2: Two-pointer Technique

Time Complexity: O(N log N), due to sorting. Space Complexity: O(N), for storing counts in a map.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Counting (Hash Map)O(n log n)O(n)General case. Safely handles negatives, duplicates, and zeros using frequency tracking.
Two-pointer TechniqueO(n log n)O(1) to O(n)When the array is sorted and you want a sequential scan without maintaining a hash map.

Video Solution

LeetCode 954. Array of Doubled Pairs - Interview Prep Ep 77 • Fisher Coder • 3,357 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Array of Doubled Pairs easy or hard?
Array of Doubled Pairs is classified as a Medium difficulty problem. The challenge comes from handling negative numbers, duplicates, and ordering constraints when forming doubled pairs. Understanding greedy ordering and frequency counting makes the problem manageable.
How to solve Array of Doubled Pairs in O(n)?
A strict O(n) solution is generally not achievable because ordering by magnitude is required to correctly match numbers with their doubles. Most correct implementations sort the array first and then use a frequency map to greedily form pairs. This results in O(n log n) time and O(n) space.
Array of Doubled Pairs Python or Java solution
Python and Java solutions typically use a dictionary or HashMap to store frequencies, then iterate through the array sorted by absolute value. For each value x, the code verifies that 2x exists with a positive count before decrementing both counts. This implementation runs in O(n log n) time and O(n) space.
What is the best approach for Array of Doubled Pairs?
The most reliable approach sorts the array by absolute value and uses a hash map to count frequencies. For each number x, the algorithm checks whether 2x exists and decreases both counts. This greedy pairing strategy handles negative values and duplicates correctly. Time complexity is O(n log n) due to sorting and space complexity is O(n).
What data structure is used in Array of Doubled Pairs?
The core data structure is a hash map that stores the frequency of each number. Combined with sorting by absolute value, the map allows constant-time checks for the required doubled value. Arrays are also used for sorting and iteration.
What is the time complexity of Array of Doubled Pairs?
The optimal solution runs in O(n log n) time because the array must be sorted before pairing elements. After sorting, each element is processed once using constant-time hash map lookups. The space complexity is O(n) for the frequency map used to track remaining numbers.
Is Array of Doubled Pairs asked at Google, Amazon, or Meta?
Array of Doubled Pairs appears in interview preparation lists for companies that test greedy and hash map reasoning. Similar pairing and frequency problems have been reported in interviews at companies like Amazon, Google, and Meta. The question evaluates sorting strategies, edge case handling, and hash table usage.

Ready to solve this problem?

Practice Array of Doubled Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Original Array From Doubled Array