Check If a Number Is Majority Element in a Sorted Array

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 110 ms)

Metric	Value
Runtime	110 ms
Memory	38.9 MB
Date	2022-02-08

Solution

public class Solution {
    public bool IsMajorityElement(int[] nums, int target) {
    int n = nums.Length;
    int first = FindFirst(nums, target);
    int targetIndex = first + n / 2;
    if (first==-1 || targetIndex >= n || nums[targetIndex] != target) return false;
    return true;
}

private static int FindFirst(int[] nums, int target)
{
    int l = 0, r = nums.Length - 1;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;

        if ((mid == 0 || target > nums[mid - 1]) && nums[mid] == target)
        {
            return mid;
        }
        else if (target > nums[mid])
        {
            l = mid + 1;
        }
        else
        {
            r = mid-1;
        }
    }
    return -1;
}
}

📜 1 more C# submission(s)

Submission (2022-02-08) — 128 ms, 38.9 MB

public class Solution {
    public bool IsMajorityElement(int[] nums, int target) {
    int n = nums.Length;
    int first = FindLast(nums, target);
    int targetIndex = first - n / 2;
    if (first==-1 || targetIndex <0 || nums[targetIndex] != target) return false;
    return true;
}

private static int FindLast(int[] nums, int target)
{
    int l = 0, r = nums.Length - 1;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;

        if ((mid == nums.Length-1 || target < nums[mid + 1]) && nums[mid] == target)
        {
            return mid;
        }
        else if (target < nums[mid])
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return -1;
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed