Sponsored
Sponsored
This approach involves using two nested loops to check all possible pairs of indices in the array. For each pair, we check if it satisfies the condition for being a good pair and count it if it does.
Time Complexity: O(n^2), where n is the length of the array. We are checking all possible pairs.
Space Complexity: O(1), as we are not using any additional data structures.
1using System;
2
3public class GoodPairs {
4 public static int NumIdenticalPairs(int[] nums) {
5 int count = 0;
6 for (int i = 0; i < nums.Length; i++) {
7 for (int j = i + 1; j < nums.Length; j++) {
8 if (nums[i] == nums[j]) {
9 count++;
10 }
11 }
12 }
13 return count;
14 }
15
16 public static void Main(string[] args) {
17 int[] nums = {1, 2, 3, 1, 1, 3};
18 Console.WriteLine(NumIdenticalPairs(nums));
19 }
20}In this C# solution, we employ two loops going over each pair (i, j), counting those that fulfill the condition nums[i] == nums[j] and i < j.
This approach optimizes the search for good pairs using a hash map (or dictionary). Instead of checking each pair directly, we track the number of occurrences of each number as we iterate through the array. For each new element, the number of good pairs it can form is equal to the frequency of the element seen so far.
Time Complexity: O(n), since each element is processed once.
Space Complexity: O(1), considering the fixed size of the frequency array which is independent of input size.
1
This C solution uses an array as a frequency counter. As each number is processed, its count in the array gets added to the good pair count, then incremented to indicate its increased frequency.