Majority Element

🏠 ⬅️ ➡️

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3] Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2] Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer, dimension(n) :: nums = (/ 3, 2, 3 /)
    integer :: i

    write (*, '(A)') 'Expected: 3'
    write (*, '(A)') 'Actual: ', majority_element(nums)

contains

    function majority_element(nums) result(majority)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer :: majority
        integer :: count

        do i = 1, size(nums)
            count = 0
            do j = 1, size(nums)
                if (nums(i) == nums(j)) then
                    count = count + 1
                end if
            end do
            if (count > size(nums)/2) then
                majority = nums(i)
                exit
            end if
        end do
    end function majority_element

end program main
❌ Compiled
❌ Executed
❌ Correct 
module majority_element

implicit none

contains

function majority_element(nums) result(majority)

! Given an array `nums` of size `n`, return the majority element.
! The majority element is the element that appears more than `⌊n / 2⌋` times.
! You may assume that the majority element always exists in the array.

integer, intent(in) :: nums(:)
integer :: majority

! Edge case: If the array has only one element, return that element.
if (size(nums) == 1) then
    majority = nums(1)
    return
end if

! Initialize the count for the first element as 1.
integer :: count = 1

! Iterate over the rest of the elements.
do i = 2, size(nums)
    ! If the current element is the same as the previous element, increment the count.
    if (nums(i) == nums(i-1)) then
        count = count + 1
    ! Otherwise, decrement the count.
    else
        count = count - 1
    end if

    ! If the count becomes zero, the current element is no longer the majority element.
    if (count == 0) exit
end do

! Return the majority element.
majority = nums(i)

end function majority_element

end module majority_element

program test_majority_element

use majority_element

implicit none

! Test case 1:
! Given an array `nums` of size `n`, return the majority element.
! The majority element is the element that appears more than `⌊n / 2⌋` times.
! You may assume that the majority element always exists in the array.

integer, parameter :: n = 3
integer, parameter :: nums(n) = [3, 2, 3]
integer :: majority

majority = majority_element(nums)

if (majority /= 3) then
    write (*,*) "Test case 1 failed. Expected: 3, Actual:", majority
    stop 1
end if

! Test case 2:
! Given an array `nums` of size `n`, return the majority element.
! The majority element is the element that appears more than `⌊n / 2⌋` times.
! You may assume that the majority element always exists in the array.

n = 8
nums = [2, 2, 1, 1, 1, 2, 2]

majority = majority_element(nums)

if (majority /= 2) then
    write (*,*) "Test case 2 failed. Expected: 2, Actual:", majority
    stop 1
end if

! Test case 3:
! Given an array `nums` of size `n`, return the majority element.
! The majority element is the element that appears more than `⌊n / 2⌋` times.
! You may assume that the majority element always exists in the array.

n = 9
nums = [3, 2, 3, 2, 2, 2, 2, 2]

majority = majority_element(nums)

if (majority /= 2) then
    write (*,*) "Test case 3 failed. Expected: 2, Actual:", majority
    stop 1
end if

! Test case 4:
! Given an array `nums` of size `n`, return the majority element.
! The majority element is the element that appears more than `⌊n / 2⌋` times.
! You may assume that the majority element always exists in the array.

n = 10
nums = [2, 2, 2, 1, 1, 1, 1, 2, 2]

majority = majority_element(nums)

if (majority /= 2) then
    write (*,*) "Test case 4 failed. Expected: 2, Actual:", majority
    stop 1
end if

! Test case 5:
! Given an array `nums` of size `n`, return the majority element.
! The majority element is the element that appears more than
🌐 Data from online sources 
def majority_element(nums):
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        count += (num == candidate) - (num != candidate)

    return candidate

The algorithm used here is called the Boyer-Moore Majority Vote algorithm. It works by initializing a candidate element and a count. Then, we iterate through the given array. If the count is 0, we set the candidate to the current element in the array. Then we update the count by adding 1 if the current element is equal to the candidate, or subtracting 1 otherwise. At the end of the iteration, the candidate will have the majority element.

The algorithm works because if there is a majority element, it will always appear more than the sum of all other elements, so the count will not be 0 at the end.

🌐 Data from online sources 
int majorityElement(vector<int>& nums) {
    int count = 0;
    int candidate;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

The algorithm used here is called the Boyer-Moore Majority Vote algorithm. It works by initializing a candidate element and a count. Then, we iterate through the given array. If the count is 0, we set the candidate to the current element in the array. Then we update the count by adding 1 if the current element is equal to the candidate, or subtracting 1 otherwise. At the end of the iteration, the candidate will have the majority element.

The algorithm works because if there is a majority element, it will always appear more than the sum of all other elements, so the count will not be 0 at the end.