Jobs

Interviews

Discussions

Fixed Point

Easy

Uber

2 views

Topics:

ArraysBinary Search

Given an array of integers arr, find a fixed point (i.e., an index i such that arr[i] == i). More formally, return the lowest index i such that arr[i] == i.

If no such index exists, return -1.

Example 1:

Input: arr = [-10,-5,0,3,5]
Output: 3
Explanation: arr[3] == 3.

Example 2:

Input: arr = [0,2,5,8,17]
Output: 0
Explanation: arr[0] == 0.

Example 3:

Input: arr = [-10,-5,3,4,7,9]
Output: -1
Explanation: There is no index such that arr[i] == i.

Constraints:

1 <= arr.length < 10⁴
-10⁹ <= arr[i] <= 10⁹

Fixed Point

Easy

Uber

2 views

Topics:

ArraysBinary Search

Given an array of integers arr, find a fixed point (i.e., an index i such that arr[i] == i). More formally, return the lowest index i such that arr[i] == i.

If no such index exists, return -1.

Example 1:

Input: arr = [-10,-5,0,3,5]
Output: 3
Explanation: arr[3] == 3.

Example 2:

Input: arr = [0,2,5,8,17]
Output: 0
Explanation: arr[0] == 0.

Example 3:

Input: arr = [-10,-5,3,4,7,9]
Output: -1
Explanation: There is no index such that arr[i] == i.

Constraints:

1 <= arr.length < 10⁴
-10⁹ <= arr[i] <= 10⁹

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 range of integer values within the array?
Can the array contain negative numbers?
What should I return if multiple fixed points exist? Should I return the smallest index as specified in the prompt, or another?
Is the input array guaranteed to be sorted in ascending order?
What is the expected behavior if the input array is empty or null?

Brute Force Solution

Approach

The brute force approach to finding a fixed point involves checking every single possibility. We essentially go through each element one by one and see if it satisfies a specific condition. If we find an element that fits the condition, we've found our answer.

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

Start with the very first element in the collection.
Check if that element's value is the same as its position.
If they are the same, you've found the answer, and you can stop.
If they are not the same, move to the next element.
Repeat the checking process for each element one after another.
Continue until you either find an element that matches its position, or you run out of elements to check.

Code Implementation

def fixed_point_brute_force(number_list):

    for index in range(len(number_list)):

        # We are checking each element if its value equals its index
        if number_list[index] == index:

            return index

        # If no match is found, the list does not have a fixed point
    return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n, examining each element once. For each element, it performs a single comparison to determine if the index equals the value. In the worst-case scenario, the algorithm iterates through all n elements without finding a fixed point. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided brute force algorithm iterates through the input without using any auxiliary data structures. It only uses a few constant space variables (e.g., for indexing and comparing the element value to its position). The space required does not depend on the input size N (where N is the number of elements in the collection). Therefore, the space complexity is constant.

Optimal Solution

Approach

The problem asks to find a place in a sorted sequence where the value is the same as its position. The trick is to avoid looking at every single position by using a process that rapidly eliminates large sections of the sequence where the solution can't possibly be.

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

Start by looking at the middle of the sequence.
Compare the value at that middle position to the position number itself.
If the value is bigger than the position, the fixed point must be earlier in the sequence, so eliminate the second half.
If the value is smaller than the position, the fixed point must be later in the sequence, so eliminate the first half.
Repeat this process of checking the middle and eliminating half of the remaining sequence until you either find the fixed point or run out of places to look.
If you find the fixed point, you are done. If you run out of places to look, then there is no fixed point in the sequence.

Code Implementation

def fixed_point(sorted_sequence):
    left_index = 0
    right_index = len(sorted_sequence) - 1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2
        middle_value = sorted_sequence[middle_index]

        # Check if the value at middle_index is a fixed point
        if middle_value == middle_index:
            return middle_index

        # Adjust search space based on middle_value compared to middle_index
        if middle_value > middle_index:
            right_index = middle_index - 1

        # Adjust search space based on middle_value compared to middle_index
        else:
            left_index = middle_index + 1

    # No fixed point was found
    return -1

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a binary search approach. In each step, it compares the middle element of the array to its index and eliminates half of the remaining search space. This halving of the search space continues until the fixed point is found or the search space is exhausted. The number of times the search space can be halved is logarithmic with respect to the input size n, hence the O(log n) time complexity.

Space Complexity

O(1) – The described algorithm uses an iterative binary search approach. It maintains a constant number of variables, such as the middle index, and start and end pointers, regardless of the input size N. No auxiliary data structures like arrays, hash maps, or recursion are used to store intermediate results. Therefore, the space complexity remains constant, independent of the input size.

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as a fixed point cannot exist in an empty array.
Array with one element and it is a fixed point	Check if arr[0] == 0 and return 0 if true, otherwise return -1.
Array with one element and it is not a fixed point	Check if arr[0] == 0 and return -1 if false.
Large array where the fixed point is near the end	Binary search ensures logarithmic time complexity regardless of the fixed point's location.
Array with negative numbers, zero, and positive numbers	Binary search works correctly with mixed positive, negative, and zero values in the sorted array.
No fixed point exists in the array	Binary search should terminate and return -1 after searching the entire array without finding a match.
Integer overflow when calculating the middle index in binary search	Calculate the middle index as mid = low + (high - low) / 2 to avoid overflow.
Array contains extremely large integers	The algorithm is designed for integers of typical size and does not explicitly handle extremely large integers differently; the underlying language and hardware limitations apply.

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 range of integer values within the array?
Can the array contain negative numbers?
What should I return if multiple fixed points exist? Should I return the smallest index as specified in the prompt, or another?
Is the input array guaranteed to be sorted in ascending order?
What is the expected behavior if the input array is empty or null?

Brute Force Solution

Approach

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

Start with the very first element in the collection.
Check if that element's value is the same as its position.
If they are the same, you've found the answer, and you can stop.
If they are not the same, move to the next element.
Repeat the checking process for each element one after another.
Continue until you either find an element that matches its position, or you run out of elements to check.

Code Implementation

def fixed_point_brute_force(number_list):

    for index in range(len(number_list)):

        # We are checking each element if its value equals its index
        if number_list[index] == index:

            return index

        # If no match is found, the list does not have a fixed point
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by looking at the middle of the sequence.
Compare the value at that middle position to the position number itself.
If the value is bigger than the position, the fixed point must be earlier in the sequence, so eliminate the second half.
If the value is smaller than the position, the fixed point must be later in the sequence, so eliminate the first half.
Repeat this process of checking the middle and eliminating half of the remaining sequence until you either find the fixed point or run out of places to look.
If you find the fixed point, you are done. If you run out of places to look, then there is no fixed point in the sequence.

Code Implementation

def fixed_point(sorted_sequence):
    left_index = 0
    right_index = len(sorted_sequence) - 1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2
        middle_value = sorted_sequence[middle_index]

        # Check if the value at middle_index is a fixed point
        if middle_value == middle_index:
            return middle_index

        # Adjust search space based on middle_value compared to middle_index
        if middle_value > middle_index:
            right_index = middle_index - 1

        # Adjust search space based on middle_value compared to middle_index
        else:
            left_index = middle_index + 1

    # No fixed point was found
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as a fixed point cannot exist in an empty array.
Array with one element and it is a fixed point	Check if arr[0] == 0 and return 0 if true, otherwise return -1.
Array with one element and it is not a fixed point	Check if arr[0] == 0 and return -1 if false.
Large array where the fixed point is near the end	Binary search ensures logarithmic time complexity regardless of the fixed point's location.
Array with negative numbers, zero, and positive numbers	Binary search works correctly with mixed positive, negative, and zero values in the sorted array.
No fixed point exists in the array	Binary search should terminate and return -1 after searching the entire array without finding a match.
Integer overflow when calculating the middle index in binary search	Calculate the middle index as mid = low + (high - low) / 2 to avoid overflow.
Array contains extremely large integers	The algorithm is designed for integers of typical size and does not explicitly handle extremely large integers differently; the underlying language and hardware limitations apply.