First Element Equals its Index
Let's check another problem with a sorted input array. Difficulty Level: Easy
We'll cover the following...
Problem statement
Suppose we are given a sorted array of distinct integers, nums, which are sorted in ascending order. We will return the smallest index i, which satisfies nums[i] == i. If no such i exists, we will return -1.
Constraints:
Example 1: General case
Input: [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, nums[0] = -10, nums[1] = -5, nums[2] = 0, nums[3] = 3, the output is 3.
Example 2: The answer is at the beginning of the array
Input: [0,2,5,8,17]
Output: 0
Explanation: nums[0] = 0. Thus the output is 0.
Example 3: The answer is missing
Input: [-10,-5,3,4,7,9]
Output: -1
Explanation: There is no such i that nums[i] = i. Thus the output is -1.
Intuition
This problem is similar to the first challenge that we solved in the previous lesson. But, in the case of this problem, there is a greater range of integers and the index we are looking for is absent. An index of an element is our target here.
Algorithm
-
Set the ...