# Maximum Number of Pairs in Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-number-of-pairs-in-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-pairs-in-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Altimetrik](https://scaleengineer.com/companies/altimetrik)
---
## Problem
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
## 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.
**Time:** 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:** O(N), where N is the number of elements in the input array. This space is required to store the `ArrayList`.
**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.
### Explanation
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.

```java
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()};
    }
}
```
### Algorithm
1. Convert the input array `nums` into an `ArrayList` to allow for easy removal of elements.
2. Initialize a `pairs` counter to 0.
3. Enter a loop that continues as long as pairs can be found. A `boolean` flag can be used to control this loop.
4. Inside the loop, use nested `for` loops to compare every element with every other element in the current list.
5. 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.
6. If the nested loops complete a full scan without finding any pair, the flag will remain `false`, and the outer loop will terminate.
7. The number of leftover elements is the final size of the list.
8. Return an array containing the total `pairs` and the number of leftovers.

## Sorting Approach
A more efficient approach involves sorting the array first. Once sorted, all equal elements will be adjacent to each other, making it very easy to find pairs by iterating through the array just once.
**Time:** O(N log N), which is dominated by the sorting step. The subsequent linear scan of the array takes O(N) time. · **Space:** O(log N) to O(N), depending on the implementation of the sorting algorithm. For Java's `Arrays.sort()` on primitive types, the average space complexity is O(log N).
**Pros:** Significantly more efficient than the brute-force approach.; Easy to implement once the array is sorted.; Space efficient, especially with in-place sorting algorithms.
**Cons:** The O(N log N) time complexity from sorting is not the most optimal solution possible.; This approach modifies the input array in-place, which might not be desirable in some scenarios.
### Explanation
The first step is to sort the input array `nums`. After sorting, we can iterate through the array with a single pointer `i`.

In each step of the iteration, we check if the current element `nums[i]` is equal to the next element `nums[i+1]`. If they are equal, we have found a pair. We increment our pair counter and advance the pointer `i` by 2 to skip both elements of the pair.

If `nums[i]` and `nums[i+1]` are not equal (or if `i` is at the last element), then `nums[i]` cannot form a pair with its neighbor. We simply advance the pointer `i` by 1 to check the next element. This single pass after sorting efficiently counts all pairs.

The number of leftovers can be easily calculated at the end by subtracting the total number of elements used in pairs (`2 * pairs`) from the total length of the array.

```java
import java.util.Arrays;

class Solution {
    public int[] numberOfPairs(int[] nums) {
        if (nums.length < 2) {
            return new int[]{0, nums.length};
        }
        Arrays.sort(nums);
        int pairs = 0;
        int i = 0;
        while (i < nums.length - 1) {
            if (nums[i] == nums[i+1]) {
                pairs++;
                i += 2; // Skip both elements of the pair
            } else {
                i++; // Move to the next element
            }
        }
        
        int leftovers = nums.length - 2 * pairs;
        return new int[]{pairs, leftovers};
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. Initialize a `pairs` counter to 0.
3. Initialize a pointer `i` to 0.
4. Iterate through the array using the pointer `i` as long as `i < nums.length - 1`.
5. If `nums[i]` is equal to `nums[i+1]`:
   a. A pair is found. Increment `pairs`.
   b. Advance the pointer `i` by 2 to skip both elements of the pair.
6. Else (if `nums[i]` is not equal to `nums[i+1]`):
   a. `nums[i]` cannot form a pair with the next element, so we move to the next element by advancing the pointer `i` by 1.
7. After the loop finishes, the total number of elements that formed pairs is `2 * pairs`.
8. The number of leftover elements is the original length of the array minus the elements used in pairs: `leftovers = nums.length - 2 * pairs`.
9. Return an array containing `pairs` and `leftovers`.

## Frequency Counting using an Array
The most optimal approach is to count the frequency of each number in the array. Once we know how many times each number appears, we can easily calculate the number of pairs and leftovers for that number. Summing these up gives the final answer.
**Time:** O(N + K), where N is the number of elements in `nums` and K is the range of values (101 in this case). Since K is a constant, the complexity simplifies to O(N). · **Space:** O(K), where K is the range of values in `nums`. Due to the constraint `0 <= nums[i] <= 100`, K is 101, making the space complexity O(1) (constant).
**Pros:** Optimal time complexity of O(N), making it very fast.; Simple and direct calculation logic after counting frequencies.; Does not require modifying the input array.
**Cons:** Requires extra space for the frequency map/array. However, for this problem, the space is constant due to the constraints on the values of `nums[i]`.
### Explanation
This method avoids direct comparisons between individual elements and instead focuses on their counts. We first iterate through the `nums` array and store the frequency of each number. Given the constraint `0 <= nums[i] <= 100`, a simple integer array of size 101 is a highly efficient choice for the frequency map.

After populating the frequency map, we iterate through the counts. For any number that appears `c` times, we can form `c / 2` pairs, and `c % 2` instances of that number will be left over. We sum up the number of pairs and leftovers across all the distinct numbers to get the total `pairs` and `leftovers`.

An alternative, slightly simpler calculation for leftovers is to first find the total pairs, and then calculate leftovers as `nums.length - 2 * pairs`.

```java
class Solution {
    public int[] numberOfPairs(int[] nums) {
        // Constraints: 0 <= nums[i] <= 100
        int[] freq = new int[101];
        for (int num : nums) {
            freq[num]++;
        }

        int pairs = 0;
        int leftovers = 0;
        for (int count : freq) {
            pairs += count / 2;
            leftovers += count % 2;
        }

        return new int[]{pairs, leftovers};
    }
}
```
### Algorithm
1. Initialize a frequency array `freq` of size 101 to all zeros (given the constraint `0 <= nums[i] <= 100`). A `HashMap` could also be used if the range of numbers were large or unknown.
2. Iterate through the input array `nums`. For each element `num`, increment its corresponding count in the frequency array: `freq[num]++`.
3. Initialize `pairs = 0` and `leftovers = 0`.
4. Iterate through the `freq` array.
5. For each count `c` in the frequency array:
   a. The number of pairs that can be formed is `c / 2`. Add this to the total `pairs`.
   b. The number of elements that will be left over is `c % 2`. Add this to the total `leftovers`.
6. Return an array containing the final `pairs` and `leftovers`.

# Solutions
### CSharp

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

### Java

```java
class Solution {
public
  int[] numberOfPairs(int[] nums) {
    int[] cnt = new int[101];
    for (int x : nums) {
      ++cnt[x];
    }
    int s = 0;
    for (int v : cnt) {
      s += v / 2;
    }
    return new int[]{s, nums.length - s * 2};
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var numberOfPairs =
  function (nums) {
    const cnt = new Array(101).fill(0);
    for (const x of nums) {
      ++cnt[x];
    }
    const s = cnt.reduce((a, b) => a + (b >> 1), 0);
    return [s, nums.length - s * 2];
  };

```

### Python

```python
class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]: cnt = Counter(nums) s = sum(v // 2 for v in cnt . values()) return [s, len(nums) - s * 2]

```

### CPP

```cpp
class Solution {
public:
  vector<int> numberOfPairs(vector<int> &nums) {
    vector<int> cnt(101);
    for (int &x : nums) {
      ++cnt[x];
    }
    int s = 0;
    for (int &v : cnt) {
      s += v >> 1;
    }
    return {s, (int)nums.size() - s * 2};
  }
};

```