Pular para o conteúdo principal

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

/**
* 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.

Alternative Solution (Manual Counting)​

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

/**
 * 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;
}

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
  • 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