2206. Divide Array Into Equal Pairs - Solution

Q: Is Divide Array Into Equal Pairs easy or hard?

Divide Array Into Equal Pairs is categorized as an Easy problem on LeetCode with a high acceptance rate. The core idea is recognizing that every number must appear an even number of times, which can be verified with a simple frequency count.

Q: Divide Array Into Equal Pairs Python/Java solution

In Python, use a dictionary or collections.Counter to track frequencies and check if each count is even. In Java, a HashMap performs the same role. Both implementations follow the same O(n) counting strategy.

The 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.

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

Approach overview

Problem Overview: You are given an integer array with an even number of elements. The task is to check whether the array can be divided into pairs such that both elements in every pair are equal. In practice, this means every value in the array must appear an even number of times.

Approach 1: Frequency Count Approach (O(n) time, O(n) space)

This approach counts how many times each number appears using a hash-based frequency table. Iterate through the array once and increment the count for each value. After building the frequency map, iterate over the stored counts and verify that every frequency is even. If any value has an odd frequency, forming equal pairs becomes impossible.

The key insight: each pair consumes exactly two identical elements. A value appearing 2k times can form k valid pairs, but a value appearing 2k + 1 times leaves one element unmatched. Hash lookups and updates are constant time, so the overall complexity stays linear. This approach relies on a hash table and simple counting, making it the most direct and scalable solution for unsorted arrays.

Approach 2: Sorting Approach (O(n log n) time, O(1) or O(n) space)

Another strategy sorts the array first, grouping identical numbers together. After sorting, iterate through the array in steps of two. For each step, compare nums[i] with nums[i+1]. If the two values differ, the array cannot be partitioned into equal pairs.

Sorting ensures duplicates appear next to each other, which simplifies verification. This method uses a common array technique: sequential pair comparison after ordering elements. While the logic is straightforward, sorting introduces an O(n log n) time cost. Space complexity depends on the sorting algorithm—some languages use in-place sorting with O(1) extra space, while others allocate additional buffers.

Recommended for interviews: The frequency count approach is the expected solution. Interviewers typically want to see that you recognize the parity constraint—each number must appear an even number of times. Implementing it with a hash map shows familiarity with counting patterns and constant-time lookups. The sorting approach is still valid and demonstrates problem-solving flexibility, but the linear-time hash counting solution better highlights algorithmic efficiency.

Approach 1: Frequency Count Approach

This 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.

Python

from collections import Counter

def divideArray(nums):
    count = Counter(nums)
    for freq in count.values():
        if freq % 2 != 0:
            return False
    return True

nums = [3, 2, 3, 2, 2, 2]
print(divideArray(nums))

Java

import java.util.HashMap;

public class Main {
    public static boolean divideArray(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int freq : map.values()) {
            if (freq % 2 != 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int[] nums = {3, 2, 3, 2, 2, 2};
        System.out.println(divideArray(nums));
    }
}

C++

#include <vector>
#include <unordered_map>
#include <iostream>

bool divideArray(std::vector<int>& nums) {
    std::unordered_map<int, int> count;
    for (const int num : nums) {
        count[num]++;
    }
    for (const auto& [key, value] : count) {
        if (value % 2 != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    std::vector<int> nums = {3, 2, 3, 2, 2, 2};
    std::cout << (divideArray(nums) ? "true" : "false") << std::endl;
    return 0;
}

JavaScript

function divideArray(nums) {
    const map = new Map();
    for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }
    for (const freq of map.values()) {
        if (freq % 2 !== 0) {
            return false;
        }
    }
    return true;
}

const nums = [3, 2, 3, 2, 2, 2];
console.log(divideArray(nums));

#include <stdio.h>
#include <stdbool.h>

bool divideArray(int* nums, int numsSize){
    int count[501] = {0};  // Given constraint: 1 <= nums[i] <= 500
    for (int i = 0; i < numsSize; ++i) {
        count[nums[i]]++;
    }
    for (int i = 1; i <= 500; ++i) {
        if (count[i] % 2 != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int nums[] = {3, 2, 3, 2, 2, 2};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%s", divideArray(nums, numsSize) ? "true" : "false");
    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public static bool DivideArray(int[] nums) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        foreach (int count in freq.Values) {
            if (count % 2 != 0) {
                return false;
            }
        }
        return true;
    }

    static void Main() {
        int[] nums = {3, 2, 3, 2, 2, 2};
        Console.WriteLine(DivideArray(nums));
    }
}

Python's `collections.Counter` is perfect for this task. We count the frequency of each number and check if all frequencies are even, returning `True` or `False` accordingly.

Complexity

Time Complexity: O(n), where n is the size of `nums`. Space Complexity: O(n).

Try this approach in the editor

Approach 2: Sorting Approach

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.

Python

def divideArray(nums):
    nums.sort()
    for i in range(0, len(nums), 2):
        if nums[i] != nums[i+1]:
            return False
    return True

nums = [3, 2, 3, 2, 2, 2]
print(divideArray(nums))

Java

import java.util.Arrays;

public class Main {
    public static boolean divideArray(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 3, 2, 2, 2};
        System.out.println(divideArray(nums));
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>

bool divideArray(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    for (size_t i = 0; i < nums.size(); i += 2) {
        if (nums[i] != nums[i + 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    std::vector<int> nums = {3, 2, 3, 2, 2, 2};
    std::cout << (divideArray(nums) ? "true" : "false") << std::endl;
    return 0;
}

JavaScript

function divideArray(nums) {
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i += 2) {
        if (nums[i] !== nums[i + 1]) {
            return false;
        }
    }
    return true;
}

const nums = [3, 2, 3, 2, 2, 2];
console.log(divideArray(nums));

#include <stdio.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool divideArray(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    for (int i = 0; i < numsSize; i += 2) {
        if (nums[i] != nums[i + 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    int nums[] = {3, 2, 3, 2, 2, 2};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%s", divideArray(nums, numsSize) ? "true" : "false");
    return 0;
}

using System;

class Solution {
    public static bool DivideArray(int[] nums) {
        Array.Sort(nums);
        for (int i = 0; i < nums.Length; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return false;
            }
        }
        return true;
    }

    static void Main() {
        int[] nums = {3, 2, 3, 2, 2, 2};
        Console.WriteLine(DivideArray(nums));
    }
}

Sorting the array with Python's built-in `sort` function, this solution verifies each pair for equality. Any deviation results in `False`.

Complexity

Time Complexity: O(n log n). Space Complexity: O(1) if using Timsort in-place.

Try this approach in the editor

Approach 3: 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.

TypeScript

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;
}

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
}

Rust

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)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Frequency Count Approach	Time Complexity: O(n), where n is the size of `nums`. Space Complexity: O(n).
Sorting Approach	Time Complexity: O(n log n). Space Complexity: O(1) if using Timsort in-place.
Counting	–

Complexity analysis

Approach	Time	Space	When to Use
Frequency Count (Hash Map)	O(n)	O(n)	General case when the array is unsorted and you want the optimal linear-time solution
Sorting + Pair Check	O(n log n)	O(1) to O(n)	Useful when sorting is already required elsewhere or when avoiding extra hash structures

Frequently asked questions

Is Divide Array Into Equal Pairs easy or hard?

Divide Array Into Equal Pairs is categorized as an Easy problem on LeetCode with a high acceptance rate. The core idea is recognizing that every number must appear an even number of times, which can be verified with a simple frequency count.

Divide Array Into Equal Pairs Python/Java solution

In Python, use a dictionary or collections.Counter to track frequencies and check if each count is even. In Java, a HashMap<Integer, Integer> performs the same role. Both implementations follow the same O(n) counting strategy.

How to solve Divide Array Into Equal Pairs in O(n)?

Traverse the array and store counts of each number in a hash map. After counting, check that every frequency is divisible by two. If any count is odd, return false; otherwise return true. Hash table operations keep the overall complexity at O(n).

What is the best approach for Divide Array Into Equal Pairs?

The best approach uses a hash map to count the frequency of each number. Iterate through the array, record how many times each value appears, and verify that every frequency is even. This method runs in O(n) time with O(n) extra space and works for any unsorted array.

Is Divide Array Into Equal Pairs asked at Google/Amazon/Meta?

Problems involving frequency counting and pair validation commonly appear in interviews at companies like Amazon, Google, and Meta. This problem specifically tests hash table usage, counting logic, and reasoning about element parity in arrays.

What data structure is used in Divide Array Into Equal Pairs?

A hash table (or dictionary) is typically used to store element frequencies. It allows constant-time insertion and lookup while counting occurrences, which enables the optimal O(n) solution.

What is the time complexity of Divide Array Into Equal Pairs?

The optimal solution runs in O(n) time using a frequency count with a hash table. Each element is processed once while updating counts. A sorting-based alternative requires O(n log n) time because of the sort operation.

Divide Array Into Equal Pairs solution and explanation

The problem

Approach overview

Approach 1: Frequency Count Approach

Approach 2: Sorting Approach

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Divide Array Into Equal Pairs solution and explanation

The problem

Approach overview

Approach 1: Frequency Count Approach

Approach 2: Sorting Approach

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems