Menu
I was asked in an interview to give an O(n) algorithm to print an element that appears more than n/2 times in an array, if there is such an element. n is the size of the array. I don't have any clue on how to do this. Can anyone help?
425
We have to find the largest/ maximum element in an array. The time complexity to solve this is linear O(N) and space compexity is O(1).
Approach: Take two variables; let's call them first and second and mark them as -∞. Iterate through the array and for each element (let's call it current), Compare it with the first and if first is less, assign the first value to second and assign current to first.
Solution Approach For the largest three elements, we will create three elements holding their values, max, max2 and max3 and set these values to arr[0]. if (arr[i] > max) -> max3 = max2, max2 = max , max = arr[i]. else if (arr[i] > max2) -> max3 = max2, max2 = arr[i].
A simple solution is to run two loops. The outer loop picks all elements one by one. The inner loop finds the frequency of the picked element and compares it with the maximum so far.
It's the Boyer's Voting algorithm.
It's also O(1) in space!.
Edit
For those complaining about the site color scheme (like me) ... here is the original paper.
53
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
