algoadvance

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

Problem Statement

Given an integer array arr sorted in non-decreasing order, there is exactly one integer in the array that appears more than 25% of the time. Return that integer.

Clarifying Questions

  1. Can the array include negative numbers?
    • The problem statement doesn’t restrict the value of integers, so both positive and negative integers can be included.
  2. What is the maximum and minimum length of the array?
    • The array length can be reasonably large, but it is sorted, which helps in reducing the complexity of our solution.
  3. Should we consider edge cases like if the array has only one element?
    • Yes, we should handle edge cases like single-element arrays appropriately.

Strategy

Since the array is sorted in non-decreasing order, every segment of the array is continuous, making it easier to identify the element that appears more than 25%.

To find the element that appears more than 25% of the time, we need to ensure that the frequency of an element e should be higher than n/4 where n is the length of the array. One effective way is to check elements at fixed intervals (n/4), (2n/4), (3n/4) since the element that appears more than 25% of the time will definitely appear at these quartiles.

Here is the proposed solution:

  1. Calculate the length n of the array.
  2. For each candidate element at indexes i*(n/4), where i ranges from 0 to 3, count its occurrences in the array and check if it exceeds n/4.
  3. Return the element that satisfies the condition.

Code

public class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        int step = n / 4;
        
        for (int i = 0; i < n; i += step) {
            int currentElement = arr[i];
            int firstOccurrence = firstIndex(arr, currentElement);
            int lastOccurrence = lastIndex(arr, currentElement);
            
            if (lastOccurrence - firstOccurrence + 1 > n / 4) {
                return currentElement;
            }
        }
        
        return -1; // This should not be reached as per problem constraints.
    }
    
    private int firstIndex(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int lastIndex(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

Time Complexity

The time complexity of this solution is as follows:

  1. The loop runs 4 times (constant time, O(1)).
  2. Both firstIndex and lastIndex involve binary search, thus they each take O(log n) time.

Overall, the time complexity of this solution is O(log n). Since the array is sorted, using binary search helps to efficiently find the first and last indices of elements, reducing the need for linear scans.

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