Thanks Aryan, i couldn't do the 4th question today , luckily i landed here and learned a new concept i.e Policy Based Data Structure and also got to learn Fenwick tree from your video , all because of this single video. great work man !!!
import java.util.HashMap; import java.util.Map; class FenwickTree { private int N; private Map bit; FenwickTree(int n) { N = n; bit = new HashMap(); } int sum(int i) { int tot = 0; while (i > 0) { if (bit.containsKey(i)) { tot += bit.get(i); } i -= i & -i; } return tot; } int sumRange(int start, int end) { return sum(end) - sum(start - 1); } void update(int i, int val) { while (i numGreaterArr2) { arr1.add(nums[i]); bit1.update(nums[i], 1); } else if (numGreaterArr1 < numGreaterArr2) { arr2.add(nums[i]); bit2.update(nums[i], 1); } else { if (arr2.size() < arr1.size()) { arr2.add(nums[i]); bit2.update(nums[i], 1); } else { arr1.add(nums[i]); bit1.update(nums[i], 1); } } } int[] resultArray = new int[arr1.size() + arr2.size()]; int index = 0; for (int num : arr1) { resultArray[index++] = num; } for (int num : arr2) { resultArray[index++] = num; } return resultArray; } }
13:07 no offence but isnot is something like just copy pasting code if we know before hand. I had solved A and B and there were some logics to implement but in D its like we can just copy the template. I am just a beginner so just writing my thoughts.
Can you post a generic solution which can be used in any language? I got the intuition of what I need to do but couldn't figure out how to code it. Once I saw you are using a STL for cpp I just stopped watching.
Although you stammer a bit, but your efforts are really commendable 👏
the way you explain its amazing ,"I really enjoy watching your videos. 👏"
To avoid the use of pair we can use the #define ordered_set tree
instead of #define ordered_set tree
Right
But this works only when you don't have to erase elements from the set I think
Thanks Aryan, i couldn't do the 4th question today , luckily i landed here and learned a new concept i.e Policy Based Data Structure and also got to learn Fenwick tree from your video , all because of this single video. great work man !!!
lower bound & upper bound is directly available for ordered set, then why aryan said only two function is available for ordered set ??
Well done.
Shashank bhai ❤️❤️🫂
What about Java users
Use a fenwick tree implementation.
class FenwickTree{
public:
int N;
unordered_map bit;
FenwickTree(int n){
N = n;
}
int sum(int i){
int tot = 0;
while(i > 0){
tot += bit[i];
i -= i & -i;
}
return tot;
}
int sum_range(int start, int end){
return sum(end) - sum(start);
}
void update(int i, int val){
while(i num_greater_arr2){
arr1.push_back(nums[i]);
bit1.update(nums[i],1);
}
else if(num_greater_arr1 < num_greater_arr2){
arr2.push_back(nums[i]);
bit2.update(nums[i],1);
}
else{
if(arr2.size() < arr1.size()){
arr2.push_back(nums[i]);
bit2.update(nums[i],1);
}
else{
arr1.push_back(nums[i]);
bit1.update(nums[i],1);
}
}
}
for(int i = 0; i < arr2.size(); i++) arr1.push_back(arr2[i]);
return arr1;
}
};
import java.util.HashMap;
import java.util.Map;
class FenwickTree {
private int N;
private Map bit;
FenwickTree(int n) {
N = n;
bit = new HashMap();
}
int sum(int i) {
int tot = 0;
while (i > 0) {
if (bit.containsKey(i)) {
tot += bit.get(i);
}
i -= i & -i;
}
return tot;
}
int sumRange(int start, int end) {
return sum(end) - sum(start - 1);
}
void update(int i, int val) {
while (i numGreaterArr2) {
arr1.add(nums[i]);
bit1.update(nums[i], 1);
} else if (numGreaterArr1 < numGreaterArr2) {
arr2.add(nums[i]);
bit2.update(nums[i], 1);
} else {
if (arr2.size() < arr1.size()) {
arr2.add(nums[i]);
bit2.update(nums[i], 1);
} else {
arr1.add(nums[i]);
bit1.update(nums[i], 1);
}
}
}
int[] resultArray = new int[arr1.size() + arr2.size()];
int index = 0;
for (int num : arr1) {
resultArray[index++] = num;
}
for (int num : arr2) {
resultArray[index++] = num;
}
return resultArray;
}
}
Bro, how will pbds work here, since ordered_set can store unique elements and we will not be able to store same element multiple times.
change less to less_equal, then it will store duplicates too
Bro very much intuitive...1 comment ❤
bhaiya is the problem only cp based , can it also come in OA /interview ?? please reply
No
why we cant use multiset and upper_bound approach here
For that, we have to sort first. So the complexity will be n*nlogn*logn
Okay, got it.
So, if there are no duplicate elements, then we can use set and upper bound, right?
@@Gauravsharma-qw3mf no in this ques we also want to know that how many values are greater than a specific key which pbds provides easily
You can do binary search on set
Do you solve this problem using this method, If so please provide the submissin link
use multiset to take duplicate also
you can but how will you find all elements lesser than or greater than a particular element as in this case in order of logn
can we not use upper_bound to find all greater elements.
By saying binary search aryan means to say using upper or loweer bound function to find the count of element greater than a particular element
Not able to understand you said we can't simply put indexes in pair but in code you did the same thing.
13:07 no offence but isnot is something like just copy pasting code if we know before hand. I had solved A and B and there were some logics to implement but in D its like we can just copy the template. I am just a beginner so just writing my thoughts.
that's why it is always said to do harder problems cover more of these topics like segment tree, fenwick , pbds , binary lifting , line sweep, dsu
Can you post a generic solution which can be used in any language? I got the intuition of what I need to do but couldn't figure out how to code it. Once I saw you are using a STL for cpp I just stopped watching.
牛逼