You are given an integer array nums consisting of 2 * n integers.
You need to divide nums into n pairs such that:
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 * n1 <= n <= 5001 <= nums[i] <= 500This approach involves counting the frequency of each number in the array. If all frequencies are even, then it is possible to pair the numbers; otherwise, it is not.
The solution creates a frequency count array `count` where each index corresponds to a number in `nums`. As it iterates through `nums`, it increments the frequency for each number. Finally, it checks all frequencies to ensure they're even, which is necessary for perfect pairing. If any frequency is odd, it returns `false`; otherwise, `true`.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is numsSize. Space Complexity: O(1), since the frequency array size is fixed and independent of input size.
This approach involves sorting the array and then checking adjacent elements in pairs. If all pairs are identical, then the array can be divided into equal pairs.
The C solution sorts the array using `qsort` and then compares every adjacent pair for equality. If any pair is not equal, `false` is returned.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if the sort is in-place.
| Approach | Complexity |
|---|---|
| Frequency Count Approach | Time Complexity: O(n), where n is numsSize. Space Complexity: O(1), since the frequency array size is fixed and independent of input size. |
| Sorting Approach | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if the sort is in-place. |
Divide Array Into Equal Pairs - Leetcode 2206 - Python • NeetCodeIO • 5,146 views views
Watch 9 more video solutions →Practice Divide Array Into Equal Pairs with our built-in code editor and test cases.
Practice on FleetCode