Array of Doubled Pairs

Medium
1128.

Array of Doubled Pairs

Array of Doubled Pairs is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

arr has an even length. Decide whether its elements can be rearranged so that, for every i with 0 <= i < arr.length / 2, the element at position 2 * i + 1 is exactly twice the element at position 2 * i.

In other words: can the whole array be split into pairs (x, 2x), each element used exactly once? Return true if it can.

Example 1

Input
arr = [-6,4,2,-3]
Output
true
Explanation
Pairs `(2, 4)` and `(-3, -6)`.

Example 2

Input
arr = [5,1,5,10]
Output
false
Explanation
`1` needs a `2` and there is none.

Example 3

Input
arr = [0,4,0,2]
Output
true
Explanation
`(0, 0)` and `(2, 4)`.

Constraints

  • 2 <= arr.length <= 3 * 10^4
  • arr.length is even
  • -10^5 <= arr[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canReorderDoubled = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Array of Doubled Pairs — Solution in Python, Java & C++

Array of Doubled Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Array of Doubled Pairs is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Sorting, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

arr has an even length. Decide whether its elements can be rearranged so that, for every i with 0 <= i < arr.length / 2, the element at position 2 * i + 1 is exactly twice the element at position 2 * i.

In other words: can the whole array be split into pairs (x, 2x), each element used exactly once? Return true if it can.

Example 1

Input: arr = [-6,4,2,-3]
Output: true
Explanation: Pairs `(2, 4)` and `(-3, -6)`.

Example 2

Input: arr = [5,1,5,10]
Output: false
Explanation: `1` needs a `2` and there is none.

Example 3

Input: arr = [0,4,0,2]
Output: true
Explanation: `(0, 0)` and `(2, 4)`.

Constraints

  • 2 <= arr.length <= 3 * 10^4
  • arr.length is even
  • -10^5 <= arr[i] <= 10^5

Hints for Array of Doubled Pairs

  1. Hint 1

    Think about the element with the smallest absolute value: can it be the double in its pair?

  2. Hint 2

    No — its partner would have to be half of it, which is smaller in absolute value. So it must pair with twice itself.

  3. Hint 3

    Count the values, visit them in increasing absolute value, and match each remaining copy of x with a copy of 2x. Zeros pair among themselves.

How to solve Array of Doubled Pairs

The element of least absolute value has no smaller half available, so it is forced to pair with its double; repeating that forced choice decides the answer greedily.

Approach

  1. Count every value.
  2. Visit the distinct values in increasing order of absolute value.
  3. For x = 0, the count must be even (zeros pair with each other).
  4. For any other x with c copies left, require at least c copies of 2x, then remove c copies of 2x.
  5. If every value is settled, return true.

Why it works

When x is processed, every value of smaller absolute value has already been settled, so the only remaining partner for a copy of x is 2x (its half x / 2 would be smaller in absolute value and is already used up). The choice is forced, so failing here means no arrangement exists, and succeeding at every step builds one.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Sorting by plain value breaks negatives: for -4 the partner is -8, which is smaller. Sort by absolute value instead.
  • Zero is its own double, so its copies must pair among themselves — an odd count fails.
  • Decrement the double's count by all copies of x at once; otherwise the loop may revisit 2x with a stale count.

Reference solution

Python

from typing import List
from collections import Counter

def canReorderDoubled(arr: List[int]) -> bool:
    count = Counter(arr)
    for x in sorted(count, key=abs):
        c = count[x]
        if c == 0:
            continue
        if x == 0:
            if c % 2:
                return False
            continue
        if count[2 * x] < c:
            return False
        count[2 * x] -= c
    return True

Java

public static boolean canReorderDoubled(int[] arr) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int v : arr) count.merge(v, 1, Integer::sum);
    List<Integer> keys = new ArrayList<>(count.keySet());
    keys.sort((a, b) -> Integer.compare(Math.abs(a), Math.abs(b)));
    for (int x : keys) {
        int c = count.get(x);
        if (c == 0) continue;
        if (x == 0) {
            if (c % 2 != 0) return false;
            continue;
        }
        int d = count.getOrDefault(2 * x, 0);
        if (d < c) return false;
        count.put(2 * x, d - c);
    }
    return true;
}

C++

bool canReorderDoubled(vector<int>& arr) {
    unordered_map<int, int> count;
    for (int v : arr) count[v]++;
    vector<int> keys;
    for (auto& p : count) keys.push_back(p.first);
    sort(keys.begin(), keys.end(), [](int a, int b) { return abs(a) < abs(b); });
    for (int x : keys) {
        int c = count[x];
        if (c == 0) continue;
        if (x == 0) {
            if (c % 2 != 0) return false;
            continue;
        }
        auto it = count.find(2 * x);
        if (it == count.end() || it->second < c) return false;
        it->second -= c;
    }
    return true;
}

JavaScript

var canReorderDoubled = function(arr) {
    var count = new Map();
    for (var i = 0; i < arr.length; i++) count.set(arr[i], (count.get(arr[i]) || 0) + 1);
    var keys = Array.from(count.keys()).sort(function(a, b) { return Math.abs(a) - Math.abs(b); });
    for (var k = 0; k < keys.length; k++) {
        var x = keys[k];
        var c = count.get(x);
        if (c === 0) continue;
        if (x === 0) {
            if (c % 2 !== 0) return false;
            continue;
        }
        var d = count.get(2 * x) || 0;
        if (d < c) return false;
        count.set(2 * x, d - c);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets