Divide Array Into Equal Pairs

EASY

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

Approaches

Checkout 3 different approaches to solve Divide Array Into Equal Pairs. Click on different approaches to view the approach and algorithm in detail.

Sorting the Array

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 nums in 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 i with the element at i+1.
If nums[i] is not equal to nums[i+1], it's impossible to form a pair, so return false.
If the loop completes without finding any unequal adjacent pairs, it means all elements can be paired up. Return true.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Divide Array Into Equal Pairs. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Divide Array Into Equal Pairs

Patterns:

Bit ManipulationCounting

Data Structures:

ArrayHash Table