algoadvance

Leetcode 1287. Element Appearing More Than 25% In Sorted Array

Problem Statement

You are given a sorted array of integers arr, where each element appears at least once. Return any element that appears more than 25% of the time in the array.

Clarifying Questions

  1. Q: Can there be multiple elements that appear more than 25% of the time?
    • A: The problem specifies returning any such element, so it is fine to return one if multiple exist.
  2. Q: Can the array be empty?
    • A: The constraints are not explicit about an empty array, but since each element appears at least once, we can assume the array is not empty.
  3. Q: What is the range of the array and size constraints?
    • A: Typically, interview problems assume reasonable constraints (e.g., 1 <= arr.length <= 10^4).

Strategy

  1. Frequency Requirement: For an element to appear more than 25% of the time, it must be present at least n / 4 times in the array, where n is the size of the array.

  2. Binary Search Approach:

    • For each candidate at positions i, i + n/4, i + 2*n/4, and i + 3*n/4 (ensuring no index out of bounds):
      • Use binary search to determine the leftmost and rightmost positions of the candidate.
      • Check if the count of occurrences of the candidate is more than n / 4.
    • Return the first candidate that meets the condition.

Code

Here is the C++ implementation of the above strategy:

#include <vector>
#include <iostream>
#include <algorithm>

int findSpecialInteger(std::vector<int>& arr) {
    int n = arr.size();
    int threshold = n / 4;
    
    for (int i = 0; i < n; i += threshold) {
        int candidate = arr[i];
        auto lower = std::lower_bound(arr.begin(), arr.end(), candidate);
        auto upper = std::upper_bound(arr.begin(), arr.end(), candidate);
        
        if (upper - lower > threshold) {
            return candidate;
        }
    }
    
    // This point should never be reached because there is always an element that appears more than 25%
    return -1;  // For safe return
}

int main() {
    std::vector<int> arr = {1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 6, 6, 6, 6, 6};
    std::cout << "Element Appearing More Than 25%: " << findSpecialInteger(arr) << std::endl;
    return 0;
}

Time Complexity

This approach is efficient and leverages the sorted nature of the array to achieve logarithmic time complexity in searching for the boundaries.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI