Count Nice Pairs in an Array | Simple Clean | Important suggestion | AMAZON | Leetcode-1814
Vložit
- čas přidán 19. 11. 2023
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 9th Video on our Hash Map/Set Playlist
In this video we will try to solve a very good problem - Count Nice Pairs in an Array (Leetcode -1814).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Count Nice Pairs in an Array
Company Tags : AMAZON
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/count-n...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
I was able to solve this question in one go. Thanks to your old videos 🫡
Excellent! 👌
bhaiya mene apka hint dekhliya ke eqution me changes kerne sir hints lena sahi he ke nehi ?@@codestorywithMIK
Learned new approach of solving problem thank you bhaiya.
tagda approach bro
bro this hint of separating was very accurate🔥
Was able to solve just after seeing your rearrange suggestion 😍😍
having problem in rev, saw ur video.
became everthing clear!!!
i first try it by myself if i cant solve by my self i watch your videos Daily and I post my solution In your video
everyone is a DSA master, until the real GOAT comes in, kudos to you mik.
Means a lot 🙏🙏❤️❤️
Totally agree. Mike is the real Goat of DSA.
I just noticed that mik put this comment in his Instagram story. You deserve this Mik.
It's true, the real goat is mik.
This is perfection
Teaching is an Art. You proved it
Great video 💯
My semester exams are going but I still manage time to watch videos.
Awesome 😇❤️🙏
Came back to see how's my bhai going!! 12k+ subscribers!! gg, and congo
Means a lot Rounaq.
❤️❤️🙏🙏😇😇
master piece explanation sir.
thenks sirrrrrrrr
Most welcome
wow ❤❤
Thanks 👍
nice and helpfull explanation.👍👍
i solved it by using combination formula n*n-1/2
int countNicePairs(vector& nums) {
int nicePairs = 0,mod = 1e9+7;
unordered_map cnt;
for(auto &i: nums){
cnt[i-rev(i)]++;
}
for(auto i: cnt){
int n = i.second;
nicePairs = ((long)n*(n-1)/2 + nicePairs)%mod;
}
return nicePairs;
}
"Sir tussi great ho"- me after watching the video
Means a lot to me 😇❤️
Legend 🫡
Very good video sir and very good explanation. Sir if you get time can you pls discuss leetcode contest problems also. I am a beginner and have started watching your videos and learning. If you could pls do this it will help me a lot
Definitely planning to start one by one Qn. Thank you so much
Bhai please make video on Leetcode : 417. Pacific Atlantic Water Flow
Definitely noted on this.
Thanks to your prev videos. I was able to do it without watchin this video. But still watching for better reach.
class Solution {
public:
int rev(int n){
int ans = 0;
while(n){
ans = ans * 10 + (n%10);
n = n/10;
}
return ans;
}
int countNicePairs(vector& nums) {
unordered_map mp;
int mod = 1e9+7;
int count = 0;
for(int i=0;i
Thank you so much
can you please start videos on leetcode contest problem upsolving ?
Definitely planning to start one by one Qn. Thanks a lot for watching.
class Solution:
def countNicePairs(self, nums: List[int]) -> int:
n=len(nums)
rev_arr=[0]*n
for i in range(n):
rev_num=0
temp=nums[i]
while temp>0:
rem=temp%10
rev_num=rev_num*10+rem
temp=temp//10
rev_arr[i]=rev_num-nums[i]
mod = 1000000007
result = 0
mp=defaultdict(int)
for i in range(n):
result = (result + mp[rev_arr[i]]) % mod
mp[rev_arr[i]]+=1
return result
Incase anyone needs the python code. Happy coding!!
why not reversing a number is On TC?
class Solution {
public:
int M = 1e9+7;
int rev(int n){
int ans = 0;
while(n){
int x = n%10;
ans = ans*10 + x;
n = n/10;
}
return ans;
}
unordered_map mp;
int countNicePairs(vector& v) {
for(int i = 0 ; i < v.size() ; i++){
v[i] = v[i] - rev(v[i]);
mp[v[i]]++;
}
long long int cnt = 0;
for(auto &it:mp){
if(it.second >=2){
long long int x = it.second;
cnt = (cnt + x*(x-1)/2)%M;
}
}
return cnt%M;
}
};
My approach:
class Solution {
public:
unordered_map mp;
int mod=1e9+7;
int rev(int n){
int num=0;
while(n>0){
num*=10;
num+=n%10;
n/=10;
}
return num;
}
int countNicePairs(vector& nums) {
long cnt=0;
// updating nums
for(int i=0;i
Beats 96%
class Solution {
public:
int rev(int num) {
int rever= 0;
while (num != 0) {
int d = num % 10;
rever = rever* 10 + d;
num /= 10;
}
return rever;
}
int countNicePairs(vector& nums) {
int mod=1e9+7;
unordered_map mp;
long int ans=0;
for(int & i :nums){
int tt=rev(i);
int min=i-tt;
if(mp[min]){
ans+=mp[min];
ans%=mod;
mp[min]++;
}else{
mp[min]++;
}
}
return ans;
}
};
cant we say TC as O(10*n) ...as the max the value can be 10^9..which means 10 digits....so can we say it ... instead of O(nlogn) ?
The maximum value of nums[i] is 10^9
So, log10(10^9) -> 9
So, T.C : O(n*9) ~ O(n)
@@codestorywithMIK are hn..matlab i was just asking we can say it like that in the interview right?
It is always advised not to change the given array as it is passed by reference,so shouldn't we make a copy of it?
int countNicePairs(vector& nums) {
map mp;
long long ans=0;
for(int i=0;i
I agree. You can choose to take a separate array and make a copy.
🎉
Leetcode 2006 :) Count Number of Pairs With Absolute Difference K
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
new_arr = []
res = 0
for i in nums :
new_arr.append(i + k)
c = Counter(new_arr)
for i in nums :
if i in c :
res += c[i]
return res
Mik please elaborate question 532 ;)
Let me check.
why can't we use absolute difference, it fails in 10 tc's?
Notice that the index of elements in pair matter.
{1,3,5,2}
Pair (1,5) index of 1 is smaller than index of 5
i < j
hi, I had written code for this problem in java. here is code. class Solution {
public static Long reverse(long x) {
long reversed = 0;
while (x != 0) {
long digit = x % 10;
if (reversed > (Long.MAX_VALUE - digit) / 10) {
return (long)0;
}
reversed = reversed * 10 + digit;
x /= 10;
}
return reversed;
}
public static void putValue(HashMap hs,long value){
if (hs.containsKey(value)) {
long temp = hs.get(value);
hs.put(value, ++temp);
} else {
hs.put(value, (long)1);
}
}
public int countNicePairs(int[] nums) {
System.out.println(nums.length);
HashMap hs = new HashMap();
for(int ele : nums){
long val = ele - reverse(ele);
putValue(hs,val);
}
long ans =0;
for(long ele : hs.values()){
System.out.println(ele);
ans += (ele*(ele-1))/2;
}
return (int)ans;
}
}.
code is failing for the test case where nums array of length 80000 and it only contains 1. my answer is 1599960000 but output is 599959993.
can u explaing why? plz....
Please do a Modulo of ans with 1000000007
solved it under 7 mins,
good to know i am improving thank you bhaiya
cuz of you i finally reached a rating of 1680
touch wood , will soon be a knight :)
my code just uses one loop
code :-
class Solution {
public:
int mod = (int)1e9+7;
int reverse(int num){
int key = num;
int ans = 0;
while(num != 0){
int digit = num%10;
ans = 10*ans + digit;
num = num/10;
}
return ans;
}
int countNicePairs(vector& nums) {
unordered_mapmp;
int ans = 0;
int n = nums.size();
for(int i =0;i
Awesome
public int countNicePairs (int[]nums){
int mod=1000000007;
int n=nums.length;
for(int i=0;i
Similar Leetcode 2364 ( ^ ^ ) Count Number of Bad Pairs :)
class Solution:
def countBadPairs(self, nums: List[int]) -> int:
new_arr = []
good_pairs = 0
n = len(nums)
for i,j in enumerate(nums) :
new_arr.append(i - j)
c = defaultdict(int)
for i in new_arr :
if i in c :
good_pairs += c[i]
c[i] += 1
else:
c[i] = 1
total_pairs = (n * (n - 1)) // 2
return total_pairs - good_pairs
Wow 😅
Thanks for sharing
@@codestorywithMIK
passes 83?84 case can you find mistake
class Solution {
public:
long MOD = 1e9+7;
int value(int n , int r)
{
int res =1;
for(int i=0; i0)
{
dig = dig*10 +num%10;
num = num/10;
}
return dig;
}
int countNicePairs(vector& nums)
{
int result =0;
for(int i=0;i
The issue was with the calculation of the combination using multiplication and division, which could result in incorrect values due to integer division.
Please find the correct code.
class Solution {
public:
long MOD = 1e9 + 7;
long long value(int n, int r) {
long long res = 1;
for (int i = 0; i < r; i++) {
res = (res * (n - i)) % MOD;
res = (res * modInverse(i + 1, MOD)) % MOD;
}
return res;
}
long long modInverse(long long a, long long m) {
long long m0 = m, t, q;
long long x0 = 0, x1 = 1;
if (m == 1)
return 0;
// Apply extended Euclid Algorithm
while (a > 1) {
q = a / m;
t = m;
m = a % m;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0)
x1 += m0;
return x1;
}
int rev(int num) {
int dig = 0;
while (num > 0) {
dig = dig * 10 + num % 10;
num = num / 10;
}
return dig;
}
int countNicePairs(vector& nums) {
int result = 0;
for (int i = 0; i < nums.size(); i++) {
nums[i] = nums[i] - rev(nums[i]);
}
map mp;
for (int i = 0; i < nums.size(); i++) {
mp[nums[i]]++; // number frequency
}
// have to create pair "nC2"
for (auto& i : mp) {
int x = i.second;
result = (result + value(x, 2)) % MOD;
}
return result;
}
};
int countNicePairs(vector& nums) {
unordered_map mp;
int num, pairs = 0, mod = 1e9+7;
for(auto val : nums) {
string s = to_string(val);
reverse(s.begin(), s.end());
mp[val - stoi(s)]++;
}
for(auto it = mp.begin(); it != mp.end(); it++) {
num = it->second;
pairs += (num * (num-1) % mod)/ 2;
}
return pairs;
} -- It's not passing for all cases .. I am messed up and unable to find error can you help out bhya please. ?