@@josuemartinez3682 yeah guys.. how to train our brain to come up with ideas like this on our own... i have a 7 days streak but still i cannot come up with my own ideas. :(
For sure on the harder side of the medium difficulty spectrum. Best I could have done on the spot is a brute force "solution" and try to optimize as much as I could from there
Once you rearrange the equation j - i != nums[j] - nums[i] it becomes j - nums[j] != i - nums[i]. Now you can substract every element with index. The problem becomes how many different elements are there for each element to its left for i in range(len(nums)): nums[i] = i - nums[i] cnt = defaultdict(int) res = 0 for i in range(len(nums)): res += i - cnt[nums[i]] cnt[nums[i]] += 1 return res
I came up with a slight different solution. Its based on the same analogy. count nums[i]-i pairs and we can count all bad pairs by taking product of an entry with all other ones. Since i should be less than j, we need to eliminate answers with j less than i, so we divide final answer by 2. class Solution { public: long long countBadPairs(vector& nums) { int n = nums.size(); unordered_map pairDiffCount; for(int i = 0; i < n; i++) { pairDiffCount[nums[i] - i]++; } long long badPairsCount = 0; for(auto [num, count]: pairDiffCount) { int diff = n - count; badPairsCount += diff * count; } return badPairsCount / 2; } };
Here is how I solved it. Remember from math classes that when you have an equality you can add the same thing to both sides and an equality will still hold. For example if you have x==5 you can add 5 to both sides and end up with x+5 == 10 If the first one is true the second one also is. The same thing holds for non equality. if x! = 5 then x+5 != 10 Now look at the equation j - i != nums[j]-nums[i] add nums[i] to both sides You will end up with j + nums[i] - i != nums[j] now subtract j from both sides. You will get nums[i]-i != nums[j]-j
Another intuition to solve this problem in less time and with less memory required is to simply implement the integer variable of the number of bad pairs tracked inside the algorithm. Then, for each position of the current index at the given integer array we take the difference of the total amount of pairs found in the array and the amount of good pairs encountered until the currently iterated index i inside the for-loop. Otherwise, from what was shown in the video, we would have to increment the total number of pairs, the count of the number of good pairs assigned to the size of the hash map, incrementing it for each iteration of the index i inside the integer array, you get the idea.
We can also just do the bad pairs directly, by substracting the number of matches in the hashmap from all the previously encountered items: func countBadPairs(nums []int) int64 { occ := map[int]int{} count := int64(0) for i,v := range nums { prev := occ[i-v] count+= int64(i - prev) occ[i-v]++ } return count } but still same idea, something like the two sum problem.
You could just rearrange the equation from j - i == nums[j] - nums[i] -> j = nums[j] + i - nums[i] -> j - nums[j] == i - nums[i]. That's how you can get the index - number grouping. You're way also works because it's the negative (number - index) but I think it would be very hard to come up with the line visualization instead of just rearranging the equation.
this feels like a medium when they don't wanna hire you. Really tough to come up with on the spot
yea i was stuck on it for a bit as well, this video made it so much clearer
@@josuemartinez3682 yeah guys.. how to train our brain to come up with ideas like this on our own... i have a 7 days streak but still i cannot come up with my own ideas. :(
For sure on the harder side of the medium difficulty spectrum. Best I could have done on the spot is a brute force "solution" and try to optimize as much as I could from there
This problem was just modified two sum? Not neetcode's solution but @yuvarajyuvi9691's solution down in the comments.
Missed your videos for 2 days 😅
bro's really solved dangerous graphs right here n today uses a loop to find total pair count 💀
Once you rearrange the equation j - i != nums[j] - nums[i] it becomes j - nums[j] != i - nums[i]. Now you can substract every element with index. The problem becomes how many different elements are there for each element to its left
for i in range(len(nums)):
nums[i] = i - nums[i]
cnt = defaultdict(int)
res = 0
for i in range(len(nums)):
res += i - cnt[nums[i]]
cnt[nums[i]] += 1
return res
nice and creative solution, but modifying the input array in-place is bad, I think.
First thought was to calculate good pairs which is easy using hashing ,and just subtract it from Nc2 total pairs :)
agree
I'm so glad you are back
hate these kinda problems..... relies on finding that one trick (aahaaa moment) ... but under interview scenario and constraints its very difficult
I came up with a slight different solution. Its based on the same analogy.
count nums[i]-i pairs
and we can count all bad pairs by taking product of an entry with all other ones.
Since i should be less than j, we need to eliminate answers with j less than i, so we divide final answer by 2.
class Solution {
public:
long long countBadPairs(vector& nums) {
int n = nums.size();
unordered_map pairDiffCount;
for(int i = 0; i < n; i++) {
pairDiffCount[nums[i] - i]++;
}
long long badPairsCount = 0;
for(auto [num, count]: pairDiffCount) {
int diff = n - count;
badPairsCount += diff * count;
}
return badPairsCount / 2;
}
};
goat is back
Here is how I solved it.
Remember from math classes that when you have an equality you can add the same thing to both sides and an equality will still hold. For example if you have
x==5
you can add 5 to both sides and end up with
x+5 == 10
If the first one is true the second one also is.
The same thing holds for non equality.
if
x! = 5
then
x+5 != 10
Now look at the equation
j - i != nums[j]-nums[i]
add nums[i] to both sides
You will end up with
j + nums[i] - i != nums[j]
now subtract j from both sides. You will get
nums[i]-i != nums[j]-j
Mate, you were right. The diagram at 6:12 was enough to crack it!
he showed us how to use the pointers in the diagram
Such a bad question for interview
really , thought it was a good question really makes you think.
Thank you for the daily!
Another intuition to solve this problem in less time and with less memory required is to simply implement the integer variable of the number of bad pairs tracked inside the algorithm. Then, for each position of the current index at the given integer array we take the difference of the total amount of pairs found in the array and the amount of good pairs encountered until the currently iterated index i inside the for-loop. Otherwise, from what was shown in the video, we would have to increment the total number of pairs, the count of the number of good pairs assigned to the size of the hash map, incrementing it for each iteration of the index i inside the integer array, you get the idea.
how long did it take you to discover the optimal solution?
Cant we get total number of pairs by doing this N*(N-1)/2 ?
Yeah, simple arithmetic progression sum
i did'nt get it
So every point (provided there's more than one) that is on the same slope is a good pair?
Just read the hints in the question at Leetcode. They are way too easier and better!
diagram was a nice instrument for this problem
We can also just do the bad pairs directly, by substracting the number of matches in the hashmap from all the previously encountered items:
func countBadPairs(nums []int) int64 {
occ := map[int]int{}
count := int64(0)
for i,v := range nums {
prev := occ[i-v]
count+= int64(i - prev)
occ[i-v]++
}
return count
}
but still same idea, something like the two sum problem.
You could just rearrange the equation from j - i == nums[j] - nums[i] -> j = nums[j] + i - nums[i] -> j - nums[j] == i - nums[i]. That's how you can get the index - number grouping. You're way also works because it's the negative (number - index) but I think it would be very hard to come up with the line visualization instead of just rearranging the equation.
So, total pairs is essentially NC2? and good pairs are just FreqC2? So the bad count is NC2- F1C2 -F2C2.... ?
Selamınaleyküm
Clever code...
not using (n)*(n-1)/2;
How is someone that solves code in python daily does not automatically use enumerate?
the one whose intention is to teach to all levels, not to show off.
Can u post 7th day problem explanation
goat goat goat
Does anyone try to solve it using combinatorics? few lines, but the time limit was exceeded ☹
goat