Recursion

Lost Keys

You dropped your keys when you were on a walk. The good news is that you were recording a video, and can easily tell when you had your keys and when you didn't. The video looks something like this:

Given the video video, return the time when you first lost your keys. If you never lost your keys, return None.

Example:

\notag \large \texttt{video = [True, True, False, False]}\\[8bp] \large \texttt{=> returns 2}

Explanation: You lost your keys at index 2.

First Few Test Cases:

timeLost([True, False, False, False])
# 1

timeLost([True, True, False, False])
# 2

timeLost([True, True, True])
# None

0. Problem

To solve this problem, we can use Binary Search, since the video is sorted based on True and False values.

search(i, j) # search versions i...j

1. Recursion

To use a Binary Search, you have to look at the middle value in the array.

We might be in the case where the middle element is True. In this case, we should continue searching to the right, between mid+1 and j:

The other case is if the middle element is False. In this case, we should continue searching to the left, between i and mid-1.

Putting these two cases together, here's the recursion:

search(i, j) = (
    mid = (i + j) // 2
    if video[mid]:
        search(mid+1, j)
    else:
        search(i, mid-1)
)

This recursion always moves towards the leftmost "False" value. This means we can keep track of the most recent "False" value that we've seen in the search, and return it as the solution to the problem.

leftmost = None

search(i, j) = (
    mid = (i + j) // 2
    if video[mid]:
        search(mid+1, j)
    else:
        # update index of most recent "False" value
        nonlocal leftmost
        leftmost = mid

        search(i, mid-1)
)

2. Base case

The recursion will call itself over and over again. We should stop recursing when two pointers cross each other.

if j == i-1:
    return

3. Code

To code this up, you combine the recursion and base case:

def timeLost(video):
    leftmost = None

    def search(i, j):
        # base case
        if j == i-1:
            return

        # recursion
        mid = (i + j) // 2
        if video[mid]:
            search(mid+1, j)
        else:
            nonlocal leftmost
            leftmost = mid
            search(i, mid-1)

    search(0, len(video)-1) # call function
    return leftmost

Time Complexity $O(\log n)$

Space Complexity $O(\log n)$ . We're using a recursive function, so the Call Stack takes up memory.

You can easily make the above code iterative, like this:

def timeLost(video):
    leftmost = None

    i = 0
    j = len(video) - 1

    while True:
        # base case
        if j == i-1:
            return leftmost

        # recursion
        mid = (i + j) // 2
        if video[mid]:
            i = mid+1
        else:
            leftmost = mid
            j = mid-1

Time Complexity $O(\log n)$

Space Complexity $O(1)$

Mark as Completed:

Submits:

timeLost

Test your code to get an output here!

timeLost(

)

Test your code to get an output here!