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.
1#include <stdio.h>
2
3int numIdenticalPairs(int* nums, int numsSize) {
4 int count = 0;
5 for (int i = 0; i < numsSize; i++) {
6 for (int j = i + 1; j < numsSize; j++) {
7 if (nums[i] == nums[j]) {
8 count++;
9 }
10 }
11 }
12 return count;
13}
14
15int main() {
16 int nums[] = {1, 2, 3, 1, 1, 3};
17 int numsSize = sizeof(nums) / sizeof(nums[0]);
18 printf("%d\n", numIdenticalPairs(nums, numsSize));
19 return 0;
20}This C solution uses two for loops to iterate through all pairs of indices. We start with index i and compare it with all subsequent indices j. If a good pair is found, we increment the count variable.
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 Python solution makes use of a dictionary to track how many times each number has appeared. For each element, the count of times it has been seen is added to the total number of good pairs before updating the dictionary with its new frequency.