1287. Element Appearing More Than 25% In Sorted Array

Problem Description

The problem provides us with an integer array that is sorted in non-decreasing order. It states that there is exactly one integer in the array whose occurrence exceeds 25% of the size of the array. Our task is to identify and return this integer. To put it simply, we need to find the integer that appears more than a quarter of the time in the list of numbers.

Intuition

The first thing to notice is that since the array is sorted in non-decreasing order, all instances of any given number will be consecutive elements in the array. To check if a number occurs more than 25% of the time, you don't need to count every occurrence of each number. Instead, you can look at specific points in the array that would indicate where the 25% threshold would fall.

For example, if an element occurs more than 25% in an array of size n, then this element must be the same as the element that is exactly a quarter of the length of the array (n / 4) away from it. In other words, the element at index i will be the same as the element at index i + n/4 for the integer that occurs more than 25% of the time.

This is because the sorted nature of the array ensures that a recurring element would occupy a contiguous block. If the block is big enough to cover more than 25% of the array, then the start and the point at a quarter length away must be part of this block and hence, contain the same value.

The solution takes advantage of this fact. It iterates through the array and checks if the current element is the same as the element n/4 indices away. The bitwise operation (n >> 2) is a more efficient way of calculating n/4, by shifting the binary representation of n to the right by 2 bits.

If it finds such an element, it returns it immediately, since the problem statement guarantees that there is exactly one such integer. If, for some reason, the loop ends without finding an integer (which should not happen given the problem's constraints), it returns 0.

Solution Approach

The implementation of the solution is straightforward and takes advantage of the fact that the list is already sorted. Here is a step-by-step walk-through of the solution approach:

Determine the length of the array and store it in variable n.
Loop through each element of the array with a for loop. With enumerate(), you have both the index i and the value val at that index.
Within the loop, check if the current element val is equal to the element a quarter length away from it in the array (arr[i + (n >> 2)]). The expression (n >> 2) efficiently calculates n/4 by using bitwise right shift operator, which essentially divides n by 2 twice.
If such an element that meets the condition is found, return it immediately. This is the element that occurs more than 25% of the time in the array because the elements in that range of the array are the same due to the array's sorted nature.
If no such element is found by the end of the loop (which theoretically should not happen given the problem guarantees an element exists), the function defaults to returning 0.

No additional data structure or complex pattern is used here. The solution capitalizes on the sequence's sort order to minimize the number of checks needed to find the required element. The correct identification of the element is predicated on the guarantee provided by the problem statement, which is that there must be an integer that satisfies the condition, thus making additional checks unnecessary.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example with the following sorted integer array to illustrate the solution approach:

arr = [1, 2, 2, 2, 3]

The size of this array n is 5. According to the problem, we are looking for an integer that occurs more than 25% of the time. Since 25% of the size of the array is 5 * 0.25 = 1.25, our threshold is more than 1.25 occurrences. Therefore, we are seeking an integer that appears at least 2 times since we cannot have a fraction of an occurrence.

Following the solution approach:

We determine that n = 5.
We begin to loop through each element using a for loop. We'll be checking if the element at the current index i is the same as the element at index i + (n >> 2). Remember (n >> 2) effectively calculates int(5 / 4) = 1, so we'll be comparing elements one index apart.
As we iterate:
- For i = 0: arr[0] is 1, and arr[0 + 1] is 2. No match, we move on.
- For i = 1: arr[1] is 2, and arr[1 + 1] is also 2. We have a match.
Since arr[1] is equal to arr[1 + 1], we found the element that occurs more than 25% of the time in the array (2 appears more than once).
We return the value 2 immediately without needing to check the rest of the array.

There's no need to continue iterating because by the problem's constraint, there's exactly one integer that must meet the condition, and we've already found it. If the array had been larger, our loop would continue checking this condition until the end, but this step is unnecessary in our example.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findSpecialInteger(self, arr: List[int]) -> int:
5        # Length of the array
6        length = len(arr)
7
8        # Iterate over the array's elements
9        for index, value in enumerate(arr):
10            # Compare the current element with the element at a quarter length away
11            # Using bitwise right shift operator to divide length by 4
12            if value == arr[index + (length >> 2)]:
13                # Since both are equal and are at least 25% apart, return the value
14                return value
15      
16        # In case no special integer is found, return 0 (though the problem statement implies there should be one)
17        return 0
18

1class Solution {
2    public int findSpecialInteger(int[] arr) {
3        // The length of the input array
4        int length = arr.length;
5      
6        // Iterate through the array with the intent to find the special integer.
7        // The special integer is the one that appears more than 25% of the time.
8        for (int index = 0; index < length; ++index) {
9            // Check if the current element is the same as the element which is away
10            // a quarter of the array's length. If it is, we've found the special integer.
11            // (n >> 2) is equivalent to dividing n by 4 (or a quarter of its length).
12            if (arr[index] == arr[index + (length >> 2)]) {
13                // Return the special integer if found.
14                return arr[index];
15            }
16        }
17      
18        // If no such element is found, return 0. This line should never be reached if the
19        // input always contains such a special integer, as per the problem's statement.
20        return 0;
21    }
22}
23

1#include <vector> // Include the required header for using vectors
2
3// The Solution class encapsulates the problem's solution.
4class Solution {
5public:
6    // Method to find the element that appears more than 25% of the time in a sorted array.
7    int findSpecialInteger(std::vector<int>& arr) {
8        int n = arr.size(); // Obtain the size of the array
9        // Iterate over each element in the array. We use the bitwise operator to divide 'n' by 4 (n >> 2).
10        // This is the same as n/4 but is potentially faster for powers of 2. 
11        for (int i = 0; i <= n - (n >> 2); ++i) { // The loop now stops at `n - (n >> 2)` to avoid accessing out-of-range elements.
12            // Check if the current element is the same as the element 25% ahead in the array.
13            // If it is, we return the value since it appears more than 25% of the time.
14            if (arr[i] == arr[i + (n >> 2)]) {
15                return arr[i];
16            }
17        }
18        // If no element appears more than 25% of the time, which theoretically should not happen in a valid input, return 0.
19        // Though given the problem constraints, this line should be unreachable.
20        return 0;
21    }
22};
23

1/**
2 * This function takes an array of numbers and returns the element that appears more than 25% of the time in the array.
3 * It uses a sliding window, leveraging the fact that if an element appears more than 25% of the time,
4 * then it must appear at the current index and again at a quarter of the array's length away.
5 * @param arr - The array of numbers to be checked.
6 * @return The special element occurring more than 25% of the time.
7 */
8function findSpecialInteger(arr: number[]): number {
9    // Get the length of the array
10    const lengthOfArray: number = arr.length;
11
12    // Iterate through the array
13    for (let i = 0; i < lengthOfArray; ++i) {
14        // Check if the current element is the same as the element a quarter array length away.
15        if (arr[i] === arr[i + (lengthOfArray >> 2)]) {
16            // Return the element if it is found to repeat after a quarter array length.
17            return arr[i];
18        }
19    }
20
21    // If no such element is found, return 0 (which can be seen as an error or a "not found" indication)
22    return 0;
23}
24

Time and Space Complexity

The given code snippet is designed to find an element in an array arr that appears more than 25% of the time. To determine the time and space complexity, let's analyze the given code:

Time Complexity: The code involves a single loop where i traverses from 0 to n-1, where n is the length of the array. The key operation to check is arr[i + (n >> 2)]. Shifting n by 2 to the right is equivalent to dividing n by 4 (n >> 2 is n/4). This operation finds the element at a quarter distance ahead of the current index i. Since it's done within a single loop, with no nested loops or recursive calls, the time complexity is linear with respect to the size of the input array. Hence, the time complexity is O(n).

Space Complexity: The algorithm only uses a constant amount of extra space for variables such as i, val, and n, with no additional data structures dependent on the input size. Therefore, the space complexity is O(1), which represents constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know