Problem

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target _is amajority element, or _falseotherwise.

A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.

Examples

Example 1:

1
2
3
4

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

Example 2:

1
2
3
4

Input: nums = [10,100,101,101], target = 101
Output: false
Explanation: The value 101 appears 2 times and the length of the array is 4.
Thus, 101 is not a majority element because 2 > 4/2 is false.

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], target <= 10^9
  • nums is sorted in non-decreasing order.

Solution

Method 1 – Binary Search for First and Last Occurrence

Intuition: Since the array is sorted, we can use binary search to efficiently find the first and last occurrence of the target. The count of the target is then last - first + 1. If this count is more than half the array’s length, the target is a majority element.

Approach:

  1. Use binary search to find the first occurrence of the target.
  2. Use binary search to find the last occurrence of the target.
  3. If the target is not found, return false.
  4. Compute the count as last - first + 1.
  5. Return true if count > n // 2, else false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    bool isMajorityElement(vector<int>& nums, int target) {
        int n = nums.size();
        int first = findFirst(nums, target);
        if (first == -1) return false;
        int last = findLast(nums, target);
        return (last - first + 1) > n / 2;
    }
    int findFirst(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) r = m - 1;
            else l = m + 1;
            if (nums[m] == target) ans = m;
        }
        return ans;
    }
    int findLast(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] <= target) l = m + 1;
            else r = m - 1;
            if (nums[m] == target) ans = m;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func isMajorityElement(nums []int, target int) bool {
    findFirst := func(nums []int, target int) int {
        l, r, ans := 0, len(nums)-1, -1
        for l <= r {
            m := l + (r-l)/2
            if nums[m] >= target {
                r = m - 1
            } else {
                l = m + 1
            }
            if nums[m] == target {
                ans = m
            }
        }
        return ans
    }
    findLast := func(nums []int, target int) int {
        l, r, ans := 0, len(nums)-1, -1
        for l <= r {
            m := l + (r-l)/2
            if nums[m] <= target {
                l = m + 1
            } else {
                r = m - 1
            }
            if nums[m] == target {
                ans = m
            }
        }
        return ans
    }
    n := len(nums)
    first := findFirst(nums, target)
    if first == -1 {
        return false
    }
    last := findLast(nums, target)
    return (last - first + 1) > n/2
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int n = nums.length;
        int first = findFirst(nums, target);
        if (first == -1) return false;
        int last = findLast(nums, target);
        return (last - first + 1) > n / 2;
    }
    private int findFirst(int[] nums, int target) {
        int l = 0, r = nums.length - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) r = m - 1;
            else l = m + 1;
            if (nums[m] == target) ans = m;
        }
        return ans;
    }
    private int findLast(int[] nums, int target) {
        int l = 0, r = nums.length - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] <= target) l = m + 1;
            else r = m - 1;
            if (nums[m] == target) ans = m;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    fun isMajorityElement(nums: IntArray, target: Int): Boolean {
        fun findFirst(nums: IntArray, target: Int): Int {
            var l = 0; var r = nums.size - 1; var ans = -1
            while (l <= r) {
                val m = l + (r - l) / 2
                if (nums[m] >= target) r = m - 1
                else l = m + 1
                if (nums[m] == target) ans = m
            }
            return ans
        }
        fun findLast(nums: IntArray, target: Int): Int {
            var l = 0; var r = nums.size - 1; var ans = -1
            while (l <= r) {
                val m = l + (r - l) / 2
                if (nums[m] <= target) l = m + 1
                else r = m - 1
                if (nums[m] == target) ans = m
            }
            return ans
        }
        val n = nums.size
        val first = findFirst(nums, target)
        if (first == -1) return false
        val last = findLast(nums, target)
        return (last - first + 1) > n / 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def isMajorityElement(self, nums: list[int], target: int) -> bool:
        def find_first(nums: list[int], target: int) -> int:
            l, r, ans = 0, len(nums) - 1, -1
            while l <= r:
                m = (l + r) // 2
                if nums[m] >= target:
                    r = m - 1
                else:
                    l = m + 1
                if nums[m] == target:
                    ans = m
            return ans
        def find_last(nums: list[int], target: int) -> int:
            l, r, ans = 0, len(nums) - 1, -1
            while l <= r:
                m = (l + r) // 2
                if nums[m] <= target:
                    l = m + 1
                else:
                    r = m - 1
                if nums[m] == target:
                    ans = m
            return ans
        n = len(nums)
        first = find_first(nums, target)
        if first == -1:
            return False
        last = find_last(nums, target)
        return (last - first + 1) > n // 2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

impl Solution {
    pub fn is_majority_element(nums: Vec<i32>, target: i32) -> bool {
        fn find_first(nums: &Vec<i32>, target: i32) -> i32 {
            let (mut l, mut r, mut ans) = (0, nums.len() as i32 - 1, -1);
            while l <= r {
                let m = l + (r - l) / 2;
                if nums[m as usize] >= target {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
                if nums[m as usize] == target {
                    ans = m;
                }
            }
            ans
        }
        fn find_last(nums: &Vec<i32>, target: i32) -> i32 {
            let (mut l, mut r, mut ans) = (0, nums.len() as i32 - 1, -1);
            while l <= r {
                let m = l + (r - l) / 2;
                if nums[m as usize] <= target {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
                if nums[m as usize] == target {
                    ans = m;
                }
            }
            ans
        }
        let n = nums.len() as i32;
        let first = find_first(&nums, target);
        if first == -1 {
            return false;
        }
        let last = find_last(&nums, target);
        (last - first + 1) > n / 2
    }
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)