algoadvance

Leetcode 2206. Divide Array Into Equal Pairs

Problem Statement

LeetCode Problem 2206: Divide Array Into Equal Pairs

You are given an integer array nums consisting of 2 * n integers. You need to divide nums into n pairs such that each pair contains exactly two equal elements. Return true if you can divide the array into n pairs, otherwise return false.

Example

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 3 pairs such as (3, 3), (2, 2), (2, 2).

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide the array into pairs.

Clarifying Questions

1. What if nums is empty or has just one element?
   • We are given that nums contains 2 * n elements, so these cases should not occur.
2. Do we have any constraints on the size of nums or the values within nums?
   • Typically, array size constraints and integer constraints given by the platform or problem description apply.

Strategy

1. Frequency Count: Use a hash map to count the frequency of each integer in nums.
2. Check Pairability: Ensure that each integer has an even frequency, as exactly two elements are needed to form a pair.

Steps

1. Initialize Frequency Map: Use a hash map (or array if values are within a small range) to count occurrences of each integer.
2. Check Frequencies: Traverse the frequency map to check if each value’s frequency is even.
3. Return Result: Return true if all values have even frequencies, otherwise return false.

Code

Here’s the implementation in C++:

#include <vector>
#include <unordered_map>

class Solution {
public:
    bool divideArray(std::vector<int>& nums) {
        std::unordered_map<int, int> freq;
        
        // Count frequencies of each number
        for (int num : nums) {
            freq[num]++;
        }
        
        // Check if all frequencies are even
        for (auto& entry : freq) {
            if (entry.second % 2 != 0) {
                return false;
            }
        }
        
        return true;
    }
};

Time Complexity

• Time Complexity: O(n)
  • Counting frequencies takes O(n) time where n is the number of elements in nums.
  • Checking if each frequency is even takes O(m) time where m is the number of distinct elements. In the worst case, m can be n, so this process is O(n).
• Space Complexity: O(m)
  • The hash map stores up to m distinct elements, which in the worst case could be n. Hence, the space complexity is O(n).

This solution efficiently checks if it’s possible to divide the array into equal pairs of elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?