algoadvance

Leetcode 2206. Divide Array Into Equal Pairs

Problem Statement

LeetCode Problem 2206: Divide Array Into Equal Pairs

You are given an integer array nums consisting of 2 * n integers. You need to determine if it is possible to divide this array into n pairs such that for each pair (a, b), a == b.

Return true if it is possible to divide the array into n pairs, otherwise return false.

Example:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 numbers and they can be divided into 3 pairs: (3, 3), (2, 2), (2, 2).

Clarifying Questions

1. Can numbers in the array be negative?
   • Yes, numbers in the array can be negative.
2. What is the range of the integer values in the array?
   • Typically, the integer values can be within the range of standard Java integer values [-2^31, 2^31 - 1].
3. Do we need to return the pairs or just determine if it is possible?
   • We only need to return true or false to indicate if it is possible to divide the array into pairs.

Strategy

To determine if it is possible to divide the array into pairs where each pair consists of identical numbers, we can follow these steps:

1. Count the Frequency:
   • Use a HashMap to count the frequency of each number in the array.
2. Check the Frequency Counts:
   • Traverse through the frequency map and check if every count is even. If every count is even, it is possible to pair them up; otherwise, it is not.

Code

Here’s the Java code implementing the above strategy:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean divideArray(int[] nums) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Count the frequency of each number in the array
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        // Check if all counts are even
        for (int count : frequencyMap.values()) {
            if (count % 2 != 0) {
                return false;
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 2, 3, 2, 2, 2};
        System.out.println(solution.divideArray(nums)); // Output: true
    }
}

Time Complexity

• Time Complexity: O(n)
  • We traverse the array once to build the frequency map, which takes O(n) time.
  • We traverse the frequency map to check if all the counts are even, which takes O(m) where m is the number of unique elements in the array. In the worst case, m can be equal to n, making this step also O(n).
  • Thus, the overall time complexity is O(n).
• Space Complexity: O(n)
  • The space used by the frequency map is proportional to the number of unique elements in the array. In the worst case, this could be O(n).

This approach ensures that we efficiently determine if the array can be divided into pairs with equal values.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?