Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.
Example 1:
Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6
Example 2:
Input: arr = [1,1] Output: 1
Constraints:
1 <= arr.length <= 1040 <= arr[i] <= 105This approach involves scanning the array with a single pass. Given that an element occurring more than 25% will appear as a block, we can count the occurrences of an element until it changes and check the count.
For a given element arr[i], count consecutive occurrences. If it exceeds the threshold (n/4), return that element immediately.
This C program uses a for loop to iterate over the sorted array. Using a threshold of n/4, it checks for consecutive elements, increasing a count until the count exceeds the threshold, returning the element if found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as it makes a single pass through the array. Space Complexity: O(1), uses a constant amount of space.
This approach involves using binary search to take advantage of the sorted nature of the array. By checking elements at regular intervals (n/4), we can identify any elements that repeat in significant blocks more than the threshold.
Instead of scanning the entire array sequentially, we check index positions at specific intervals (n/4, n/2, 3n/4) to find the repeating element.
This binary search-based approach checks specific, equally distanced indices (n/4 positions) and determines if an element appears more than the 25% threshold by comparing element boundaries within each block.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) average on small fixed comparisons. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Linear Scan Approach | Time Complexity: O(n), as it makes a single pass through the array. Space Complexity: O(1), uses a constant amount of space. |
| Binary Search Approach | Time Complexity: O(1) average on small fixed comparisons. Space Complexity: O(1). |
Single Element in a Sorted Array - Leetcode 540 - Python • NeetCodeIO • 26,500 views views
Watch 9 more video solutions →Practice Element Appearing More Than 25% In Sorted Array with our built-in code editor and test cases.
Practice on FleetCode