Maximum Occurred Integer in N Ranges | DSA | Programming Tutorials | GeeksforGeeks

Our courses :
practice.geeks...
This video is contributed by Rahul Singla
Please Like, Comment, and Share the Video among your friends.
Install our Android App:
play.google.co...
If you wish, translate into the local language and help us reach millions of other geeks:
www.youtube.com...
Follow us on Facebook:
/ gfgvideos
And Twitter:
/ gfgvideos
Also, Subscribe if you haven't already! :)

[@fxexile]

By far the best explanation I found, i even remember byhearting this question lol

[@adityadhikle9473]

Could'nt understand the solution by reading. But after watching this video I understood it. Cheers!!!

[@shaneahmad2598]

intuition??

[@KishanSingh-vc3re]

Someone in the comment explained the best way possible. Check that out

[@rajverma1703]

comment the explaination here brother

[@kashishverma6276]

I didn't understand logic behind the last method..Can someone explain?

[@SuperPabbs]

By marking only the start and end+1 element in a range with [1 and -1],
all the frequencies between the ranges are considered as 1 for that particular range.
i.e when you take a prefix sum(for 1 particular range), the element's frequency between the the min and max of a range is 1.
Now for the next range, when you mark the range's start and end element as 1 and -1(1+max-range number)
and if it overlaps with the previous range at some point,
say [1-5] 1 2 3 4 5 and [4-8] 4 5 6 7 8, the overlapped frequencies look like:
* [0 1 1 1 1 1 0 0 0 0]----for(1-5)
* [0 0 0 0 1 1 1 1 1 0]----for(4-8)
* 0 1 2 3 4 5 6 7 8 9
* If we add the frequencies:
* [0 1 1 1 2 2 1 1 1 0]-----------(1)
*
* OR
*
other way of seeing it is:
* 0 1 2 3 4 5 6 7 8 9
* [ 1 1 -1 -1]------- gaps are 0, because it is an int[]
* 4 and 5 overlap above.
* If we take a prefix sum
* 0 1 2 3 4 5 6 7 8 9
* [0 1 1 1 2 2 1 1 1 0]-----------(2)
*
* As we can see, (1) and (2) yield same result
*
If you mark the range in the array with [1 and 1] for starting and ending number of a range, then
when you take the prefix sum, the frequency of the numbers after the 'max-range' number
will also be positive.
That is why to avoid this, we use a -1 on the next number after max-range number,
to mark the end of the range, so that it cancels out the prefix sum to a 0 for all the numbers after the
max-range number.

[@Abhishek-Khelge]

@@SuperPabbs superb

[@sachinshet6285]

@@SuperPabbs this is the best explanation available for this problem in internet

[@mdhasib4641]

@@SuperPabbs Thank you so much........

[@Masti_Mjaak]

@@SuperPabbs bhai boht achee se smjhaya hai tumne...

[@motivity22]

kitna bakwass explanation hai..10 minutes brute samjhaya hai ,,which is very obvious that anyone could understand.
optimal 3 mint me samjhaya jo no one could understand even he himself doesnt know .
Learn first before leading man.

[@anuragC819]

can someone explain how prefix sum is recording the frequencies?

[@kashishverma6276]

I didn't understand logic behind the last method..Can someone explain?

[@vinayak186f3]

Would there be any problem
8:27
1.if we initialise the array with size = max element+1 in R instead of 10^6 ?
12:20
2.if we label LBs and UBs as 1 and -1 respectively , then put non zero element in queue and extract the index of first element whose for which value in queue changes from 1 to -1 .
Plz clarify .

[@adheeshmishra7882]

its even better

[@omkark7118]

@vinayak it should be maxx+2 or else it throw arrayoutofbound exception

[@Abhishek-Khelge]

thanks gfg

[@Jyotigupta-vs4mz]

Great Explanation, for anyone who didn't get it first do prefix sum problem

[@ujjwalkumar5596]

very well and clearly xplained ..I was in doubt why we are taking arr[ L[ i ] ]++ and then decrementing the arr[ R[ i ] +1]-- .But now it's clear thanks to u and GFG for clearing the doubts

[@aditichandra5049]

So nicely explained.......thank you so much :D

[@m.s.nabhiram1532]

Thanks gfg

[@siddharthsharma2373]

Poor. Delete the video

[@anushkamishra8865]

thankyou so much, your easy explanation made me solve the question i was stuck in.

[@meme-ku1vs]

thanks

[@kashishverma6276]

I didn't understand logic behind the last method..Can someone explain?

[@Ayush-ry1el]

Yes,
Here we put 1 to know that starting of range, and -1 to know ending of range
After that start prefix sum to calculate occurrence in range