Leetcode 954: Array of Doubled Pairs

Input: The input consists of an array of integers, arr, with even length.

Example: Input: arr = [6, 3, 4, 8]

Constraints:

• 2 <= arr.length <= 30000

• arr.length is even.

• -105 <= arr[i] <= 105

Output: The output should be a boolean value: true if the array can be reordered as described, false otherwise.

Example: Output: true

Constraints:

• The output will be a boolean indicating if the array can be reordered accordingly.

Goal: The goal is to check whether we can reorder the elements in pairs such that each second element is twice the first element.

Steps:

• 1. Create a frequency map to count occurrences of each element.

• 2. Sort the unique elements by their absolute values.

• 3. For each element, check if the frequency of its double exists. If not, return false.

• 4. Adjust the frequencies accordingly after each pair is formed.

• 5. If all elements are successfully paired, return true; otherwise, return false.

Goal: The input array will always have an even length, and the solution must handle arrays of size up to 30000 efficiently.

Steps:

• The input array length is always even.

• The array elements are in the range [-105, 105].

• The array will contain unique integers.

Assumptions:

• The array will always have an even number of elements.

• We assume the input array is non-empty.

• Input: Input: arr = [6, 3, 4, 8]

• Explanation: In this case, we cannot reorder the array such that for every i, arr[2 * i + 1] = 2 * arr[2 * i] because the elements do not form valid pairs.

• Input: Input: arr = [4, -2, 2, -4]

• Explanation: Here, we can form pairs [-2, -4] and [2, 4], so the array can be reordered to form a valid sequence.

Approach: The approach involves sorting the elements of the array based on their absolute values and then checking if we can pair each element with its double while adjusting frequencies.

Observations:

• The key observation is that we need to pair each element with its double, so sorting the elements will allow us to efficiently check this condition.

• Using a frequency map to track the occurrences of elements is an efficient way to ensure we can match each element with its double.

Steps:

• 1. Build a frequency map of the input array to count the occurrences of each element.

• 2. Sort the elements by their absolute values to handle the smallest numbers first.

• 3. For each element, check if its double exists in the map with sufficient count. If not, return false.

• 4. Decrease the count of the double as it has been paired with the current element.

• 5. If all elements are successfully paired, return true; otherwise, return false.

Empty Inputs:

• The input will not be empty as the length of the array is guaranteed to be at least 2.

Large Inputs:

• For large arrays up to the size limit of 30000, the solution should run in linearithmic time due to sorting, followed by linear passes for pairing.

Special Values:

• Special values like 0 and negative numbers are valid as long as they satisfy the pairing condition.

Constraints:

• The algorithm must run efficiently for large input sizes, particularly for arrays of length up to 30000.

bool canReorderDoubled(vector<int>& arr) {
    
    unordered_map<int, int> c;
    for(int i : arr)
        c[i]++;
    
    vector<int> keys;
    for(auto it: c)
        keys.push_back(it.first);
    
    sort(keys.begin(), keys.end(), [&](int a, int b){
        return abs(a) < abs(b);
    });
    
    for(int x: keys) {
        if(c[x] > c[2 * x])
            return false;
        c[2 * x] -= c[x];
    }
    
    return true;
}

1 : Function Declaration

bool canReorderDoubled(vector<int>& arr) {

The function `canReorderDoubled` takes an array and determines if it can be reordered to form valid (x, 2x) pairs.

2 : Map Initialization

    unordered_map<int, int> c;

Create a hash map `c` to count the frequency of each element in the array.

3 : Frequency Calculation

    for(int i : arr)

Iterate through the array to populate the frequency map `c`.

4 : Increment Frequency

        c[i]++;

Increase the count of the current element in the frequency map.

5 : Key Extraction

    vector<int> keys;

Create a vector `keys` to store unique elements from the frequency map.

6 : Iterate Map

    for(auto it: c)

Iterate through the frequency map to extract unique keys.

7 : Push Keys

        keys.push_back(it.first);

Push each unique key into the `keys` vector for further processing.

8 : Sort Keys

    sort(keys.begin(), keys.end(), [&](int a, int b){

Sort the keys in ascending order of their absolute values using a lambda function.

9 : Absolute Value Comparison

        return abs(a) < abs(b);

Compare the absolute values of two elements to determine their order.

10 : Iterate Keys

    for(int x: keys) {

Iterate through the sorted keys to verify the (x, 2x) pairs.

11 : Pair Check

        if(c[x] > c[2 * x])

If there are more occurrences of `x` than `2x`, the pairing is invalid.

12 : Return False

            return false;

Return `false` immediately if a valid pair cannot be formed for the current key.

13 : Adjust Frequency

        c[2 * x] -= c[x];

Adjust the frequency of `2x` by subtracting the count of `x` after pairing.

14 : Return True

    return true;

Return `true` indicating the array can be reordered to form valid pairs.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The time complexity is O(n log n) due to the sorting step, followed by linear scans to check the pairing conditions.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage required for the frequency map and the sorted keys.

Leetcode 954: Array of Doubled Pairs

Explore →