Practice/Microsoft/Leetcode 169. Majority Element

Leetcode 169. Majority Element

CodingMust

Problem

You are given an array of integers where one element appears more frequently than all others combined. Specifically, there exists an element that appears more than ⌊n/2⌋ times, where n is the length of the array. Your task is to identify and return this dominant element.

You are guaranteed that such an element always exists in the input array.

Requirements

1. Return the integer value that appears more than half the time in the array
2. The solution should handle arrays of any length (minimum length is 1)
3. Optimize for both time and space efficiency

Constraints

• 1 ≤ array length ≤ 50,000
• -10^9 ≤ array[i] ≤ 10^9
• A dominant element is guaranteed to exist
• Target time complexity: O(n)
• Target space complexity: O(1)

Examples

Example 1:

Input: [3, 3, 4, 2, 3, 3, 3] Output: 3 Explanation: The element 3 appears 5 times in an array of length 7. Since 5 > 7/2, element 3 is dominant.

Example 2:

Input: [1] Output: 1 Explanation: In a single-element array, that element is always dominant.

Example 3:

Input: [2, 2, 1, 1, 1, 2, 2] Output: 2 Explanation: Element 2 appears 4 times and element 1 appears 3 times. Since 4 > 7/2, element 2 is dominant.