Leetcode 2341: Maximum Number of Pairs in Array

Input: The input consists of an integer array `nums` of length `n`.

Example: nums = [4, 2, 7, 4, 2, 7, 7]

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

Output: Return an array where the first element is the number of pairs formed, and the second element is the number of leftover integers.

Example: [3, 1]

Constraints:

Goal: The goal is to count the number of pairs and leftover elements in the input array.

Steps:

• Use a frequency count to track the occurrence of each integer in the array.

• For each integer, calculate how many pairs can be formed by dividing the frequency by 2.

• Count the leftover integers, which are the remainder after pairing.

Goal: The array contains integers between 0 and 100, and the length of the array can be between 1 and 100.

Steps:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

Assumptions:

• The input array is valid and contains integers within the specified range.

• Input: nums = [4, 2, 7, 4, 2, 7, 7]

• Explanation: We form pairs with the identical integers and count the number of leftover elements. This example results in 3 pairs and 1 leftover element.

Approach: We will count the frequency of each number and then calculate how many pairs can be formed and how many leftover elements remain.

Observations:

• We can efficiently count the frequency of each integer using a hashmap or an array.

• The problem boils down to counting pairs and calculating the leftover elements.

• We can use an array of size 101 to store the counts of each number, and then calculate the pairs and leftovers.

Steps:

• Initialize an array `cnt` to store the count of each integer from 0 to 100.

• Iterate through the `nums` array and update the count of each integer in `cnt`.

• For each integer, calculate the number of pairs formed by dividing the count by 2 and calculate the leftover by taking the modulus.

Empty Inputs:

• Empty input is not valid as per the problem constraints.

Large Inputs:

• The solution should efficiently handle arrays of length up to 100.

Special Values:

• If all elements are the same, the number of pairs will be `nums.length // 2`.

Constraints:

• The length of `nums` is at least 1, and the integers are between 0 and 100.

  // even counter
  vector<int> numberOfPairs(vector<int>& nums) {
  int cnt[101] = {}, pairs = 0;
  for (int n : nums)
      pairs += ++cnt[n] % 2 == 0 ? 1 : 0;
  return { pairs, (int)nums.size() - pairs * 2 };
  }

1 : Function Definition

  vector<int> numberOfPairs(vector<int>& nums) {

The function `numberOfPairs` takes a vector of integers `nums` as input and returns a vector of two integers: the number of pairs and the remaining unpaired elements.

2 : Variable Declaration

  int cnt[101] = {}, pairs = 0;

The array `cnt` is used to count the occurrences of each element in `nums`. `pairs` is initialized to 0 to count the number of even pairs.

3 : Loop

  for (int n : nums)

A for-each loop that iterates over each element `n` in the `nums` array.

4 : Pair Counting

      pairs += ++cnt[n] % 2 == 0 ? 1 : 0;

For each element `n`, we increment its count in `cnt[n]` and check if the count is even. If it is, we increase the `pairs` counter.

5 : Return

  return { pairs, (int)nums.size() - pairs * 2 };

The function returns a vector with two elements: the number of pairs (`pairs`) and the number of remaining unpaired elements (calculated as the total size of the array minus twice the number of pairs).

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the input array `nums`, as we iterate over the array once and perform constant-time operations for each element.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we only use a fixed-size array of 101 elements for the frequency count.

Leetcode 2341: Maximum Number of Pairs in Array

Explore →