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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer technique does Quick Sort use?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

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.

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

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

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

Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1287. Element Appearing More Than 25% In Sorted Array

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings