Smallest Index With Equal Value - Leetcode Solution

Problem Statement: Given an array of distinct integers nums, return the smallest index i that satisfies nums[i] == i. If there is no such index, return -1.

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

Example 2: Input: nums = [0,2,5,8,17] Output: 0 Explanation: For the given array, nums[0] == 0, thus the output is 0.

Example 3: Input: nums = [-10,-5,3,4,7,9] Output: -1 Explanation: For the given array, there is no index i such that nums[i] == i, thus the output is -1.

Solution: We can solve the given problem statement by using Binary Search Algorithm. To perform the binary search on the given array, we can start by initializing the left index to 0 and right index to n-1, where n is the size of the array. Then, while the left index is less than or equal to right index, we can find the middle index as (left+right)//2. If the element present at the middle index is equal to the index itself, we can return the middle index as the smallest index. If the element at the middle index is greater than the index, we can update right to (middle-1), else we can update left index to (middle+1). If there is no such index, we can return -1.

Pseudo code: function smallestIndex(nums): left ← 0 right ← n-1 while left ≤ right do middle ← (left+right)//2 if nums[middle] = middle: return middle else if nums[middle] > middle: right ← middle-1 else: left ← middle+1 return -1

Time Complexity: The time complexity of the above solution is O(log n) as we are performing binary search on the given array of size n.

Space Complexity: The space complexity of the above solution is O(1) as we are not using any extra data structures.

Let us implement the above solution in Python.

1