169. Majority Element

Problem description

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

Intuition:

The problem asks for finding the majority element, which is the element that appears more than ⌊n/2⌋ times in the given array. Sorting the array provides an elegant solution, as the majority element will always be positioned at the middle index after sorting.

Approach:

Sort the array nums.

Find the middle index mid by dividing the length of the array by 2.

Return the element at index mid, as it is guaranteed to be the majority element.

Complexity Analysis:

Time Complexity: Sorting the array takes O(n log n) time. Finding the middle element afterward takes constant time. Therefore, the overall time complexity is dominated by the sorting step, making it O(n log n).

Space Complexity: Sorting the array in-place doesn't require any additional space. Hence, the space complexity is O(1).

Code Explanation:

The code first sorts the input array nums.

It then calculates the middle index mid by dividing the length of the array by 2.

Finally, it returns the element at index mid, which is the majority element.

This solution provides a straightforward and efficient approach to finding the majority element, with a time complexity of O(n log n) and space complexity of O(1).

Code


public class Solution {
    public int MajorityElement(int[] nums) {
        Array.Sort(nums);
        int mid = nums.Length/2;
        return nums[mid];
    }
}