💬 Discord
Sign In
NeetCode #65LC-2206EasyArrays & Hashing
← Back to All Problems

#65 · #2206 · Divide Array Into Equal Pairs(将数组划分成相等数对)

📌 Problem Statement & Constraints

You are given an integer array nums of even length. Divide it into n / 2 pairs so that every pair contains two equal elements. Return true if it is possible. Constraints: 2 <= nums.length <= 500, 0 <= nums[i] <= 500.

💡 Core Algorithmic Approaches

  1. If every value occurs an even number of times, the elements can always be paired up (pair equal values with each other).
  2. Conversely, if some value occurs an odd number of times, one copy is left unpaired, so it is impossible.
  3. Therefore the answer is simply whether every frequency is even.
  4. Equivalently, sort the array and check that equal elements occupy indices (0,1), (2,3), ... -- which is the same condition.

💻 Benchmark Python3 Implementation

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        from collections import Counter
        return all(c % 2 == 0 for c in Counter(nums).values())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one counting pass plus a scan over the distinct values.
💾 Space Complexity
O(k) for the counter, where k is the number of distinct values.

⚠️ Interview Pitfalls & Follow-ups

  • Requiring all values to be distinct: the requirement is the opposite -- each value must appear an even number of times.
  • Only checking that the length is even: the length is guaranteed even, but the frequencies need not be.
  • Sorting and checking adjacent pairs greedily: correct, but O(n log n) and more code than a frequency check.