Majority Element II — Divide and Conquer Approach

Problem Description:

Given an array arr[] consisting of N integers, the task is to find all the array elements which occurs more than floor (n/3) times.

Input: arr[] = {5, 3, 5}
Output: 5
Explanation:
The frequency of 5 is 2, which is more than N/3(3/3 = 1).

Input: arr[] = {7, 7, 7, 3, 4, 4, 4, 5}
Output: 4 7
Explanation:
The frequency of 7 and 4 in the array is 3, which is more than N/3( 8/3 = 2).

Algorithm- To solve the problem, the idea is to use Divide and Conquer technique. Follow the steps below to solve the problem:

Step 1: Initialize a function majorityElement() that will return the count of majority element in the array from any index left to right.

Step 2: Divide the given array arr[] into two halves and repeatedly pass it to the function majorityElement().

Step 3: Initialize low and high as 0 and (N — 1) respectively.

Step 4: Compute the majority element using the following steps:

a. If low = high: Return arr[low] as the majority element.

b. Find the middle index, say mid(= (low + high)/2).

c. Recursively call for both the left and right subarrays as majorityElement(arr, low, mid) and majorityElement(arr, mid + 1, high).

d. After completing the above steps, merge both the subarrays and return the majority element.

Step 5: Whenever the required majority element is found, append it to the resultant list.

Step 6: Print all the majority elements stored in the list.

Time Complexity: O(N*log N)
Auxiliary Space: O(log N)

Below is the Code Implementation:

Thanks for reading, Hit a clap if you liked it.

Happy Coding!