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:

video = [True, True, False, False]=> returns 2\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:

0. Problem

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

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:

image

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.

image

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

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

2. Base case

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

3. Code

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

Time Complexity O(logn)O(\log n)

Space Complexity O(logn)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:

Time Complexity O(logn)O(\log n)

Space Complexity O(1)O(1)

Mark as Completed:
Submits:
timeLost
Test your code to get an output here!
timeLost(
)
Test your code to get an output here!