
Problem Statement
The task is to analyze a given integer array which is sorted in non-decreasing order. Among the values in this array, one specific integer appears with a frequency greater than 25% of the array's total length. The objective is to identify and return this integer.
Examples
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 <= 104
0 <= arr[i] <= 105
Approach and Intuition
Given that the array is already sorted in non-decreasing order, the integer that appears more than 25% of the time will appear in a contiguous block. Here's a step-by-step approach to solving the problem:
- Calculate the threshold needed to exceed 25% frequency by taking the ceiling of 𝑛/4, where 𝑛 is the length of the array.
- Iterate through the array using a pointer or index to count consecutive occurrences of each integer.
- As the count of a particular integer exceeds the threshold, that integer can be immediately returned.
- Since the array is sorted, once we move past a number, there is no need to check it again.
Why This Works:
- The efficiency of this approach lies in the fact that we exploit the sorted property of the array, making it unnecessary to use extra space for counting elements.
- Given that the array ensures at least one integer occurs more than 25% of the time, the solution is guaranteed, thus removing the need for additional validation checks.
Considerations:
- Due to the constraints and the requirement for an integer exceeding the 25% mark, there is always a definitive answer, which simplifies the problem.
- Operation is linear in terms of time complexity, O(n), because each element in the array is checked once.
- Space complexity is O(1) as the solution does not require any additional space proportional to the size of the input.
Solutions
- C++
- Java
- Python
class Solution {
public:
int findDominantElement(vector<int>& vec) {
int len = vec.size();
vector<int> potentialElements = {vec[len / 4], vec[len / 2], vec[3 * len / 4]};
int requiredCount = len / 4;
for (int elem : potentialElements) {
int startPos = lower_bound(vec.begin(), vec.end(), elem) - vec.begin();
int endPos = upper_bound(vec.begin(), vec.end(), elem) - vec.begin() - 1;
if (endPos - startPos + 1 > requiredCount) {
return elem;
}
}
return -1;
}
};
The given C++ solution is designed to find an element in a sorted array that appears more than 25% of the time. Here's a breakdown of how the solution operates:
- Define a public function
findDominantElement
that takes a reference to a vector of integers as its parameter. - Calculate the length of the vector
vec
and store it inlen
. - Identify potential elements that could meet the criteria. These are elements located at 25%, 50%, and 75% of the length of the vector.
- Set
requiredCount
which is the minimum number of times the potential element should appear in the vector, calculated as the size of the array quartered. - Iterate through these potential elements, and for each element:
- Utilize
lower_bound
to find the first occurrence of the element. - Utilize
upper_bound
to find the position just after the last occurrence of the element. - Check if the count of this element is greater than
requiredCount
. - If yes, return this element as it meets the criteria.
- Utilize
- If no element meets the requirements, return -1.
This method efficiently determines whether any given number in certain strategic positions in the sorted list meets the condition of appearing more than 25% of the time by levering the properties of binary search through lower_bound
and upper_bound
. This makes the solution robust and efficient for large inputs due to its logarithmic time complexity with respect to these operations.
class Solution {
public int findSpecialInteger(int[] sequence) {
int length = sequence.length;
int[] testCandidates = {sequence[length / 4], sequence[length / 2], sequence[3 * length / 4]};
int threshold = length / 4;
for (int candidate : testCandidates) {
int leftIndex = findLower(sequence, candidate);
int rightIndex = findUpper(sequence, candidate) - 1;
if (rightIndex - leftIndex + 1 > threshold) {
return candidate;
}
}
return -1;
}
public int findUpper(int[] sequence, int target) {
int left = 0;
int right = sequence.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (sequence[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public int findLower(int[] sequence, int target) {
int left = 0;
int right = sequence.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (sequence[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
The given solution in Java aims to identify an element in a sorted integer array that appears more than 25% of the time. The process utilizes an efficient method suitable for instances where the array's elements are sorted and allows for a rapid determination of the majority element.
Overview of the Solution:
The primary operation begins in the
findSpecialInteger()
method. First, it calculates the array's length and predefines three candidate positions: at one-quarter, half, and three-quarters of the array's length. These positions likely contain the element which could be repeating more than 25%.The algorithm then sets a threshold representing 25% of the array's length. This threshold is vital since any candidate must exceed this frequency to be considered the valid answer.
Each candidate from the predefined positions undergoes verification. For each candidate, two helper methods (
findLower()
andfindUpper()
) determine the range of indices where the candidate occurs.findLower()
searches for the first occurrence, whilefindUpper()
finds the position just after the last occurrence.By calculating the difference between the indices returned by
findLower()
andfindUpper()
, the code checks if the count of occurrences surpasses the 25% threshold. If true, the candidate is immediately returned as the result.
Performance Insight:
- The approach considerably reduces the need to search through the entire array by focusing on significant quartile positions.
- These binary searches (
findLower()
andfindUpper()
) contribute to a time complexity of O(log n), making the algorithm highly efficient for even large datasets.
Final Remark:
This method is particularly powerful for sorted arrays, leveraging strategic positions and efficient binary search operations to isolate and verify potential candidates quickly. Consequently, you solve for the element exceeding the 25% occurrence threshold in an optimized manner.
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
length = len(arr)
elements = [arr[length // 4], arr[length // 2], arr[3 * length // 4]]
threshold = length / 4
for element in elements:
first_occurrence = bisect_left(arr, element)
last_occurrence = bisect_right(arr, element) - 1
if (last_occurrence - first_occurrence + 1) > threshold:
return element
return -1
This solution provides a method to identify an element that appears more than 25% in a sorted array provided by the function findSpecialInteger
. The function computes based on Python 3 syntax and uses binary search mechanisms within the bisect
module for efficiency. Follow this concise step-by-step explanation to understand the function operation:
- Calculate the length of the input array
arr
and store it inlength
. - Identify candidate elements that might appear over 25% of the time. These elements are located at the quartile positions within the array – specifically, at
length/4
,length/2
, and3*length/4
. Store these candidates in the listelements
. - Set the
threshold
as a quarter of the array's length which is the minimum count for an element to be considered as appearing more than 25%. - Iterate through each element in
elements
. For each element, determine the positions of the first and last occurrence usingbisect_left
andbisect_right
respectively. - Calculate the count of the element's occurrences. If this count exceeds the
threshold
, return the element, as it appears more than 25%. - If none of the candidate elements meet the criteria, return -1 indicating no such element was found.
By calculating potential candidates based on fixed points and using binary search to determine frequency, the function remains efficient, operating within time complexities beneficial for large datasets.
No comments yet.