954. Array of Doubled Pairs

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\ast 10^4$
• arr.length is even.
• $-10^5<=arr[i]<=10^5$

From: LeetCode
Link: 954. Array of Doubled Pairs

Solution:

Ideas:

• Count how many times each value appears (freq).

• Sort the array by absolute value so we always handle smaller magnitudes before their doubles.

• For each value x in that order:

  • If it’s already used (freq[x] == 0), skip.
  • Otherwise we must match it with 2 * x. If freq[2*x] == 0, pairing is impossible → return false.
  • Decrease both counts (we’ve formed one pair (x, 2x)).

• If we finish the loop without failing, every element has been successfully paired → return true.

Code:

#define SHIFT 200000          // enough to cover values from -200000 to 200000
#define MAXVAL 200000
#define FREQ_SIZE (2 * MAXVAL + 1)

// comparator for qsort: sort by absolute value
static int cmpAbs(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    int ax = x < 0 ? -x : x;
    int ay = y < 0 ? -y : y;
    if (ax < ay) return -1;
    if (ax > ay) return 1;
    // if abs equal, any order is fine
    return 0;
}

bool canReorderDoubled(int* arr, int arrSize) {
    static int freq[FREQ_SIZE];
    // reset frequency array
    for (int i = 0; i < FREQ_SIZE; ++i) {
        freq[i] = 0;
    }

    // count frequencies
    for (int i = 0; i < arrSize; ++i) {
        int v = arr[i];
        // v is guaranteed in [-100000, 100000]
        freq[v + SHIFT]++;
    }

    // sort by absolute value
    qsort(arr, arrSize, sizeof(int), cmpAbs);

    // try to pair each number with its double
    for (int i = 0; i < arrSize; ++i) {
        int x = arr[i];
        int idx = x + SHIFT;
        if (freq[idx] == 0) {
            // already used in a previous pair
            continue;
        }

        int doubled = x * 2;
        // doubled is in [-200000, 200000], safe for our freq array
        int idx2 = doubled + SHIFT;

        if (idx2 < 0 || idx2 >= FREQ_SIZE) {
            // doubled value is out of our tracking range, can't pair
            return false;
        }

        if (freq[idx2] == 0) {
            // no available double for x
            return false;
        }

        // use one x and one 2x
        freq[idx]--;
        freq[idx2]--;
    }

    return true;
}