Problem

Given an array of distinct integers arr, where arr is sorted in ascending order , return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.

Examples

Example 1:

1
2
3

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

Example 2:

1
2
3

Input: arr = [0,2,5,8,17]
Output: 0
Explanation: arr[0] = 0, thus the output is 0.

Example 3:

1
2
3

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

Constraints:

  • 1 <= arr.length < 10^4
  • -109 <= arr[i] <= 10^9

Follow up: The O(n) solution is very straightforward. Can we do better?

Solution

Method 1 – Binary Search

Intuition

Since the array is sorted and all elements are distinct, we can use binary search to efficiently find the smallest index i such that arr[i] == i.

Approach

  1. Initialize left and right pointers for the array.
  2. While left <= right:
    • Compute mid = (left + right) // 2.
    • If arr[mid] < mid, search right half (left = mid + 1).
    • If arr[mid] > mid, search left half (right = mid - 1).
    • If arr[mid] == mid, record mid as a candidate and continue searching left half for a smaller index.
  3. Return the smallest index found, or -1 if none exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int fixedPoint(vector<int>& arr) {
        int l = 0, r = arr.size() - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == m) {
                ans = m;
                r = m - 1;
            } else if (arr[m] < m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func fixedPoint(arr []int) int {
    l, r, ans := 0, len(arr)-1, -1
    for l <= r {
        m := (l + r) / 2
        if arr[m] == m {
            ans = m
            r = m - 1
        } else if arr[m] < m {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int fixedPoint(int[] arr) {
        int l = 0, r = arr.length - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == m) {
                ans = m;
                r = m - 1;
            } else if (arr[m] < m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun fixedPoint(arr: IntArray): Int {
        var l = 0
        var r = arr.size - 1
        var ans = -1
        while (l <= r) {
            val m = (l + r) / 2
            if (arr[m] == m) {
                ans = m
                r = m - 1
            } else if (arr[m] < m) {
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def fixedPoint(self, arr: list[int]) -> int:
        l, r, ans = 0, len(arr) - 1, -1
        while l <= r:
            m = (l + r) // 2
            if arr[m] == m:
                ans = m
                r = m - 1
            elif arr[m] < m:
                l = m + 1
            else:
                r = m - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn fixed_point(arr: Vec<i32>) -> i32 {
        let (mut l, mut r, mut ans) = (0, arr.len() as i32 - 1, -1);
        while l <= r {
            let m = (l + r) / 2;
            let m_usize = m as usize;
            if arr[m_usize] == m {
                ans = m;
                r = m - 1;
            } else if arr[m_usize] < m {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fixedPoint(arr: number[]): number {
        let l = 0, r = arr.length - 1, ans = -1;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            if (arr[m] === m) {
                ans = m;
                r = m - 1;
            } else if (arr[m] < m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log n), since we use binary search on the array.
  • 🧺 Space complexity: O(1), as we use only a few variables.