Given an array of integers nums, return the number of good pairs.
A pair (i, j) is called good if nums[i] == nums[j] and i < j.
Example 1:
Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2:
Input: nums = [1,1,1,1] Output: 6 Explanation: Each pair in the array are good.
Example 3:
Input: nums = [1,2,3] Output: 0
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100This 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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of the array. We are checking all possible pairs. |
| Optimized Approach Using Hash Map | Time Complexity: O(n), since each element is processed once. |
Number of Good Pairs (LeetCode 1512) | Full solution with visuals and examples | Study Algorithms • Nikhil Lohia • 22,650 views views
Watch 9 more video solutions →Practice Number of Good Pairs with our built-in code editor and test cases.
Practice on FleetCode