What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?
First we find the majority Element in an array :
I:e
Array : 3 5 3 3 5 3 3 7 3 5
n = 10
int count = 0 ;
int candidate = 0
Integer candidate =
null
;
int count = 0;
for
(int i = 0; i < array.length; i++) {
if
(count == 0) {
candidate = array[i];
count = 1;
continue
;
}
else
{
if
(candidate == array[i]) {
count++;
}
else
{
count--;
}
}
}
Explanation :
Iteration 1 : array[0] = 3 , candidate = 3 , count = 1 ;
Iteration 2 : array[1] = 5 , count - - , count = 0 , candidate = 3
Iteration 3 : array[2] = 3 , candidate = 3 , count = 1
iteration 4 : array[3] = 3 , candidate == array[3] // holds true , count++ , count = 2 , candidate = 3
iteration 5 : array[4] = 5, count - - , count = 1 , candidate = 3
iteration 6 : array[5] = 3 , candidate == array[5] // holds true , count ++ , count = 2 , candidate = 3
iteration 7 : array[6] = 3 , candidate == array[6] // holds true , count ++ , count = 3 , candidate = 3
iteration 8 : array[7] = 7 , count - - , count = 2 , candidate = 3
iteration 9 : array[8] = 3 , candidate == array[8] // hold true , count ++ , count = 3
Iteration 10 : array[9] = 5 , count- - , count = 2 , candidate = 3
we done out execution in which final count = 2 and candidate = 3
which mean candidate = 3 is our majority element which occurs most of the time
and this required : O(n)
Now , we have to check whether it occurs greater then n/2 times or not
count = 0;
for
(int i = 0; i < array.length; i++) {
if
(candidate == array[i]) {
count++;
}
}
return
(count > array.length / 2) ? candidate :
null
;
}
it also required : O(n)
total time complexity : O(n) + O(n) = O(n)