Divide Array Into Equal Pairs
EasyPrompt
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 * n1 <= n <= 5001 <= nums[i] <= 500
Approaches
3 approaches with complexity analysis and trade-offs.
This approach relies on the idea that if an array can be divided into pairs of equal elements, then after sorting the array, all equal elements will be adjacent. We can then iterate through the sorted array and check if every pair of adjacent elements at even-starting indices (2*i, 2*i + 1) are identical.
Algorithm
- Sort the input array
numsin non-decreasing order. - Iterate through the sorted array with a step of 2, starting from index 0.
- In each iteration, compare the element at the current index
iwith the element ati+1. - If
nums[i]is not equal tonums[i+1], it's impossible to form a pair, so returnfalse. - If the loop completes without finding any unequal adjacent pairs, it means all elements can be paired up. Return
true.
Walkthrough
The first step is to sort the input array nums. This operation groups all identical elements together. For example, [3,2,3,2,2,2] becomes [2,2,2,2,3,3]. After sorting, if the array can indeed be partitioned into n pairs of equal values, then for every even index i, the element nums[i] must be equal to the element nums[i+1]. We can verify this by iterating through the sorted array with a step of 2. We compare nums[i] and nums[i+1] in each step. If we find any pair that is not equal, we can conclude that the array cannot be divided as required and return false. If the entire loop finishes without finding any such unequal pairs, it confirms that the array can be successfully divided, and we return true.
import java.util.Arrays; class Solution { public boolean divideArray(int[] nums) { // The array has 2 * n elements. If n=0, nums is empty, which is trivially true. if (nums.length == 0) { return true; } // Sort the array to group equal elements together. Arrays.sort(nums); // Iterate through the array, checking pairs of elements. for (int i = 0; i < nums.length; i += 2) { // If a pair of adjacent elements is not equal, it's impossible to form equal pairs. if (nums[i] != nums[i+1]) { return false; } } // If all pairs are equal, the condition is satisfied. return true; }}Complexity
Time
O(N log N), where N is the number of elements in `nums`. The sorting operation is the bottleneck. The subsequent loop to check pairs runs in O(N) time.
Space
O(log N) to O(N). The space complexity depends on the sorting algorithm's implementation. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires `O(log N)` space on average for the recursion stack.
Trade-offs
Pros
The logic is straightforward and easy to understand.
It can be implemented with minimal extra space, depending on the sorting algorithm used.
Cons
The time complexity is dominated by the sorting step, making it less efficient than other approaches for this problem.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.