array index and element equality

This easy pramp question seems utterly innocuous, so let's try digging below the surface:

Given a sorted array arr of distinct integers, write a function indexEqualsValueSearch that returns the lowest index i for which arr[i] == i. Return -1 if there is no such index. Analyze the time and space complexities of your solution and explain its correctness.

1input: arr = [-8,0,2,5]
2output: 2 # since arr[2] == 2
3
4input: arr = [-1,0,3,6]
5output: -1 # since no index in arr satisfies arr[i] == i.

Constraints:

• time limit: 5000ms
• input: array.integer arr
  • 1 arr.length 100
• output: integer

Solution

You may be tempted to do something clever, like a binary search, but a max array length of 100 and a time limit of 5000ms begs for a linear search. The problem does not ask for the most optimal solution, so any solution that fulfills the constraints and passes the tests will do. Since a linear search is simpler than a binary search, the path of least resistance is the correct one.

1def index_equals_value_search(arr):
2  for i, v in enumerate(arr):
3    if i == v:
4      return i
5  return -1

The above solution is fine, but in a fully Pythonic world, we may prefer:

1def index_equals_value_search(arr):
2  return next((i for i, v in enumerate(arr) if i == v), -1)

A generator expression is iterable, so calling nextgets its first item. If the first item is None then next returns the default value -1. This may seem like overkill, but generator one-liners can do lots of exotic work expressively, which leads to concise code that does more work. This is a good thing.

Filtering leading zeros

For example, given an array of integers, how would we go about filtering leading zeros? We may write:

1A = [0,0,0,1,2,3,0]
2for i, a in enumerate(A):
3   if a != 0:
4       A = A[i:]
5       break
6else:
7    A = A[len(A):]
8print(A)

The Pythonic equivalent would be:

1A = [0,0,0,1,2,3,0]
2A = A[next((i for i, a in enumerate(A) if a != 0), len(A)):]
3print(A)

The second version may seem more complicated, at first, but it is more to the point: we want to perform array indexing based on some logic, and have a default behaviour in case the array is all zeroes. The Pythonic functional approach expresses our intent more clearly than the standard for-loop approach.