Count the Number of Fair Pairs - Leetcode 2563 - Python

0:00 - Read the problem
4:00 - Drawing Explanation
12:45 - Coding Explanation

leetcode 2563

#neetcode #leetcode #python

[zhizheng]

I love the new thumbnail, but its missing the FAANG banner, surprised reaction face, red arrows pointing to random things, beats 100% submissions, other random people reaction faces, whiteboard background.

[bgfreakn]

For some of these more abstract problems, I think it'd be cool to see the code stepped through one last time at the end, maybe in a debugger just to help visualize what's happening. I'm still confused on how the binary search is working for us here.

[NayanGohil]

This is good approach but what I did after sorting is: (number of pairs sum less than equal to upper - number of pairs sum less than lower)

And we can use 2 pointers to find number of pairs sum for a target.

[vayunjain]

Thank you sir, for giving me this idea.
This is a nlog(n) algorithm but its more optimized, the finding of pairs part is O(N).
sort(nums.begin(), nums.end());
int n = nums.size();
long long ans = 0;
int lowerbound = n;
int upperbound = n-1;
for(int i=0;i<n;i++){
while(lowerbound>0 && lowerbound--;
while(upperbound>=0 && upperbound--;
int add = upperbound-lowerbound+1;
if(i<=upperbound && i>=lowerbound) add--;
ans+=add;
}
return ans/2;

[mehulparekh]

Hey NeetCode! Have you ever considered solving problems from different problem sets, like the CSES problem set? There are very few good explanations out there for these problems, and it would be amazing to see your approach on them. Thanks for all the great content you put out!

[khushigupta]

how did you apply sorting, isnt i<j a constraint, which makes it position dependent

[sebastianramirez]

I did a linear scan and got time limit exceeded for case 48/50 so it's really good you found that solution I hate this problem so much

[jp-wixr]

Couldn't think of searching through solution space. Came up with a heap soln. Take the max elem out and allot 1 more store to it. Do while stores > 0. Passes (barely)

[howardlam]

Binary search is not the most efficient way within the loop. For the loop, you can do O(n) if you do 2 pointers.

[anmolgangwal]

how we are maintaining i<j constraints

[nhujamaharjan]

if you are doing binary search for each element in the array wouldn't the time complexity be n * n log(n) = n^2 log(n)?

[HarshaVardhan-pjgp]

I dont understand, after sorting, why aren't we using a two pointer approach and then finding pairs? Wouldnt that be nlogn(sorting) + n ???

[biry]

im at the point where i see the solution but i cant code it out so frustrating

[CS_nb]

why do we need to do binary search, cant you just maintain a window that shrinks over time as we move from left to right

[charlesweng]

Wouldn't it be faster to maintain a window of the valid pairs? as you increment the for loop, the the indexes of where the up and low search returns should be a decreasing sequence.

[DeathSugar]

but how does it hold index constraint after sorting?

[sriniidhi]

I don't get it, why are we adding the difference between the indexs??

[ben_]

how am i still struggling with 1d bisection search problems man😭

[jiafengdu]

How come this solution runtime is faster???? Makes no sense to me. Am I missing something here?

class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
res = 0
lo = hi = len(nums)-1
for i, num in enumerate(nums):
while 0 <= hi and num + nums[hi] > upper:
hi -= 1
while 0 <= lo and num + nums[lo] >= lower:
lo -= 1
res += hi - lo
if lo < i <= hi: res -= 1 # reduce 1 for case of (i, i) in (lo+1, i), (lo+2, i), (lo+3, i), ..., (i-1, i), (i, i), (i, i+1), ..., (i, hi-2), (i, hi-1), (i, hi) because i need < hi
return res//2 # pairs have been counted doubled

[jody]

could anyone elaborate on the overflow issue on the middle point calculation?