Jobs

Interviews

Discussions

Element Appearing More Than 25% In Sorted Array

Easy

Asked by:

More companies

36 views

Topics:

ArraysBinary Search

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

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Example 2:

Input: arr = [1,1]
Output: 1

Constraints:

1 <= arr.length <= 10⁴
0 <= arr[i] <= 10⁵

Try coding it in LeetCode

Element Appearing More Than 25% In Sorted Array

Easy

Asked by:

36 views

Topics:

ArraysBinary Search

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

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Example 2:

Input: arr = [1,1]
Output: 1

Constraints:

1 <= arr.length <= 10⁴
0 <= arr[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements in the array, and what is the range of possible values?
What should I return if no element appears more than 25% of the time?
Is the input array guaranteed to be sorted in ascending order, and strictly ascending or non-decreasing?
Could the array be empty or contain only one element?
Is the 25% threshold calculated with integer division or floating-point division?

Brute Force Solution

Approach

The brute-force approach to finding an element that appears more than 25% of the time in a sorted list is straightforward. We check the count of every unique number in the list to see if any of them meet the required frequency.

Here's how the algorithm would work step-by-step:

Go through the list, one number at a time.
For each number, count how many times that specific number appears in the entire list.
Check if that number's count is greater than 25% of the total number of elements in the list.
If a number's count exceeds 25%, that's the answer; stop and return that number.
If you've checked all the numbers and none of them appear more than 25% of the time, then there's no solution.

Code Implementation

def find_element_appearing_more_than_twenty_five_percent(numbers):
    list_length = len(numbers)

    for index in range(list_length):
        current_number = numbers[index]

        number_count = 0
        # Iterate to count occurrences of the current number.

        for inner_index in range(list_length):
            if numbers[inner_index] == current_number:
                number_count += 1

        # Check if current number appears more than 25% of the time.
        if number_count > list_length / 4:
            return current_number

    # No element appears more than 25% of the time.
    return -1

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the array. For each element, it counts its occurrences by iterating through the entire array again, which takes O(n) time. Since this counting process is repeated for each of the n elements, the total time complexity is O(n * n), which simplifies to O(n²). The input size n is the length of the array and directly influences the number of operations performed by the nested loops. Thus, the dominant factor is the nested loop structure, giving us a quadratic time complexity.

Space Complexity

O(1) – The provided algorithm iterates through the input array and maintains a counter for each unique number encountered. However, it does not explicitly store all unique numbers in a separate data structure. The space complexity is determined by the storage for the current number being checked and its count, which are constant regardless of the input array size N. Therefore, the auxiliary space required remains constant. The algorithm does not use any temporary lists, hash maps, or recursion, resulting in O(1) space complexity.

Optimal Solution

Approach

The problem asks us to find the element that appears more than 25% of the time in a sorted list. Instead of checking every element, the key is to smartly pick a few elements to check based on how frequently an element must appear to satisfy the condition.

Here's how the algorithm would work step-by-step:

Since the target element appears more than 25% of the time, we know it must appear at least once in every four elements.
Therefore, we can select a few elements that are roughly one-quarter apart in the list (e.g., at the 25%, 50%, and 75% positions).
For each of these selected elements, count how many times that specific element appears in the list.
If any of these counts is greater than 25% of the total number of elements, then that element is the answer.
If none of the selected elements appear more than 25% of the time, there is no solution, which violates the problem constraints.

Code Implementation

def findSpecialInteger(array_of_numbers):
    array_length = len(array_of_numbers)

    # These indices represent approximately 25%, 50%, and 75% of the array.
    quarter_index = array_length // 4

    potential_elements = [
        array_of_numbers[quarter_index],
        array_of_numbers[2 * quarter_index],
        array_of_numbers[3 * quarter_index],
    ]

    for potential_element in potential_elements:
        # Count the occurrences of potential_element.
        element_count = array_of_numbers.count(potential_element)

        # If the count is greater than 25% of array length, return.
        if element_count > array_length / 4:

            return potential_element

Big(O) Analysis

Time Complexity

O(n) – We select three elements at approximately the 25%, 50%, and 75% positions in the sorted array of size n. For each selected element, we perform a count operation by iterating through the array. This count operation has a time complexity of O(n). Since we perform the count operation a constant number of times (3 times in this solution), the overall time complexity is dominated by the count operation, which is O(n). Therefore, the overall time complexity of the solution is O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the selected elements and their counts. The space required to store these variables remains constant regardless of the input array's size, denoted as N. No auxiliary data structures like lists or hash maps are created that scale with the input size. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return -1 since no element can appear more than 25% of the time in an empty array.
Array with only one element	Return that single element since it appears 100% of the time, which is > 25%.
Array where all elements are the same	Return any element in the array, as it appears 100% of the time.
Array where the element appearing > 25% is at the very beginning	The linear search should find it quickly in this scenario.
Array where the element appearing > 25% is at the very end	The linear search must iterate to the end to confirm the frequency is > 25%.
Integer overflow when calculating frequency or array size	Use appropriate data types (e.g., long) for calculations to avoid overflow, or check the array length against `Integer.MAX_VALUE`.
No element appears more than 25% of the time	Return -1 to indicate no such element exists after iterating the entire array.
Large input array size	The time complexity should remain O(n) and space complexity O(1) (or O(log n) for binary search solution) to efficiently handle large inputs.

Empty input array

How to Handle:

Return -1 since no element can appear more than 25% of the time in an empty array.

Array with only one element

How to Handle:

Return that single element since it appears 100% of the time, which is > 25%.

Array where all elements are the same

How to Handle:

Return any element in the array, as it appears 100% of the time.

Array where the element appearing > 25% is at the very beginning

How to Handle:

The linear search should find it quickly in this scenario.

Array where the element appearing > 25% is at the very end

How to Handle:

The linear search must iterate to the end to confirm the frequency is > 25%.

Integer overflow when calculating frequency or array size

How to Handle:

Use appropriate data types (e.g., long) for calculations to avoid overflow, or check the array length against `Integer.MAX_VALUE`.

No element appears more than 25% of the time

How to Handle:

Return -1 to indicate no such element exists after iterating the entire array.

Large input array size

How to Handle:

The time complexity should remain O(n) and space complexity O(1) (or O(log n) for binary search solution) to efficiently handle large inputs.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements in the array, and what is the range of possible values?
What should I return if no element appears more than 25% of the time?
Is the input array guaranteed to be sorted in ascending order, and strictly ascending or non-decreasing?
Could the array be empty or contain only one element?
Is the 25% threshold calculated with integer division or floating-point division?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the list, one number at a time.
For each number, count how many times that specific number appears in the entire list.
Check if that number's count is greater than 25% of the total number of elements in the list.
If a number's count exceeds 25%, that's the answer; stop and return that number.
If you've checked all the numbers and none of them appear more than 25% of the time, then there's no solution.

Code Implementation

def find_element_appearing_more_than_twenty_five_percent(numbers):
    list_length = len(numbers)

    for index in range(list_length):
        current_number = numbers[index]

        number_count = 0
        # Iterate to count occurrences of the current number.

        for inner_index in range(list_length):
            if numbers[inner_index] == current_number:
                number_count += 1

        # Check if current number appears more than 25% of the time.
        if number_count > list_length / 4:
            return current_number

    # No element appears more than 25% of the time.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Since the target element appears more than 25% of the time, we know it must appear at least once in every four elements.
Therefore, we can select a few elements that are roughly one-quarter apart in the list (e.g., at the 25%, 50%, and 75% positions).
For each of these selected elements, count how many times that specific element appears in the list.
If any of these counts is greater than 25% of the total number of elements, then that element is the answer.
If none of the selected elements appear more than 25% of the time, there is no solution, which violates the problem constraints.

Code Implementation

def findSpecialInteger(array_of_numbers):
    array_length = len(array_of_numbers)

    # These indices represent approximately 25%, 50%, and 75% of the array.
    quarter_index = array_length // 4

    potential_elements = [
        array_of_numbers[quarter_index],
        array_of_numbers[2 * quarter_index],
        array_of_numbers[3 * quarter_index],
    ]

    for potential_element in potential_elements:
        # Count the occurrences of potential_element.
        element_count = array_of_numbers.count(potential_element)

        # If the count is greater than 25% of array length, return.
        if element_count > array_length / 4:

            return potential_element

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return -1 since no element can appear more than 25% of the time in an empty array.
Array with only one element	Return that single element since it appears 100% of the time, which is > 25%.
Array where all elements are the same	Return any element in the array, as it appears 100% of the time.
Array where the element appearing > 25% is at the very beginning	The linear search should find it quickly in this scenario.
Array where the element appearing > 25% is at the very end	The linear search must iterate to the end to confirm the frequency is > 25%.
Integer overflow when calculating frequency or array size	Use appropriate data types (e.g., long) for calculations to avoid overflow, or check the array length against `Integer.MAX_VALUE`.
No element appears more than 25% of the time	Return -1 to indicate no such element exists after iterating the entire array.
Large input array size	The time complexity should remain O(n) and space complexity O(1) (or O(log n) for binary search solution) to efficiently handle large inputs.

Empty input array

How to Handle:

Return -1 since no element can appear more than 25% of the time in an empty array.

Array with only one element

How to Handle:

Return that single element since it appears 100% of the time, which is > 25%.

Array where all elements are the same

How to Handle:

Return any element in the array, as it appears 100% of the time.

Array where the element appearing > 25% is at the very beginning

How to Handle:

The linear search should find it quickly in this scenario.

Array where the element appearing > 25% is at the very end

How to Handle:

The linear search must iterate to the end to confirm the frequency is > 25%.

Integer overflow when calculating frequency or array size

How to Handle:

Use appropriate data types (e.g., long) for calculations to avoid overflow, or check the array length against `Integer.MAX_VALUE`.

No element appears more than 25% of the time

How to Handle:

Return -1 to indicate no such element exists after iterating the entire array.

Large input array size

How to Handle:

The time complexity should remain O(n) and space complexity O(1) (or O(log n) for binary search solution) to efficiently handle large inputs.