Count Number Of Bad Pairs - Leetcode Solution

Problem Statement:

Given an array of integers nums, a pair (i,j) is called bad if nums[i] > 2*nums[j] and i < j. Return the number of bad pairs.

Example 1:

Input: nums = [1,2,3,4,5] Output: 2 Explanation: There are 2 bad pairs (4,1) and (5,1). Example 2:

Input: nums = [0,0] Output: 0 Explanation: There are no bad pairs since there are no pairs of numbers. Example 3:

Input: nums = [1,3,1,2,1,2,3] Output: 4 Explanation: There are 4 bad pairs (2,1), (3,1), (4,2), (6,5).

Solution:

One of the ways to solve this problem is to utilize a brute-force approach by iterating over all possible pairs of numbers in the array. This approach, however, has a time complexity of O(n^2) which is not very efficient for large input sizes.

A more optimal solution is to sort the array in non-decreasing order and then use a two-pointer approach to find the bad pairs. We begin by initializing two pointers, i and j, to the beginning of the array. Then, we move the j pointer while checking if there exists any bad pair with nums[i] > 2*nums[j]. If such a pair exists, it means that we can move the i pointer as well since there will be bad pairs with i and all the elements after j.

We can use this approach to count the number of bad pairs in O(nlogn) time complexity.

Here's the detailed solution in Python:

class Solution: def reversePairs(self, nums: List[int]) -> int: def mergesort(l, r): if l >= r: return 0 mid = (l + r) // 2 count = mergesort(l, mid) + mergesort(mid + 1, r) j = mid + 1 for i in range(l, mid + 1): while j <= r and nums[i] > nums[j] * 2: j += 1 count += j - (mid + 1)

        nums[l:r+1] = sorted(nums[l:r+1])
        return count
    
    return mergesort(0, len(nums) - 1)

In this Python solution, we first define a helper function called mergesort that takes two indices l and r as input. The mergesort function performs a standard merge sort on the given indices. The key difference is that we count the number of bad pairs while merging the subarrays.

The count value is incremented by j - (mid + 1) every time we find a bad pair with nums[i] > 2*nums[j]. Here, j is the right pointer that moves from mid+1 to r, trying to find a number that satisfies the bad pair condition with nums[i]. We use sorted(nums[l:r+1]) to merge and sort the subarrays during the merging phase.

Finally, we return the count value after calling mergesort recursively on the entire array from index 0 to len(nums) - 1.

1