COUNT INVERSIONS in an ARRAY | Leetcode | C++ | Java | Brute-Optimal
Вставка
- Опубліковано 19 вер 2024
- Please watch the new video which covers it in more depth, and also prints it: • Count Inversions in an...
Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures on the entire SDE sheet.. (bit.ly/takeUfo...) ..
✅Entire Series: • Two Sum Problem | Leet...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: practice.geeks...
Problem Link: www.geeksforge...
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
Striver's Linkedin Profile: / rajarvp
Instagram: / striver_79
Connect with us: t.me/Competiti... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
Please watch the new video which covers it in more depth, and also prints it: ua-cam.com/video/AseUmwVNaoY/v-deo.html
Understood or nott? am waiting in the comment section ;)
.
Check me out at Instagram: instagram.com/striver_79/
.
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Understood
Understood
Hey u forgot to upload link to this video on sde sheet....
No 🥺
Understoood
180 questions form sde sheet with striver's solution>>> 1000 self practice questions , you get to learn so many tricks and concepts with in each question. the key is to not fast forward the question. give each question its deserving time. that's all then striver's sheet is enough to you ! thank you dude!
i sincerely feel that this problem should not be marked as medium level as its extremely difficult to figure out this answer in an interview if not solved previously.
Yes I was stuck for whole day literally then came here😢
Not at all possible to figure out this solution unless you are genius 😃
Maine to phele kiya tha ye to jb dubara kiya after months nahi hua.😔😔
@@ritikashishodia675 This is very normal 😂
For this type of problem, you should make a note and revise weekly
Sir you are really a motivation , after so much of busy schedule your are still selflessly helping us in every way (hats off to you) . I wait the whole day just for your video and only after watching and learning the concept I sleep. Thank you so much sir
Yashi Srivastava glat that you wait, this things keeps me motivated!!
The alpha rule : never lose the concentration while watching striver's video . Best explanation
Highly agree with you 👍🏻🙌🏻
Seriously, this guy is Awesome. but its also true... you can't doze off for a single bit. If you do then rewind ...
this question is very interesting one should try to solve with all approches merge sort, fenwick and trie
Great Explanation!
One more thing if anyone is implementing it then the invertion count will increase by mid - i + 1
@Anand Pandey As you are calling merge() function with 'mid' as as the argument..you have to write " mid- i + 1"
But the In video...
He is calling as merge(left, mid+1, right)
Why.? Can you explain.
@Anand Pandey why we need to add 1 ? Can you explain
You Speak So Clearly!
Great Video Quality and Awesome Explaination!!
You are so hardworking man!!
I just look up to this✨
Truly each and every word you speak is in align with the question's essence and explanation 1 minute apart and I need to watch the video again. Its a thorough explanation. Wonderful!!!
Happy Teachers Day :)
Thanks for such a great content.
UNDERSTOOD... !!!
Thanks striver for the video... :)
Solution in javascript
function merge(left, right, obj) {
let result = [];
let l = 0;
let r = 0;
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
result.push(left[l++]);
} else {
obj.count++; // this is one pair as a[i]>a[j]
obj.count += left.slice(l + 1).length; // if left[l]>left[r], and left array is sorted in ascending order, then all elements to to the right also can be pair
result.push(right[r++]);
}
}
return [...result, ...left.slice(l), ...right.slice(r)];
}
function mergeSort(arr, obj) {
const length = arr.length;
if (length < 2) return arr;
let midPoint = Math.floor(length / 2);
const left = arr.slice(0, midPoint);
const right = arr.slice(midPoint);
return merge(mergeSort(left, obj), mergeSort(right, obj), obj);
}
function countInversion(arr) {
const obj = { count: 0 };
const mergedArr = mergeSort(arr, obj);
return obj.count;
}
Merge-Sort with small modification :
void merge(int l1, int h1, int l2, int h2, vector&nums, int &count)
{
int n1 = h1 - l1 + 1;
int n2 = h2 - l2 + 1;
vectora(n1), b(n2), c(n1 + n2);
for (int i = 0; i < n1; i++)
a[i] = nums[l1 + i];
for (int i = 0; i < n2; i++)
b[i] = nums[l2 + i];
int i = 0, j = 0, k = 0;
while (i < n1 and j < n2)
{
if (a[i] l)
{
int mid = l + (h - l) / 2;
merge_sort(l, mid, nums, count);
merge_sort(mid + 1, h, nums, count);
merge(l, mid, mid + 1, h, nums, count);
}
}
I really appreciate you explaining the prerequisite too for the question.
tum dhanush fan ko kya ?
I am already done this question but after that i am loving to see your solution video its helps us to how we should explain our solution in front of interviewer
thanx..
Thanks! Cheers!!
Nice explanation, I would love to see more videos on critical questions
Thank You very much for providing this video.........👍👍👍👍👍👍
Striver, i make sure i like and comment on every video that i watch. I am learning a lot from your videos.
12:22 I guess there should by said number of elements to the right of the 'i' not 'mid' so the number of elements from left that the right element needed to jump over it. And this is what Striver said here 12:27 basically :)
11:56 K should not be set to zero, as we won't to have indexes in temp as in original arr.
13:01 Do we rally need that copying for anything?
Love to discuss with myself :) but yeah we really need that copying and by saying that K should not be zero I've automatically confirmed that it's needed :)
@@krisnerdscave394 yes, Thank you for the first statement, I got confused then this helped me to clarify.
amazing explanation, thank you for your efforts:)
your diagram had made me reailze the core part of the solution.very nice explanatio
Thank you so much bro!!!!!
Great work bro, please never stop these explanation videos 💯💯
Amazingly taught the concept. Thank you so much!!
Hey striver I have one suggestion for placement series U could add 3 similar ques for practice in each vdo of placement series starting from Day -1 ...
I am not sure i am right or wrong plzz tell striver is it correct or not bas man me kya isliye suggest kar diye .
Plzz reply #striver 🤔
Bro when you solve these questions on leetcode then leetcode suggest similar questions , just do one or two from the suggestions maybe .
@@jayeshgupta8618 uske liye leetcode premium lena padega kya ????
@@SurajVerma-lx6ik no
@@sasiraj1594 ok
A small tip for those who are watching this for the first time
-understand merge sort properly before jumping into this
Awesome content shows how good preparation it needs and you nail every time .
Happy teachers day ʕ´•ᴥ•`ʔ
The Struggle Between Sort and Shot.Very Evident😛.
Great Explaination.Understood.
bolo aunty tau kya
Hi striver meet gandhi , here again revising few tough code , i think there is a mistake wen u are doing inv_count =inv_count +(mid-1) ;
U are telling this for right side of array but ideally we are counting from mid to left (i.e. i) . I think it is left right do correct asap plz if wrong .
I think line number 28 should be inv_count = inv_count + mid - i+1;
Yes that was the doubt which i was searching for in the comment section
@Anand Pandey bro can you tell me whats wrong with the below code. Just ignore as i am not maintaining the temp array and just looking for inv_count. Thanks in advance
Code ->
long long merge(long long arr[], long long l, long long mid, long long r){
long long i = l;
long long j = mid + 1;
long long inv_count = 0;
while(i
yep, i had the same doubt
Bhai bahut bdiya explain krte..
Fully understood..
Thanks! Cheers :)
Yo
CAME UP WITH MY OWN SOLUTION
Checks from back of array and maintains a stack of Smaller elements, if larger count is incremented
Its like the naive approach but optimised
class Solution
{
// arr[]: Input Array
// N : Size of the Array arr[]
//Function to count inversions in the array.
static long inversionCount(long arr[], long N)
{
long count=0;
int flag=0;
ArrayListal=new ArrayList();
al.add(arr[(int)N-1]);
for(int i=(int)N-1;i>=0;i--){
if(arr[i]
Very interesting question once you practice it
why not inv_count=mid-i+1 bcz both i and mid are inclusive
javascript solution
function mergeSortAndCount(arr) {
let count = 0;
helper(arr);
return count;
function helper(nums) {
if (nums.length right[rightIndex]) {
count += left.length - leftIndex;
rightIndex++;
} else {
leftIndex++;
}
}
leftIndex = 0;
rightIndex = 0;
let sortedArray = [];
while (leftIndex < left.length || rightIndex < right.length) {
if (leftIndex >= left.length || left[leftIndex] > right[rightIndex]) {
sortedArray.push(right[rightIndex]);
rightIndex++;
} else {
sortedArray.push(left[leftIndex]);
leftIndex++;
}
}
return sortedArray;
}
}
The way you teach, how can anyone one not understand 🔥🙏
just the way i did.
Can we use ordered set in interviews, this ques is much easier with ordered set
Nice video totally understood optimal approach
Simple code in java
public class Solution {
static long count = 0;
public static long getInversions(long arr[], int n) {
mergeSort(arr, 0, arr.length - 1);
return count;
}
public static long[] mergeSort(long[] arr, int lo, int hi){
if(lo == hi){
long[] base = new long[1];
base[0] = arr[lo];
return base;
}
int mid = (lo + hi) / 2;
long[] left = mergeSort(arr, lo, mid);
long[] right = mergeSort(arr, mid + 1, hi);
long[] merge = merge2Sort(left, right);
return merge;
}
public static long[] merge2Sort(long[] left, long[] right){
int i = 0;
int j = 0;
int k = 0;
long[] merge = new long[left.length + right.length];
while(i < left.length && j < right.length){
if(left[i]
thx bro actually i did merge sort like this,but the video showed a different method,which after 45 min of debugging I understood😅
I think we can use binary search(lower_bound stl) which would take O(nlogn)
No pro it will not.. you will have to use set, so after lower bound to find number of elements you need to subtract the iterator which will take n time making it total of n^2
@@takeUforward yeah got it thanx
@@takeUforward is there any other method to solve this problem using hash/set/maps?
Hey Striver!
was wondering if we could do it by Priority Queue. I mean we can but then we would need an extra storage for storing the popped values and an additional complexity to push back to pq. What do you suggest?
Yeah but wouldn't it be O(n^2).For every element you traversing the entire queue in worst case.
@@prashantbisht2219 yup
Following from bangladesh..😇😇
Would you kindly explain the Fenwick tree method?
It would have been much much clearer if you had modified the code of merge sort from gfg because using temp as parameter is confusing and the gfg article from where you have taken the code is also not easy to understand.
I did not want to modify because a bunch kf students follow gfg 😅
Please,
continue with this series closely following your videos.
You help us a lot!!!
First video I used to watch at ×0.75
better than gfg's explaination
Such a easy way of explanation
ThanKs @ striver
Hey Stiver,I can easily solve that question using fenwick tree data structure.But what about if maximum element in array can be upto 10^9.How to solve that using fenwick tree ? Or we can't do incase of large elements of array?
this can be done by compressing the array because size of array is 10^5 .For example {10^8,10^9} can be compressed as {1,2}
Bro can u tell me from where you learned Fenwick tree. There are not many good videos about Fenwick tree in UA-cam
@@adityasai550 ua-cam.com/video/9uaXG62Y8Uw/v-deo.html
Segmentation fault: (Help !!!)
long long int inversionCount(long long arr[], long long N)
{
if(N==1)
return 0;
long long mid = (N-1)/2;
long long s1=mid+1;
long long left[s1];
for(int i=0;i
Kitna accha samjhaate ho 🥲🥲💋
GFG SOLUTION: C++
Public:
long long int mergeIt(long long arr[], long long temp[], long long left, long long mid, long long right)
{
long long inv_count=0;
long long i=left;
long long j =mid;
long long k =left;
while((i
Great explanation sir
Fabulous solution!
class Solution{
public:
// arr[]: Input Array
// N : Size of the Array arr[]
// Function to count inversions in the array.
long long getinversioncount(long long a[],long long start,long long end,long long mid)
{
long long i=0,j=0,k=start,count=0;
long long n1=mid-start+1;
long long n2=end-mid;
long long L[n1], R[n2];
for(long long z=0;z
Thanks For Your Efforts
What do you think about a "binary indexed tree" with O(N) ?!?!?!?!?!
great explanation : D
So can we say that the crux is doing inversion is basically sorting ? and merge sort is the most appropriate one
thanks for the explanation
Awesome explanation!
This is awesome ❤
why can't we solve this with gap method??? please reply.......
Legends are watching this during online class🤣🤣 cos your way of solving a problem is so addictive
Haha, what if your prof sees this comment 🤣
@@takeUforward then he will reward me with great internal marks, you know what i mean🤪🤣🤣
Great Explanation as always! Thanks anna.😅
MergeSort approach : 3:04
Can you please the solution using BIT, I saw it on leetcode but I am not so familiar to using BIT except for the range sums. It would be very helpful if we could learn some applications of BIT.
whats the name of this problem on leetcode?
WAH KYA SCENE HAI!!
Amazing explanations :)
Awesome Explanation
Thank you sir
Can you explain why you are using -> (mid-i) isnt it supposed to be (mid-i+1), but why your code works?
Yeah, my code worked with mid-i+1 as well
Note: Please start solving this SDE sheet if and only if you have studied DSA atleast twice or else you won't be able to understand even through the video solution of the problem.
Thank you very much👍
tech dose has expained in a better way
Really helpful !
understood nicely 1-Aug-2022
How can i think that, it will be solve using merge sort ??
understood clearly..
can we just move in the array and use stl sort to sort the right half and then compare each element to the one on the right and if its greater we are good to go,
however after every sort i want to my array back to normal, is there a way around this?
Bro this approach sounds more brute than the brute force itself
@@nuclearnadal69 my programming 4 months back was "brutal" lol 😂😂
His voice reminds of Pawri
Pawri ho rhi hai bali ya kuch aur
Your sde sheet link for this video is not working, directing the spoj
This video is helpful ❤️
Thank you
Happy teachers day 🌹
Brilliant !!!
We can do this in 4-5 lines using PBDS bt obv. they will not allow us to use PBDS.
why do we need temp array? I'm not getting in what way will the existing array will be modified. Please Explain
U can watch merge sort it that u need a array so that you can basically store your elements and find comparison
awesome man
I have been thinking of an alternate easy approach.
Let's say I sort the array in nlogn,
then count every element inversion count using O(N) approach where we just count the number of elements on the right side of the array.
total TC= nlogn + n = nlogn
Wouldnt this be an easier solution?
Please correct me if this is wrong.
can't sort the array
No its wrong bcoz it will count that inversions also which was not a inversion in real array . It will work if array is sorted in descending order, then only your approach will follow good. Hope you understand. If have any doubt let me know
can we do this without using temp array??
Yes, you can. Use the concept of shell sort.
thanks bro u r best
whats wrong in the code below?
#include
using namespace std;
int merge(vector& nums, int start, int mid, int end){
int count = 0;
int n1 = mid - start + 1;
int n2 = end - mid;
vector leftArray(n1);
vector rightArray(n2);
for(int i = 0; i < n1; i++){
leftArray[i] = nums[start + i];
}
for(int i = 0; i < n2; i++){
rightArray[i] = nums[mid + 1 + i];
}
int i = 0, j = 0, k = start;
while(i < n1 && j < n2){
if(leftArray[i] = end) return 0;
int count = 0;
int mid = (start + end) / 2;
count += mergeSort(nums, start, mid);
count += mergeSort(nums, mid + 1, end);
count += merge(nums, start, mid, end);
return count;
}
int countInversions(vector& nums) {
return mergeSort(nums, 0, nums.size() - 1);
//return nums;
}
I tried to think, when i saw nlogn, heapsort, merge sort came to my mind.
my mind tried to think, but could not develop intuition for O(nlogn) :(
Although, brute force is easy for me, but how do i optimise?
no one can come up with the optimal soln until and unless you have already solved it before.
@@farazahmed7 no after 1 ye if practice now i can see why merge sort is the key to solve this problem. We can make use of merge sort in order to find the number of inversions optimally
What is the thought process behind the Merge sort?
Awesome man....
void merge(long long int *ans,int start,int end,long long arr[])
{
int mid=(start+end)/2;
int len1=mid-start+1;
int len2=end-mid;
long long int first[len1];
long long int second[len2];
int k=start;
for(int i=0;i
Sometimes u have a fake English accent & that's funny lol...btw thanks for vid, plz show some competitive programming u used in your amazon internship sirji :)
no i try to make u laugh by making it a musical tone XD so that its not serious all the time huhuhaha
@@takeUforward Cool still bro plz tell which datastructures or algo or competitive programming strategies u used in ur Internships ... It would be cool