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

Divide Array Into Equal Pairs

Number: 2308

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

Given an integer array nums of length 2*n, determine if it is possible to split the array into n pairs such that the two numbers in each pair are equal.

Key Insights

  • The array's length is even, ensuring that pairs can be formed if the conditions are met.
  • For each distinct element in nums, its frequency must be even.
  • Counting the frequency of elements is an efficient way to check if every element can form pairs.
  • Alternatively, sorting the array and checking adjacent pairs is a viable solution.

Space and Time Complexity

Time Complexity: O(n), where n is the number of pairs (or O(2n) elements)
Space Complexity: O(n) in the worst case when all elements are unique

Solution

We can solve this problem by using a hash table (or dictionary) to count the frequency of each number in the array. Once the frequency count is computed, iterate over the hash table and check if every count is even. If any count is odd, then it is impossible to split nums into pairs such that each pair contains equal numbers. This approach efficiently determines the solution in one pass for counting and another pass over the unique keys.

Code Solutions

# Python solution using a dictionary for counting frequencies

def divideArray(nums):
    # Create a dictionary to count frequency of each number
    frequency = {}
    for num in nums:
        # Increment the frequency count for this number
        frequency[num] = frequency.get(num, 0) + 1
    
    # Check each number's frequency to ensure it is even
    for count in frequency.values():
        if count % 2 != 0:
            # If frequency is odd, pairing is not possible
            return False
    return True

# Example usage:
print(divideArray([3, 2, 3, 2, 2, 2]))  # Expected output: True
print(divideArray([1, 2, 3, 4]))        # Expected output: False
← Back to All Questions