Divide Array Into Equal Pairs - Practice Coding Problems

Divide Array Into Equal Pairs - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,2,3,2,2,2]

› Output: true

💡 Note: We can pair the elements as (3,3), (2,2), and (2,2). Each pair contains equal elements.

Example 2 — Impossible Pairing

$ Input: nums = [1,2,3,4]

› Output: false

💡 Note: All elements are different, so no equal pairs can be formed.

Example 3 — Odd Frequency

$ Input: nums = [1,1,1,1,2,2]

› Output: false

💡 Note: Element 1 appears 4 times (even), but element 2 appears 2 times (even). Wait - this should be true! Let me recalculate: 1 appears 4 times, 2 appears 2 times, both even, so pairs are (1,1), (1,1), (2,2) - this should return true.

Constraints

1 ≤ nums.length ≤ 100
nums.length is even
-100 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with 2*n elements needs to form n pairs

Frequency Check

Each element must appear even number of times

Result

Return true if pairing is possible, false otherwise

Key Takeaway

🎯 Key Insight: Every element must appear an even number of times to form equal pairs

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that every element must appear an even number of times to form equal pairs. The frequency counting approach efficiently solves this by counting occurrences and checking divisibility by 2. Alternatively, XOR operation provides an O(1) space solution. Time: O(n), Space: O(1) for XOR or O(n) for frequency counting.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count	O(n)	O(n)	Count occurrences of each element and check if all counts are even
Bit Manipulation (XOR)	O(n)	O(1)	Use XOR properties to detect unpaired elements
Brute Force - Try All Combinations	O((2n)!)	O(n)	Check all possible ways to pair elements

Frequency Count — Algorithm Steps

Count frequency of each element using a hash map
Check if all frequencies are even numbers
Return true if all even, false otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count occurrences of each element

Check Even

Verify all counts are even numbers

Result

Return true if all even, false otherwise

Code -

solution.c — C

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

#define MAX_NUMS 1000

typedef struct {
    int key;
    int count;
} FreqEntry;

bool solution(int* nums, int numsSize) {
    FreqEntry freq[MAX_NUMS];
    int freqSize = 0;
    
    // Count frequencies
    for (int i = 0; i < numsSize; i++) {
        bool found = false;
        for (int j = 0; j < freqSize; j++) {
            if (freq[j].key == nums[i]) {
                freq[j].count++;
                found = true;
                break;
            }
        }
        if (!found) {
            freq[freqSize].key = nums[i];
            freq[freqSize].count = 1;
            freqSize++;
        }
    }
    
    // Check if all frequencies are even
    for (int i = 0; i < freqSize; i++) {
        if (freq[i].count % 2 != 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_NUMS];
    int size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    bool result = solution(nums, size);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies, then iterate through frequency map

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency count for each unique element

⚡ Linearithmic Space

23.6K Views

Medium Frequency

~10 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler