Count Partners

Given an integer array nums, return the total number of "partners" in the array.

Note: Two numbers in our array are partners if they reside at different indices and both contain the same value.

Example(s)

Example 1:

Input: nums = [5, 5, 3, 1, 1, 3, 3]
Output: 5
Explanation:
- 5 (index 0) and 5 (index 1) are partners → 1 pair
- 1 (index 3) and 1 (index 4) are partners → 1 pair
- 3 appears at indices 2, 5, 6:
  - 3 (index 2) and 3 (index 5) are partners → 1 pair
  - 3 (index 2) and 3 (index 6) are partners → 1 pair
  - 3 (index 5) and 3 (index 6) are partners → 1 pair
Total: 1 + 1 + 3 = 5

Example 2:

Input: nums = [1, 2, 3, 4, 5]
Output: 0
Explanation:
All values are unique, so there are no partners.

Example 3:

Input: nums = [1, 1, 1, 1]
Output: 6
Explanation:
Value 1 appears 4 times. Number of pairs = C(4,2) = 4×3/2 = 6
Pairs: (0,1), (0,2), (0,3), (1,2), (1,3), (2,3)

Example 4:

Input: nums = [2, 2, 2, 2, 2]
Output: 10
Explanation:
Value 2 appears 5 times. Number of pairs = C(5,2) = 5×4/2 = 10

Solution

The solution uses hash map and combinatorics:

1. Count frequencies: Use a hash map to count occurrences of each value
2. Calculate pairs: For each value with frequency n, calculate C(n, 2) = n × (n - 1) / 2
3. Sum all pairs: Add up all pairs from all values

Key Insight: If a value appears n times, the number of pairs is C(n, 2) = n × (n - 1) / 2

JavaScript Solution

JavaScript Solution

/**
* Count total number of partners in array
* @param {number[]} nums - Array of integers
* @return {number} - Total number of partners
*/
function countPartners(nums) {
// Step 1: Count frequency of each value
const frequency = new Map();
for (const num of nums) {
  frequency.set(num, (frequency.get(num) || 0) + 1);
}

// Step 2: Calculate pairs for each value
let totalPairs = 0;
for (const count of frequency.values()) {
  // If value appears n times, number of pairs = C(n, 2) = n * (n - 1) / 2
  if (count > 1) {
    totalPairs += (count * (count - 1)) / 2;
  }
}

return totalPairs;
}

// Test cases
console.log('Example 1:', countPartners([5, 5, 3, 1, 1, 3, 3])); // 5
console.log('Example 2:', countPartners([1, 2, 3, 4, 5])); // 0
console.log('Example 3:', countPartners([1, 1, 1, 1])); // 6
console.log('Example 4:', countPartners([2, 2, 2, 2, 2])); // 10
console.log('Test 5:', countPartners([1, 1, 2, 2])); // 2 (1 pair of 1s + 1 pair of 2s)

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution

from typing import List
from collections import Counter

def count_partners(nums: List[int]) -> int:
  """
  Count total number of partners in array
  
  Args:
      nums: List of integers
      
  Returns:
      int: Total number of partners
  """
  # Step 1: Count frequency of each value
  frequency = Counter(nums)
  
  # Step 2: Calculate pairs for each value
  total_pairs = 0
  for count in frequency.values():
      # If value appears n times, number of pairs = C(n, 2) = n * (n - 1) / 2
      if count > 1:
          total_pairs += count * (count - 1) // 2
  
  return total_pairs

# Test cases
print('Example 1:', count_partners([5, 5, 3, 1, 1, 3, 3]))  # 5
print('Example 2:', count_partners([1, 2, 3, 4, 5]))  # 0
print('Example 3:', count_partners([1, 1, 1, 1]))  # 6
print('Example 4:', count_partners([2, 2, 2, 2, 2]))  # 10
print('Test 5:', count_partners([1, 1, 2, 2]))  # 2 (1 pair of 1s + 1 pair of 2s)

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Manual Counting)

Here's an alternative that manually counts pairs (less efficient but more explicit):

JavaScript Alternative

/**
 * Alternative: Manual pair counting (less efficient)
 */
function countPartnersManual(nums) {
  let totalPairs = 0;
  
  // For each index i, count how many indices j > i have the same value
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) {
        totalPairs++;
      }
    }
  }
  
  return totalPairs;
}

Python Alternative

def count_partners_manual(nums: List[int]) -> int:
    """
    Alternative: Manual pair counting (less efficient)
    """
    total_pairs = 0
    
    # For each index i, count how many indices j > i have the same value
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                total_pairs += 1
    
    return total_pairs

Complexity

• Time Complexity:
  • Hash map approach: O(n) - Where n is the length of the array. We iterate through the array once to count frequencies, then iterate through unique values.
  • Manual counting: O(n²) - Nested loops check all pairs.
• Space Complexity:
  • Hash map approach: O(k) - Where k is the number of unique values. We store frequency of each unique value.
  • Manual counting: O(1) - Only uses a counter variable.

Approach

The solution uses hash map and combinatorics:

1. Count frequencies:

   • Iterate through the array
   • Use a hash map to count how many times each value appears

2. Calculate pairs:

   • For each value with frequency n:
     • If n = 1, no pairs (skip)
     • If n > 1, number of pairs = C(n, 2) = n × (n - 1) / 2
   • This is the number of ways to choose 2 items from n items

3. Sum all pairs:

   • Add up pairs from all values
   • Return the total

Key Insights

• Combinatorics: If a value appears n times, there are C(n, 2) pairs
• Hash map: Efficient way to count frequencies
• O(n) time: Optimal time complexity
• Formula: C(n, 2) = n × (n - 1) / 2
• No need to track indices: Only frequency matters

Step-by-Step Example

Let's trace through Example 1: nums = [5, 5, 3, 1, 1, 3, 3]

Step 1: Count frequencies
  frequency = {}
  Process 5: frequency[5] = 1
  Process 5: frequency[5] = 2
  Process 3: frequency[3] = 1
  Process 1: frequency[1] = 1
  Process 1: frequency[1] = 2
  Process 3: frequency[3] = 2
  Process 3: frequency[3] = 3
  
  frequency = {5: 2, 3: 3, 1: 2}

Step 2: Calculate pairs for each value
  Value 5: count = 2
    pairs = 2 × (2 - 1) / 2 = 2 × 1 / 2 = 1
  Value 3: count = 3
    pairs = 3 × (3 - 1) / 2 = 3 × 2 / 2 = 3
  Value 1: count = 2
    pairs = 2 × (2 - 1) / 2 = 2 × 1 / 2 = 1

Step 3: Sum all pairs
  totalPairs = 1 + 3 + 1 = 5

Result: 5

Mathematical Explanation

Combinations Formula:

• C(n, 2) = n! / (2! × (n-2)!) = n × (n-1) / 2

Why this works:

• If a value appears n times at different indices, we want to count all pairs of indices
• Number of ways to choose 2 indices from n indices = C(n, 2)
• This gives us exactly the number of partner pairs

Example: Value 3 appears 3 times (indices 2, 5, 6)

• Pairs: (2,5), (2,6), (5,6) = 3 pairs
• Formula: C(3, 2) = 3 × 2 / 2 = 3 ✓

Visual Representation

Array: [5, 5, 3, 1, 1, 3, 3]
Index:  0  1  2  3  4  5  6

Value 5 (appears 2 times):
  Pairs: (0, 1) → 1 pair

Value 1 (appears 2 times):
  Pairs: (3, 4) → 1 pair

Value 3 (appears 3 times):
  Pairs: (2, 5), (2, 6), (5, 6) → 3 pairs

Total: 1 + 1 + 3 = 5

Edge Cases

• All unique values: Return 0 (no pairs)
• All same value: Return C(n, 2) where n is array length
• Empty array: Return 0
• Single element: Return 0
• Two elements same: Return 1
• Two elements different: Return 0

Important Notes

• Different indices: Partners must be at different indices (same index doesn't count)
• Same value: Partners must have the same value
• Order doesn't matter: Pair (i, j) is the same as (j, i), so we use combinations not permutations
• Combinatorics formula: C(n, 2) = n × (n - 1) / 2

Related Problems

• Number of Good Pairs: Similar problem (LeetCode 1512)
• Count Pairs With Given Sum: Different constraint
• Two Sum: Find pairs that sum to target
• Group Anagrams: Grouping related items

Takeaways

• Combinatorics is useful for counting pairs/combinations
• Hash map efficiently counts frequencies
• Formula C(n, 2) gives number of pairs from n items
• O(n) time is optimal (must process all elements)
• Frequency counting is the key insight