Number of Good Pairs
EasyPrompt
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] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses two nested loops to iterate through all possible pairs of indices (i, j) in the array. It checks if the elements at these indices are equal and if i < j. If both conditions are met, a counter is incremented.
Algorithm
- Initialize a counter
goodPairsCountto 0. - Get the length of the array,
n. - Loop with an index
ifrom0ton-2. - Inside this loop, start another loop with an index
jfromi+1ton-1. - Check if
nums[i]is equal tonums[j]. - If they are equal, increment
goodPairsCount. - After the loops complete, return
goodPairsCount.
Walkthrough
The simplest way to solve the problem is to check every possible pair of indices (i, j) and see if they form a good pair. We can use a nested loop structure. The outer loop iterates from i = 0 to n-1, and the inner loop iterates from j = i + 1 to n-1. This structure naturally ensures that i < j. Inside the inner loop, we compare nums[i] and nums[j]. If they are equal, we've found a good pair and we increment our total count. After checking all pairs, the final count is the answer.
class Solution { public int numIdenticalPairs(int[] nums) { int goodPairsCount = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] == nums[j]) { goodPairsCount++; } } } return goodPairsCount; }}Complexity
Time
O(n^2), where n is the number of elements in the `nums` array. This is because for each element, we iterate through the rest of the array, leading to a quadratic number of comparisons.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra memory, making it space-efficient.
Cons
Inefficient for large arrays due to its quadratic time complexity.
Solutions
Solution
class Solution {public int numIdenticalPairs(int[] nums) { int ans = 0; int[] cnt = new int[101]; for (int x : nums) { ans += cnt[x]++; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.