Element Appearing More Than 25 In Sorted Array - Leetcode Solution

Problem Statement:

Given a sorted array nums, there is a single element which appears more than 25% of the time.

Return that element.

Solution:

The problem can be solved efficiently in linear time using a single pass through the array. A brute-force approach would be to count the occurrences of each element, but that could take O(n^2) time.

Since the array is sorted, we can take advantage of that fact and use binary search to find the element that appears more than 25% of the time. We can find the midpoint of the array and check which half of the array the element must be in based on its frequency.

If the element appears more than 25% of the time, then it must either be in the left half of the array, the right half of the array, or the midpoint itself.

We can keep track of the current element and its frequency while iterating through the array, and if we find an element that appears more than 25% of the time, we can return it.

Pseudocode:

int frequency = n / 4; int current = nums[0]; int count = 1;

for (int i = 1; i < nums.length; i++) { if (nums[i] == current) { count++; } else { count = 1; current = nums[i]; }

if (count > frequency) {
    return current;
}

}

return current;

This algorithm will take O(n) time in the worst case, which is much better than the O(n^2) time complexity of a brute-force approach.

1