Element appearing more than 25% in array

XXX. Find Integer Appearing More Than 25%

Binary Search

Array

Problem Statement:

Given a sorted array, find the integer that appears more than 25% of the time in the array. There will always be such an integer.

• Array is sorted in non-decreasing order
• One number must appear > n/4 times
• Need to find first and last occurrence

Implementation:

public int findSpecialInteger(int[] arr) {
    int n = arr.length;
    if(n == 1) return arr[0];
    
    // Check candidates at 25%, 50%, and 75% positions
    List list = new ArrayList<>(Arrays.asList(
        arr[n/4], arr[n/2], arr[(3*n)/4]
    ));
    
    for (int element : list) {
        // Find first and last occurrence
        int first = firstOccurrence(arr, element);
        int last = lastOccurrence(arr, element);
        
        // Check if frequency > 25%
        if(last - first + 1 > n/4) {
            return element;
        }
    }
    return -1;
}

// Binary search for first occurrence
private int firstOccurrence(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    
    while(start < end) {
        int middle = start + (end - start)/2;
        
        if(nums[middle] == target && 
           (middle == start || nums[middle-1] < target)) {
            return middle;
        }
        
        if(target > nums[middle])
            start = middle + 1;
        else
            end = middle;
    }
    return start;
}

// Binary search for last occurrence
private int lastOccurrence(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    
    while(start < end) {
        int middle = start + (end - start)/2;
        
        if(nums[middle] == target && 
           (middle == end || nums[middle+1] > target)) {
            return middle;
        }
        
        if(nums[middle] > target)
            end = middle;
        else
            start = middle + 1;
    }
    return start;
}

Complexity:

Time Complexity: O(log n) for binary search operations
Space Complexity: O(1)

Key Points:

• **Candidate Selection**:
  • Check elements at n/4, n/2, 3n/4 positions
  • One of these must be the answer
  • Uses sorted array property
• **Binary Search Usage**:
  • Find first occurrence of element
  • Find last occurrence of element
  • Calculate frequency from boundaries

Example:

For array [1,2,2,2,3,4,5]:

• Check at positions:
  • n/4: arr[1] = 2
  • first(2) = 1, last(2) = 3
  • 3 occurrences > n/4 = 1.75
  • Return 2

Implementation Notes:

• **Edge Cases**:
  • Handle single element array
  • Check boundaries in binary search
  • Handle equal elements properly
• **Binary Search Details**:
  • Use different conditions for first/last
  • Avoid infinite loops
  • Handle boundary cases