ks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Td2e,

Problem

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.

Examples

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

Solution

Method 1 - Using frequency map

This problem can be solved using the concept of counting occurrences of elements in the array. The key points are:

Since each pair comprises equal elements, the frequency of each element in the array must be even (because one pair requires 2 of the same element).
If all elements in the array satisfy this condition, the array can be divided into n pairs; otherwise, it cannot.

The approach is as follows:

Use a hash map (or dictionary in Python) to count occurrences of each element.
Check if all counts are even.
Return true if they are, otherwise false.

Code

[{"language":"Java","code":"class Solution {\n    public boolean divideArray(int[] nums) {\n        Map<Integer, Integer> freq = new HashMap<>();\n        for (int num : nums) {\n            freq.put(num, freq.getOrDefault(num, 0) + 1);\n        }\n        \n        boolean ans = true;\n        for (int count : freq.values()) {\n            if (count % 2 != 0) {\n                ans = false;\n                break;\n            }\n        }\n        return ans;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def divideArray(self, nums: List[int]) -> bool:\n        freq = {}\n        for num in nums:\n            freq[num] = freq.get(num, 0) + 1\n            \n        ans = all(count % 2 == 0 for count in freq.values())\n        return ans","lang":"python"}]

Complexity

⏰ Time complexity: O(m), where m is the number of elements in nums.
- Computing the frequency count takes O(m)
- - Checking the frequency counts takes O(m) (since unique elements are bounded by m).
🧺 Space complexity: O(k) , where k is the number of unique elements in nums for using hashmap.

8:["$","div",null,{"className":"max-w-

Related Tags