Maximum Number of Pairs in Array
EasyPrompt
You are given a 0-indexed integer array nums. In one operation, you may do the following:
- Choose two integers in
numsthat 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 <= 1000 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
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
numsinto anArrayListto allow for easy removal of elements. - Initialize a
pairscounter to 0. - Enter a loop that continues as long as pairs can be found. A
booleanflag can be used to control this loop. - Inside the loop, use nested
forloops to compare every element with every other element in the current list. - If two equal elements are found at indices
iandj: a. Increment thepairscounter. b. Remove both elements from the list. It's crucial to remove the element at the larger indexjfirst to avoid shifting issues with indexi. 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
pairsand the number of leftovers.
Walkthrough
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
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`.
Trade-offs
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.
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.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize a
pairscounter to 0. - Initialize a pointer
ito 0. - Iterate through the array using the pointer
ias long asi < nums.length - 1. - If
nums[i]is equal tonums[i+1]: a. A pair is found. Incrementpairs. b. Advance the pointeriby 2 to skip both elements of the pair. - Else (if
nums[i]is not equal tonums[i+1]): a.nums[i]cannot form a pair with the next element, so we move to the next element by advancing the pointeriby 1. - After the loop finishes, the total number of elements that formed pairs is
2 * pairs. - The number of leftover elements is the original length of the array minus the elements used in pairs:
leftovers = nums.length - 2 * pairs. - Return an array containing
pairsandleftovers.
Walkthrough
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.
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}; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Initialize a frequency array
freqof size 101 to all zeros (given the constraint0 <= nums[i] <= 100). AHashMapcould also be used if the range of numbers were large or unknown. - Iterate through the input array
nums. For each elementnum, increment its corresponding count in the frequency array:freq[num]++. - Initialize
pairs = 0andleftovers = 0. - Iterate through the
freqarray. - For each count
cin the frequency array: a. The number of pairs that can be formed isc / 2. Add this to the totalpairs. b. The number of elements that will be left over isc % 2. Add this to the totalleftovers. - Return an array containing the final
pairsandleftovers.
Walkthrough
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.
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}; }}Complexity
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).
Trade-offs
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].
Solutions
Solution
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 }; }}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}; }}/** * @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]; };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]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}; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.