Count Nice Pairs In An Array - Leetcode Solution

Problem Statement:

You are given an array nums that consists of integers. Let's define a pair (i, j) is nice if nums[i] + nums[j] == i + j where 0 <= i < j < nums.length.

Return the number of nice pairs of indices. Since that number can be too large, return it modulo 10^9 + 7.

Solution:

The problem states that we need to count the number of nice pairs in an array. A pair is said to be nice if the sum of the elements at the indices is equal to the sum of those indices.

We will start by initializing a dictionary to keep track of the required count. We will loop through the array and for each element, we will compute its contribution to the answer.

First, we will compute the sum of the index and the element at that index. We will then check if this sum has been seen before. If yes, it means we have already seen some elements whose sum of index and value is the same as the current element. Hence we will increment the value of the corresponding key in our dictionary by the count of such elements we have seen so far.

For example, let's say we have seen 2 elements with a sum of index and value equal to 5. Now we have an element whose sum of index and value is also 5. This new element can form a nice pair with any of the previously seen elements. Hence, we will add 2 to our answer and update the count of 5 in our dictionary.

We will keep adding these contributions to our answer for every element in the array and finally return the answer.

Code:

As discussed above, we will maintain a dictionary to store the count of the elements whose sum of value and index is equal.

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        mod = 10**9 + 7 # as given
        count = {}
        ans = 0

We will then loop through the array and calculate the sum of value and index and update our dictionary:

for i in range(len(nums)):
            diff = i - nums[i]
            if diff in count:
                ans += count[diff]
                ans %= mod
                count[diff] += 1
            else:
                count[diff] = 1

We will then return our answer.

return ans

Time Complexity:

The time complexity of this algorithm is O(n) as we loop through the array only once.

Space Complexity:

We use a dictionary to keep track of the count of elements whose sum of index and value is equal. We can have at most n such elements, hence the space complexity of our code is O(n).

Conclusion:

In this problem, we learned how to use a dictionary to keep track of the count of elements whose sum of value and index is equal. This approach helps us solve the problem efficiently with time and space complexity of O(n).

1