Array of Doubled Pairs

LeetCode 991 | Difficulty: Medium

Medium

Problem Description

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 * 10^4`

- `arr.length` is even.

- `-10^5 <= arr[i] <= 10^5`

Topics: Array, Hash Table, Greedy, Sorting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 274 ms)

Metric	Value
Runtime	274 ms
Memory	45 MB
Date	2022-02-01

Solution

public class Solution {
    public bool CanReorderDoubled(int[] arr) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (var num in arr)
    {
        if (counts.ContainsKey(num))
        {
            counts[num]++;
        }
        else counts.Add(num, 1);
    }
    Array.Sort(arr);
    foreach (var num in arr)
    {
        if (counts[num] == 0) continue;
        
        // in case of negative values we already encountered 2*val e.g. -4 comes before -2 so check if val/2 exists
        int target = num < 0 ? num / 2 : 2 * num;
        if (num < 0 && num % 2 != 0) return false;
        if (!counts.ContainsKey(target) || counts[target] == 0)
            return false;
        counts[target]--;
        counts[num]--;

    }

    return true;
}
}

📜 1 more C# submission(s)

Submission (2022-01-31) — 344 ms, 46 MB

public class Solution {
    public bool CanReorderDoubled(int[] arr) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (var num in arr)
    {
        if(counts.ContainsKey(num))
        {
            counts[num]++;
        }
        else counts.Add(num, 1);
    }
    Array.Sort(arr);
    foreach(var val in arr)
    {
        if(counts[val] == 0) continue;
        
        int want = val < 0 ? val/2 : 2*val;
        if(val < 0 && val%2 != 0) return false;
        if(!counts.ContainsKey(want) || counts[want]==0)
        return false;
        counts[want]--;
        counts[val]--;
        
    }
    
    return true;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.