Check If a Number Is a Majority Element in a Sorted Array

Asked atZZupee
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element, or false otherwise.

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

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

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

Input: nums = [3,3,3,3,3,5,5,5,5,5], target = 3

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

cpp

class Solution {
public:
    bool isMajorityElement(vector<int>& nums, int target) {
        // Your code goes here
    }
};

java

class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        // Your code goes here
    }
}

python

class Solution:
    def isMajorityElement(self, nums, target):
        # Your code goes here

javascript

/**
 * @param {number[]} nums - Sorted array of numbers
 * @param {number} target - Target number to check
 * @return {boolean} - Whether target is a majority element
 */
function isMajorityElement(nums, target) {
    // Your code goes here
}

csharp

public class Solution {
    public bool IsMajorityElement(int[] nums, int target) {
        // Your code goes here
    }
}

go

func isMajorityElement(nums []int, target int) bool {

}
Stuck? Show a way to structure it+
  1. 01Find the first target occurrence with lower bound.
  2. 02Check that target exists.
  3. 03Compare position first+n/2 against target.
  4. 04Return whether it remains target.

Reference answer

Then expect these follow-ups

  • How would you return the exact count?

    Tests: upper bound

  • What changes for a threshold other than half?

    Tests: generalization

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.
  • Senior Software Engineer -.NET

    Tyler Technologies · Annapolis, Maryland

  • Software Development Engineer II

    SaaS Labs · Bengaluru, Karnataka, India

  • Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)

    Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question