LeetCode 2206. Divide Array Into Equal Pairs Solution in Java, C++, Python & More | Explanation + Code

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 cnt to record the number of occurrences of each element, then traverse cnt. If any element appears an odd number of times, return false; otherwise, return true.

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

PythonJavaC++GoRustTypeScriptJavaScript

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

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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) } }(code-box)

function divideArray(nums: number[]): boolean { const cnt = Array(501).fill(0); for (const x of nums) { cnt[x]++; } for (const x of cnt) { if (x & 1) return false; } return true; }(code-box)

/** * @param {number[]} nums * @return {boolean} */ var divideArray = function (nums) { const cnt = Array(501).fill(0); for (const x of nums) { cnt[x]++; } for (const x of cnt) { if (x & 1) return false; } return true; };(code-box)