Check If a Number Is Majority Element in a Sorted Array

Check If a Number Is Majority Element in a Sorted Array - 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 & Output

Example 1 — Target is Majority

$ Input: nums = [2,4,5,5,5,5,5,6,6], target = 5

› Output: true

💡 Note: Target 5 appears 5 times in array of length 9. Since 5 > 9/2 (which is 4), target 5 is a majority element.

Example 2 — Target is Not Majority

$ Input: nums = [10,100,101,101], target = 101

› Output: false

💡 Note: Target 101 appears 2 times in array of length 4. Since 2 ≤ 4/2 (which is 2), target 101 is not a majority element.

Example 3 — Target Not Found

$ Input: nums = [1,1,2,2], target = 3

› Output: false

💡 Note: Target 3 does not appear in the array, so it cannot be a majority element.

Constraints

1 ≤ nums.length ≤ 1000
-10⁹ ≤ nums[i], target ≤ 10⁹
nums is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array and target value

Count

Find occurrences of target

Check

Return count > length/2

Key Takeaway

🎯 Key Insight: Use binary search on sorted arrays to find element bounds in O(log n) time

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that since the array is sorted, we can use binary search to efficiently find the first and last occurrence of the target. Best approach is Binary Search with Time: O(log n), Space: O(1). For unsorted arrays, we'd need O(n) linear counting.

Common Approaches

Approach	Time	Space	Notes
✓ Linear Count	O(n)	O(1)	Count occurrences of target by scanning the entire array
Binary Search Bounds	O(log n)	O(1)	Find first and last occurrence using binary search, then calculate count

Linear Count — Algorithm Steps

Step 1: Initialize counter to 0
Step 2: Iterate through array and count target occurrences
Step 3: Return true if count > nums.length / 2

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with count = 0

Count

Increment count when target is found

Check

Return count > length/2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int numsSize, int target) {
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == target) {
            count++;
        }
    }
    return count > numsSize / 2;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    bool result = solution(nums, numsSize, target);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the entire array to count occurrences

✓ Linear Growth

Space Complexity

O(1)

Only using a counter variable for tracking occurrences

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler