⬅ Previous Topic
Find Majority Element in Array (more than n/2 times)Next Topic ⮕
Maximum Subarray Sum using Kadane's Algorithm⬅ Previous Topic
Find Majority Element in Array (more than n/2 times)Next Topic ⮕
Maximum Subarray Sum using Kadane's AlgorithmTopic Contents
Given an integer array arr
, your task is to find all elements that appear more than ⌊n/3⌋
times in the array, where n
is the size of the array.
2
such elements in any array.If no such element exists, return an empty list.
arr
of size n
.candidate1
and candidate2
and their counts to 0.candidate1
, increment count1
.candidate2
, increment count2
.count1
is 0, set candidate1
to current element and count1
to 1.count2
is 0, set candidate2
to current element and count2
to 1.count1
and count2
.n/3
times.def majority_elements(arr):
if not arr:
return []
candidate1 = candidate2 = None
count1 = count2 = 0
for num in arr:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
elif count1 == 0:
candidate1 = num
count1 = 1
elif count2 == 0:
candidate2 = num
count2 = 1
else:
count1 -= 1
count2 -= 1
result = []
for candidate in [candidate1, candidate2]:
if arr.count(candidate) > len(arr) // 3:
result.append(candidate)
return result
# Sample Input
arr = [3,2,3]
print("Majority Elements:", majority_elements(arr))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | The array is traversed twice: once for candidate selection and once for verification, both in linear time. |
Average Case | O(n) | Regardless of the input distribution, both candidate identification and validation phases take linear time. |
Worst Case | O(n) | Even in the worst-case (e.g., all elements are different), both passes still involve scanning the entire array. |
O(1)
Explanation: Only a fixed number of variables are used (two candidates and their counts), independent of the input size.
⬅ Previous Topic
Find Majority Element in Array (more than n/2 times)Next Topic ⮕
Maximum Subarray Sum using Kadane's AlgorithmYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.