We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Array of Doubled Pairs

Number: 991

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array of even length arr, determine if it is possible to reorder the array such that for every index i, arr[2i + 1] equals 2 * arr[2i]. In other words, can we form pairs [x, 2*x] using all the elements of the array?

Key Insights

  • Sort the array based on the absolute value of the elements to handle negative numbers correctly.
  • Use a hash table (or frequency counter) to track the occurrence of each element.
  • For each number in the sorted list, if the number is still available in the frequency map, try to pair it with its double.
  • Decrement the appropriate counts and validate that it is possible to find sufficient doubles for all numbers.
  • Special case: when dealing with zeros, pairing works within the same value.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the frequency map.

Solution

The solution starts by counting the frequency of each element in the array. Sorting the array by absolute value ensures that when we process an element, any potential pair (i.e., its double) comes later in the sequence. For each number, if there are available occurrences, we try to match it with its double. If there are not enough doubles available, the answer is false. If all elements can be paired appropriately by decrementing their counts in the frequency map, the function returns true.

Code Solutions

from collections import Counter

def canReorderDoubled(arr):
    # Count frequency for each element in arr
    count = Counter(arr)
    # Sort the array based on the absolute value of elements
    for x in sorted(arr, key=abs):
        # If no x is left to be paired, skip to the next element
        if count[x] == 0:
            continue
        # Check if double the current number exists in sufficient frequency
        if count[2 * x] < count[x]:
            return False
        # Decrement the frequency for the double of x
        count[2 * x] -= count[x]
    return True

# Example usage:
print(canReorderDoubled([4,-2,2,-4]))  # Expected Output: True
← Back to All Questions