3267. Count Almost Equal Pairs II | Weekly Leetcode 412

*************************************************

*************************************************
Timestamps -

00:00 - Agenda
01:30 - Problem Description
03:30 - Brute Force solution
04:45 - Do we need to perform swap in both "X" and "Y"?
07:08 - Pseudo code & Time Complexity
11:10 - Intuition to optimise
16:00 - # of ways to re-arrange "R"
18:25 - Time Complexity & Pseudo code
21:30 - Code Walkthrough

*************************************************
Interview Experiences Playlists -

*********************************************************************

Please show support and subscribe if you find the content useful.

[nabhirajjain]

very nice and clear explanation, thanks :)

[prateekbhaisora]

C++ implementation of above approach:

class Solution {
public:
void findPerm(string &s, int &ind, vector<unordered_set<int>> &perm) {
int n = s.length();
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
swap(s[i], s[j]);
int num = stoi(s);
perm[ind].insert(num);
swap(s[i], s[j]);
}
}
for (int i1=0; i1<n; i1++) {
for (int j1=i1+1; j1<n; j1++) {
for (int i2=0; i2<n; i2++) {
for (int j2=i2+1; j2<n; j2++) {
swap(s[i1], s[j1]);
swap(s[i2], s[j2]);
int num = stoi(s);
perm[ind].insert(num);
swap(s[i2], s[j2]);
swap(s[i1], s[j1]);
}
}
}
}
}
int countPairs(vector<int>& nums) {
int n = nums.size();
int mx = 0;
for (int i=0; i<n; i++) {
string s = to_string(nums[i]);
mx = max(mx, (int)s.length());
}
vector<unordered_set<int>> perm(n);
for (int i=0; i<n; i++) {
perm[i].insert(nums[i]);
string s = to_string(nums[i]);
s = string(mx-s.length(), '0') + s;
findPerm(s, i, perm);
}
unordered_map<int, int> freq;
int cnt = 0;
for (int i=0; i<n; i++) {
for (auto ele : perm[i])
cnt += freq[ele];
freq[nums[i]]++;
}
return cnt;
} // TC = O(n.d^4) SC = O(n.d^4)
};

[chiragbaliyan]

leetcode weekly contest 411 ques D, can you discuss please

[dawodujohnson]

Can we solve it using disjoint set?
Really tried hard but failed at 604/630

[UnknownLearner-odqn]

First viewer🥰, but sir quality is upto 360p only