You are given a 0-indexed integer array nums. In one operation, you may do the following:
nums that are equal.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] <= 100In this approach, we count the frequency of each number using a hash map or array. For each number, we determine how many pairs can be formed by dividing the frequency by 2. The leftover elements are the ones not used in pairs.
This C solution uses an array to count occurrences of each number. After counting, it calculates pairs and leftovers by iterating through the frequency array, using integer division and modulus.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) because the frequency array size is fixed.
This approach also involves counting frequencies, but uses a dictionary or hash map. It is particularly convenient for languages with built-in hash map support, such as Python and JavaScript.
Python's Counter class makes it easy to tally counts of each element, and the approach to calculate pairs and remaining elements is direct.
JavaScript
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(n) in the worst case for storing counts.
| Approach | Complexity |
|---|---|
| Frequency Count Approach | Time Complexity: O(n) where n is the length of the array. |
| Hash Map Solution | Time Complexity: O(n) where n is the length of the array. |
Leetcode - Max Number of K-Sum Pairs (Python) • Timothy H Chang • 8,391 views views
Watch 9 more video solutions →Practice Maximum Number of Pairs in Array with our built-in code editor and test cases.
Practice on FleetCode