Maximum Number of Pairs in Array

Easy
597.

Maximum Number of Pairs in Array

Maximum Number of Pairs in Array is an easy coding problem on arrays, hash table and counting, asked in Amazon and TCS interviews.

Repeatedly remove two equal elements from nums and form a pair, until no two equal elements remain.

Return [pairs, leftovers] — the number of pairs formed and the number of elements still in the array.

Example 1

Input
nums = [1,3,2,1,3,2,2]
Output
[3,1]
Explanation
Three pairs (1,1), (3,3), (2,2) leave a single 2.

Example 2

Input
nums = [1,1]
Output
[1,0]

Example 3

Input
nums = [0]
Output
[0,1]

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var numberOfPairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Pairs in Array — Problem & Solution

Maximum Number of Pairs in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Number of Pairs in Array is an easy coding problem on arrays, hash table and counting, asked in Amazon and TCS interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Repeatedly remove two equal elements from nums and form a pair, until no two equal elements remain.

Return [pairs, leftovers] — the number of pairs formed and the number of elements still in the array.

Example 1

Input: nums = [1,3,2,1,3,2,2]
Output: [3,1]
Explanation: Three pairs (1,1), (3,3), (2,2) leave a single 2.

Example 2

Input: nums = [1,1]
Output: [1,0]

Example 3

Input: nums = [0]
Output: [0,1]

Constraints

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

Hints for Maximum Number of Pairs in Array

  1. Hint 1

    Pairs can only form between equal values, so handle each value independently.

  2. Hint 2

    A value occurring c times contributes c / 2 pairs and c % 2 leftovers.

  3. Hint 3

    Sum both across all distinct values.

How to solve Maximum Number of Pairs in Array

Pairing never crosses value boundaries, so the array splits into independent groups and each group's answer is a division and a remainder.

Approach

  1. Count the occurrences of each value.
  2. Add count / 2 to the pair total and count % 2 to the leftover total.
  3. Return both.

Why it works

Within a group of c identical elements, greedy pairing removes two at a time and leaves c mod 2 behind — and no ordering of removals can do better, since every pair uses exactly two.

Complexity

  • Time — O(n)
  • Space — O(V)

Pitfalls

  • Computing leftovers as n - 2 * pairs also works, but only if pairs was summed correctly first.
  • Simulating the removals is fine here but pointlessly slower.

Reference solution

Python

from typing import List

def numberOfPairs(nums: List[int]) -> List[int]:
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    pairs = sum(c // 2 for c in count.values())
    left = sum(c % 2 for c in count.values())
    return [pairs, left]

Java

public static int[] numberOfPairs(int[] nums) {
    int[] count = new int[101];
    for (int x : nums) count[x]++;
    int pairs = 0, left = 0;
    for (int v = 0; v <= 100; v++) {
        pairs += count[v] / 2;
        left += count[v] % 2;
    }
    return new int[] { pairs, left };
}

C++

vector<int> numberOfPairs(vector<int>& nums) {
    vector<int> count(101, 0);
    for (int x : nums) count[x]++;
    int pairs = 0, left = 0;
    for (int v = 0; v <= 100; v++) {
        pairs += count[v] / 2;
        left += count[v] % 2;
    }
    return { pairs, left };
}

JavaScript

var numberOfPairs = function(nums) {
    const count = new Array(101).fill(0);
    for (let i = 0; i < nums.length; i++) count[nums[i]]++;
    let pairs = 0, left = 0;
    for (let v = 0; v <= 100; v++) {
        pairs += Math.floor(count[v] / 2);
        left += count[v] % 2;
    }
    return [pairs, left];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets