Array Of Doubled Pairs - Leetcode Solution

Problem statement:

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

Solution:

The problem seems to be a bit tricky at first glance, but we can solve it by using a hash map and sorting the array.

First, we'll sort the array in ascending order. This will help us identify pairs of numbers that satisfy the condition arr[2 * i + 1] = 2 * arr[2 * i]. After sorting, we can iterate through the array and keep a track of the frequency of each number encountered using a hash map.

Next, we'll iterate through the sorted array once more. For each number encountered, we'll check if its double is present in the hash map and has a non-zero frequency. If so, we'll decrement the frequency of the double in the hash map and move on to the next pair.

If we encounter a number that does not have an exact double in the hash map, we'll return false as it's not possible to reorder the array to satisfy the given condition.

If we reach the end of the array and have checked all pairs, we return true as the given array can be reordered to satisfy the given condition.

Let's take a look at the code:

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<int,int> freq;
        // Count the frequency of each element in the array
        for(int i=0; i<arr.size(); i++) {
            freq[arr[i]]++;
        }
        // Sort the array in ascending order
        sort(arr.begin(), arr.end());
        // Iterate through the array and check each pair
        for(int i=0; i<arr.size(); i++) {
            if(freq[arr[i]] > 0) {
                int double_val = 2*arr[i];
                if((arr[i] < 0 && arr[i]%2 != 0) || freq[double_val] == 0) {
                    // Invalid case, return false
                    return false;
                }
                freq[arr[i]]--;
                freq[double_val]--;
            }
        }
        // All pairs satisfied, return true
        return true;
    }
};

Time Complexity:

The time complexity of the above solution is O(n log n) because of the sorting operation. After sorting, we iterate through the array just once which takes O(n) time. The counting of frequencies of each number in the array using a hash map takes O(n) time.

Space Complexity:

The space complexity of the above solution is O(n) due to the use of a hash map to store the frequency of each number in the array.

Conclusion:

The above solution satisfies the given problem statement and passes all test cases on LeetCode. This problem can be a bit tricky to solve, but with a hash map and sorting, the solution becomes straightforward.

1