Maximum Number of Pairs in Array

EASY

Description

You are given a 0-indexed integer array nums. In one operation, you may do the following:

Choose two integers in nums that are equal.
Remove both integers from nums, forming a pair.

The operation is done on nums as many times as possible.

Return a 0-indexed integer array answer of size 2 where answer[0] is the number of pairs that are formed and answer[1] is the number of leftover integers in nums after doing the operation as many times as possible.

Example 1:

Input: nums = [1,3,2,1,3,2,2]
Output: [3,1]
Explanation:
Form a pair with nums[0] and nums[3] and remove them from nums. Now, nums = [3,2,3,2,2].
Form a pair with nums[0] and nums[2] and remove them from nums. Now, nums = [2,2,2].
Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [2].
No more pairs can be formed. A total of 3 pairs have been formed, and there is 1 number leftover in nums.

Example 2:

Input: nums = [1,1]
Output: [1,0]
Explanation: Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [].
No more pairs can be formed. A total of 1 pair has been formed, and there are 0 numbers leftover in nums.

Example 3:

Input: nums = [0]
Output: [0,1]
Explanation: No pairs can be formed, and there is 1 number leftover in nums.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Approaches

Checkout 3 different approaches to solve Maximum Number of Pairs in Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

This approach directly simulates the process described in the problem. It repeatedly scans the array to find two equal numbers, removes them, and counts it as a pair. This continues until no more pairs can be found.

Algorithm

Convert the input array nums into an ArrayList to allow for easy removal of elements.
Initialize a pairs counter to 0.
Enter a loop that continues as long as pairs can be found. A boolean flag can be used to control this loop.
Inside the loop, use nested for loops to compare every element with every other element in the current list.
If two equal elements are found at indices i and j: a. Increment the pairs counter. b. Remove both elements from the list. It's crucial to remove the element at the larger index j first to avoid shifting issues with index i. c. Set the flag to indicate a pair was found and break out of the inner loops to restart the scan on the now-smaller list.
If the nested loops complete a full scan without finding any pair, the flag will remain false, and the outer loop will terminate.
The number of leftover elements is the final size of the list.
Return an array containing the total pairs and the number of leftovers.

The algorithm works by converting the input array into a mutable list, like an ArrayList, to facilitate element removal. It then enters a loop that continues as long as pairs can be formed.

Inside the loop, nested loops are used to scan the list for two equal elements. When a pair is found at indices i and j, the pair count is incremented, and both elements are removed from the list. To avoid index issues, the element at the larger index j is removed first, followed by the element at index i.

After a pair is removed, the search process is restarted from the beginning of the modified, smaller list. This continues until a full scan of the list completes without finding any pairs. The final number of pairs and the size of the remaining list (which represents the leftovers) are then returned.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] numberOfPairs(int[] nums) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }

        int pairs = 0;
        boolean pairFoundInIteration = true;
        while (pairFoundInIteration) {
            pairFoundInIteration = false;
            for (int i = 0; i < numList.size(); i++) {
                for (int j = i + 1; j < numList.size(); j++) {
                    if (numList.get(i).equals(numList.get(j))) {
                        pairs++;
                        // Remove the element with the larger index first
                        numList.remove(j);
                        numList.remove(i);
                        pairFoundInIteration = true;
                        // Break to restart the search on the modified list
                        break;
                    }
                }
                if (pairFoundInIteration) {
                    break;
                }
            }
        }

        return new int[]{pairs, numList.size()};
    }
}

Complexity Analysis

Time Complexity: O(N^3) in the worst case. Finding a single pair requires up to O(N^2) comparisons, and removing an element from an `ArrayList` can take O(N). This process is repeated for each pair found (up to N/2 pairs).Space Complexity: O(N), where N is the number of elements in the input array. This space is required to store the `ArrayList`.

Pros and Cons

Pros:

Conceptually simple and easy to understand as it directly models the operations described in the problem statement.

Cons:

Highly inefficient due to the nested loops and repeated scanning of the list after each removal.
Modifying a list while iterating over it is complex and can be error-prone if not handled carefully.
The time complexity is very high (cubic), making it impractical for larger input sizes.

Code Solutions

Checking out 5 solutions in different languages for Maximum Number of Pairs in Array. Click on different languages to view the code.

public class Solution {
    public int[] NumberOfPairs(int[] nums) {
        int[] cnt = new int[101];
        foreach(int x in nums) {
            ++cnt[x];
        }
        int s = 0;
        foreach(int v in cnt) {
            s += v / 2;
        }
        return new int[] {
            s,
            nums.Length - s * 2
        };
    }
}

Video Solution

Watch the video walkthrough for Maximum Number of Pairs in Array

Patterns:

Counting

Data Structures:

ArrayHash Table

Companies:

Altimetrik |