Count occurrences of a number in a sorted array with duplicates using Binary Search

[@mycodeschool]

Hi Kulamani, Quick sort does not need any extra memory while merge sort needs extra memory proportional to the size of array to be sorted. That's why quick sort is preferred over merge sort. But there may be scenarios where merge sort would be preferred. It all depends upon the scenario.

[@AnujGupta-ee8dx]

These videos are very helpful and informative. The guy explains wonderfully without rushing into anything. Examples are good and the subtitles are accurate. Thank you mycodeschool for coming out with such good videos. Kudos to you and your team.

[@doingsneakypeakylike]

thanks! you're better than most professors at explaining these :)

[@rohankucheriya]

I thought I'd write the function twice for first and last element. But the introduction to flag boolean was a good idea. Now calling twice would help. Awesome

[@alokporwal007]

the way you speak is fantanstic!Kudos.

[@ujeshnada7281]

One of the best teacher in programming.

[@MohamedKhafaga8]

You really are a great teacher

[@ashitbarandas8879]

This is pure gold

[@Anilkumar-xu8vj]

.alot informative :) perfect explanation of every topic !! hats off for your recommendable work .. i found these videos best !!! amongst all cyber tutorials...

[@sofianehammami4869]

Thank you mycodeschool for these videos !

[@sanjoychattopadhyay3454]

You are the best , sir

[@GOWRISANKARAS]

Thanks as always for clear explanation.

[@vijayendrasdm]

very clear explanation. thanks

[@codingandmathvideos]

You forgot to check if lastIndex == -1 (element appears only once). You can't return last-first+1 if last is -1. In that case you should return 1 since first index was not -1.

[@mrmca1]

if firstIndex is -1, it means element is not present so whats the point of checking lastIndex?

[@ven398]

iRock If first index is not -1 and the last index is -1 then the ans would be wrong is what coding math is trying to say...

[@ARUNRAJ-11]

Venkatesh Narayanan: How can this happen? If first index is not -1, it means the array has that particular element. So last index can never be -1, if first index is not -1.

[@amithapa1994]

1,3,3,4,5,5,5,5 the user inputs the value 4. the first occurrence of 4 would be index 3 and the last occurrence will also be 3 Hence, the value will be [ first occurrence - last occurrence + 1] ---> (3-3+1) = 1 the number 4 occurs only once in the given array :D

[@anchitbhushan6172]

public static int Count(int[] a, int low, int high, int key){ if(low>high) return 0; int mid = low+(high-low)/2; if(a[mid]==key) return 1+Count(a, low, mid-1, key)+Count(a, mid+1, high, key); if(a[mid]>key) return Count(a, low, mid-1, key); else return Count(a, mid+1, high, key); } This is the recursive way to calculate number of occurence which he was talking at @3:02, but still it has O(n) worst case complexity

[@LakshmikanthAyyadevara]

#another algorithm of finding a=[1,1,1,1,1,1,1,1,1,1,2] l=len(a) count=1 y=int(input('select an integer')) for i in range(l): if a[i]==y or a[l-i-1]==y: if a[i]==y and a[l-i-1]==y: print(l-1-2*i+count) break elif a[i]==y: if a[i]!=a[i+1]: print(count) break count+=1 elif a[l-i-1]==y: if a[l-i-1]!=a[l-i-2]: print(count) break count+=1 Sir i like your process a lot can you check this algorithm and mention which one i better one sir

[@hengamehoseini2666]

Thanks for clear explanations

[@dikshagupta1371]

#include include this header file to use BOOL .

[@bhavyapatel6306]

Awesome, thank you, this helped me a lot.

[@Stoic623]

Below code works for me. Note element passed should be present else returns 1 int countElement(int[] arr, int low, int high, int element) { while (low

[@kulamanisahoo4785]

am a Big Fan of U r Video Series...Simple CLear and to the Point ina ll Sorting Video's..But it will be Good If you compare the Time and space complexity for all the sorting in one Video...Also want to Know why Quick Sort not Merger sort?

[@urur2000]

easy to understand. thank you so much

[@MichaelSalo]

The +1 is what would trip me in an interview. I would be thinking, I just need the difference.

[@adityaroshanpatro9861]

can u explain the "+1" in return (last -first +1)

[@saichaitanyanallamala117]

@@adityaroshanpatro9861 lets see if you want to count number of ones in {1,1,2,3,3} the indexes of ones are 0,1 if you subtract you will only get 1,but there are two 1s.To avoid this you add +1.

[@mutian7168]

This is awesome!

[@gregmccadden2147]

Thank you so much!!!! Is it possible to implement an algorithm like this that searches for the 1st and last occurrence of a duplicate number within an UNSORTED vector? (C++ preferably).

[@suyashsingh4338]

You can sort the vector using the STL sort function first sort(vec.begin(),vec.end()) O(nlogn) is the time complexity of this function

[@veerendrashukla]

Very nice!

[@shubhamladha5426]

Thank you

[@ahmidahmid9303]

this algorithm have a major bug if there only 1 element in the array running first and last will return the same index and creates a false count there must be a case if (first==last)return 1; or when searching for the last duplicate pass the array partition from last+1 to array.length-1

[@AndriyByalyk]

i've done it with xor.

[@alihaydargubatov2790]

How did you do that? I know that with xor you can find one unique element in array but don't know how to count given element. And what complexity your method has?

[@findMeOnYoutube350]

Андрій Б'ялик how would you solve with xor ..

[@nazmulislam3348]

Thanks 😍😍🥰🥰🥰

[@andrewstauble4324]

THANK YOU.

[@aleksandarmiladinovic594]

Hi. I have a question to find in unsorted list of integers 2nd anth 5th number six in Array and calculate the sum(+) of all the numbers in between those two sixes. If you could help me that would be great.Thank you

[@samijames9986]

The search for First and Last sections of this code look linear to me (O(n) and not O(Log(n)) , because you're decrementing/incrementing the boundary by 1 at each iteration

[@thanakornkunta9236]

He increases/decreases the "boundary", so that by itself is the basis of binary search (eliminating the data to search by half in every iteration). So it's O(log(n))

[@adityaroshanpatro9861]

can u explain the "+1" in return (last -first +1) 6:36

[@robtangled8816]

You can think about with examples: array = [1, 3, 3, 3, 3, 4, 7, 9] and x = 3; You will find element 3 four times. The first index will be 1, and the last index will be 4. last = 4; first = 1; So last-first = 3. +1 = 4. And four is the correct number of occurrences. But in the case that no occurrences are found, this type of ecuation will give you 1. Because if the findFirst and findLast functions return -1 in the scenario they don't find the element, the ecuation will be: -1 -(-1) + 1 = 1; So what I did was to place some if statments like so: function countOccurrences(array, x) { let n = array.length; let first = findFirst(array, x); let last = findLast(array, x); let occurrences = (last - first + 1) if (first === -1 || last === -1) { occurrences = 0; } return occurrences } Hope this helps. I'm just a noob, but I think this works fine.

[@kushal1]

This is all fine and well explained. But what's the intuition behind the very basis of the equation ( R - L +1). It's not straightforward to form this analysis.

[@shreevatsalamborghin]

its because of the zero based indexing....if youll look closely and test different cases it comes to abs(l-r+1)

[@kushal1]

@@shreevatsalamborghin Yep. This is coming after two months. Well equipped now with such things. Thanks anyway.

[@swathik3491]

sir can you do a lecture on prims algorithm

[@swatsolitaryma]

man I LUVV YOUU

[@xof8256]

Thanks

[@georgez9995]

how would you have it read from a txt file and give you the 10 most common numbers?

[@VikramSingh-hu2hs]

Please upload hashing tutorial also

[@sandeepkumawat4982]

he is no more with us😥 he passed away in a car accident RIP🙏

[@sunnymeska7015]

i am going to infinite loop when i am running this program please help me

[@shikha1387]

Where were you my entire life? 😫🤦

[@prasannakumarz]

hahha....he's actually hiding somewhere

[@aditya234567]

@@prasannakumarz Sad to know that this person passed away in 2014 :( you can find about him by searching for humblefool

[@kamaleshneerasa5425]

I want to check whether an array is super array or not. A SUPER ARRAY is an array which contains each element repeated its number of times. like 1224444 is asuper array because 2 is repeated twice and four is repeated 4 times. can you help me with algorithm.

[@Prashantkumar-sz2qk]

worst cast time complexity of this code will still be O(n)

[@GAURAVKUMAR-bb2xh]

In find count, we can't use else if 4:54

[@meghasyam427]

what if the duplicates are not in continuous indices in the array.....for example A[ ]={1,2,3,4,5,6,4,7,8,4,9,4,10,4}; Look at this now.. we have element 4 repeated but not continuously .....

[@avikasliwal4283]

the given array was sorted

[@ahmidahmid9303]

binary search works only on sorted data

[@richardhollon6965]

That would be a non-sorted array, which is not used in binary searches

[@balasubramaniantk4863]

if input is 4 4 4 4 and searched for 4 it will show in location 2, why?

[@Pooh__7__]

That is because 4 is the only element in your array

[@JAKdeLILLIPUT]

Why using "firstIndex + 1" when subtracting from "lastIndex"? Thank You.

[@akhileshswaroopxisrnnadbt3669]

Suppose element is present only once in array then both function will return it (let's say index is x of number).Now (last-first) will give 0 because element is occuring only once in array and hence both function will return same index.But actually we need our answer as 1 not 0 as number is one time in array,hence +1 will do the work Moreover initialize result=-1 in last_occurence function and result=0 in first_occurence function to handle not found case

[@akhileshswaroopxisrnnadbt3669]

Hope you understand

[@sumitbansal1967]

What is big O

[@reyanshmishra7676]

most of the time I get stuck at (low + high) / 2 and low + high / 2

[@RiteshKasat]

nice

[@niteshmishra4122]

what if similar elements are not in contiguous location? how will calculate count?

[@njengagathee7886]

I understand that this method works on an already sorted list, so it is guaranteed that the elements are contiguous.

[@jameskelly132]

Then the array is not sorted and you can't use binary search.

[@ahmidahmid9303]

use Arrays.sort first

[@shreevatsalamborghin]

@@ahmidahmid9303 nope that would cost tc...In that case hash map is best

[@arunsharma-tc6jv]

is bool data type supported in C ?

[@madasamym8127]

yes c supported we can declare a funtion also as bool bool funtion_name { return true or false; }

[@dikshagupta1371]

#include use this header file to use bool . it will work fine . unlike c++ , here u need to add a header file

[@svinceonal9518]

how about if float array?

[@andreykatak433]

same question

[@tahapek2411]

you catch a good point

[@emirhankoc3593]

your profile picture is fuckin awesome man omfg

[@jahidulislam-wd9jf]

help me someone

[@victormeyer4116]

what if we want to determine the number of duplicates, How do we write the code?

[@PramodRj]

Rewrite using recursion and have a flag!

[@idiotsuo2418]

Sir I'm using shipping desktop applications and import excel file in application show message Sorry this id already added duplicate value index was out of range. Must be non negative and less than size of the collection. Parameters name index

[@bipul2138]

nice