Skip to content

2206. Divide Array Into Equal Pairs

Description

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

  • Each element belongs to exactly one pair.
  • The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

 

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

 

Constraints:

  • nums.length == 2 * n
  • 1 <= n <= 500
  • 1 <= nums[i] <= 500

Solutions

Solution 1: Counting

According to the problem description, as long as each element in the array appears an even number of times, the array can be divided into \(n\) pairs.

Therefore, we can use a hash table or an array \(\textit{cnt}\) to record the number of occurrences of each element, then traverse \(\textit{cnt}\). If any element appears an odd number of times, return \(\textit{false}\); otherwise, return \(\textit{true}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        cnt = Counter(nums)
        return all(v % 2 == 0 for v in cnt.values())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public boolean divideArray(int[] nums) {
        int[] cnt = new int[510];
        for (int v : nums) {
            ++cnt[v];
        }
        for (int v : cnt) {
            if (v % 2 != 0) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool divideArray(vector<int>& nums) {
        int cnt[510]{};
        for (int x : nums) {
            ++cnt[x];
        }
        for (int i = 1; i <= 500; ++i) {
            if (cnt[i] % 2) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func divideArray(nums []int) bool {
    cnt := [510]int{}
    for _, x := range nums {
        cnt[x]++
    }
    for _, v := range cnt {
        if v%2 != 0 {
            return false
        }
    }
    return true
}

1
2
3
4
5
6
7
function divideArray(nums: number[]): boolean {
    const cnt: Record<number, number> = {};
    for (const x of nums) {
        cnt[x] = (cnt[x] || 0) + 1;
    }
    return Object.values(cnt).every(x => x % 2 === 0);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
use std::collections::HashMap;

impl Solution {
    pub fn divide_array(nums: Vec<i32>) -> bool {
        let mut cnt = HashMap::new();
        for x in nums {
            *cnt.entry(x).or_insert(0) += 1;
        }
        cnt.values().all(|&v| v % 2 == 0)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var divideArray = function (nums) {
    const cnt = {};
    for (const x of nums) {
        cnt[x] = (cnt[x] || 0) + 1;
    }
    return Object.values(cnt).every(x => x % 2 === 0);
};

Comments