1885. Count Pairs in Two Arrays - Week 1/5 Leetcode May Challenge

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!
Problem: leetcode.com/p...
Twitch: / larryny
Discord: / discord
Instagram: / larrysomewhere
#leetcode #coding #programming

[@Algorithmist]

Were you able to pair the arrays up?

[@yilangliang5208]

Its really cool to see experts solving problems live!! Hope you feel better soon!

[@huskytusky1706]

Hope you feel better soon Larry, respect that you keep it going no matter what

[@Gzzzzzz111]

For those who still don't understand what the code does, here's a summary:
nums1[ i ] - nums2[ i ] > nums2[ j ] - nums1[ j ]
Each iteration you are fixing the right side of the equation (nums1[j] - nums2[j]) and finding an index i from previous differences such that the left side > the right side.
You might attemp to do it the other way around by fixing the left side of the equation. You can't do that becasue i has to come before j. If you fix the left side, and attemp to find a j such that the left side > the right side, that would mean j comes before i.

[@DJSTEVE42]

Thanks. This helped

[@DJSTEVE42]

Any idea if SortedLists weren't allowed, then what sort of a data structure would we use to tackle this problem ?

[@Gzzzzzz111]

@@DJSTEVE42 SortedList isn't the only solution for this problem. I am assuming you meant the general case where it is the only way to solve a problem (very uncommon on Leetcode). Unfortunately, you'll either have to implement it on your own or switch to other languages. In C++, you can use multiset.

[@Algorithmist]

Ya, I usually talk about this whenever I use it, but I think I was suffering too much from allergies - in other languages there are other things, but in python, probably you want to implement your own BBST. Which is not great, of course, but that would be an interview answer, perhaps.

[@minimalistasimples]

@@DJSTEVE42 Binary Search
Store the difference between 2 arrays into a new array
Sort the new array
Using Binary Search with 2 pointers
Add the largest and smallest elements and store it in a new variable called Sum
If sum > 0: Increment the count to sum of low and high index else move the pointers till low

[@akshayc4017]

Another way of thinking :
(nums1[ i ]-nums2[ i ]) + (nums1[ j ]-nums2[ j ]) > 0
Now the problem breaks down to finding pair in (nums1 - nums2) array where their sum is positive.

[@minimalistasimples]

You could have solved it using Binary Search too