[Solution]Problem 74: Find the First True in a Sorted Boolean Array [Stripe]
Logic, Problem Soling, Boolean, Arrays
Hey, it’s your favorite cult leader here 🐱👤
On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹
To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!
p.s. you can learn more about the paid plan here.
For some of you, this problem was a piece of cake.
If you were amongst these people, congrats!! Good job. It’s proof that you put that work in. However, I would still recommend that you read this solution. Toward the end of this post, we will discuss a very important concept that you can use to solve much harder problems. I picked this question as an introduction to that concept.
But before we proceed, I have a burning question for y’all-
Help me settle this. Now onwards to our solution.
Problem
An array of boolean values is divided into two sections; the left section consists of all false and the right section consists of all true. Find the First True in a Sorted Boolean Array of the right section, i.e. the index of the first true element. If there is no true element, return -1.
Input: arr = [false, false, true, true, true]
Output: 2
To solve this question, we will go over a very interesting idea. Before proceeding, tell me what you think that idea will be. Cookies for the person who gets it correct. The principle is important because it will allow you to solve much harder problems.
Step 1: Simple Solution
This is a conceptually simple problem. And as you know, when the problem is easy enough to understand, we go right into creating an easy brute-force solution for it. The benefits of this are numerous, and I’ve gone over them multiple times.
The brute force solution is easy enough to come up with. Since this is a search problem, we can simply use Linear Search to find the first true value. This will get over in O(n) time and constant space. No shockers so far.
So how can we improve this? If you read the question carefully, the term sorted array would have stood out to you. Since this is a sorted array and we need to search for a particular value, we should be able to use Binary Search in some way.
But how?
Step 2: Setting up the Comparison
The standard binary search algorithm looks like this-
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1The comparisons determine the next step. Imagine that our target was a boolean value instead of a number/string. The first comparison (arr[mid]==target) still works fine. However, the next one (arr[mid] < target) would cause some problems. How do we determine whether true > false (bet you weren’t expecting a philosophy discussion)?
In this question, this problem has been solved for us. We know that the left section consists of all false and the right section consist of all true. This tells us the following two things-
if the element is false, we discard everything to the left and the current element itself.
if the element is, the current element could be the first true although there may be another true to the left. We discard everything to the right but what about the current element?
To solve that, we can just track the index of the leftmost true's recorded. If the current element is true, then we update our variable with its index and discard everything to the right including the current element itself since its index has been recorded by the variable.
Let’s start implementing this.
Step 3: Coding it Up
The code for this looks a lot like vanilla binary search-
def find_boundary(arr: List[bool]) -> int:
left, right = 0, len(arr) - 1
boundary_index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid]:
boundary_index = mid
right = mid - 1
else:
left = mid + 1
return boundary_indexTime Complexity- O(n)
Space Complexity- 1
If you’ve read so far, you might be wondering what the important concept I was referring to is. Let’s get right into it.
Sorting vs Ordering
These are two related concepts, but understanding the distinction can be very useful to you. The idea of a sorted array will be obvious to you. But what is an ordered array. I’ll give you a hint. The following could be an ordered array-
[1,2,4,5,99,2,-1, 100]
Did you get it?
I’ll give you another hint- all sorted arrays are ordered.
Still shooting blanks? Any array that follows a specific rule set is an ordered array. In the example I gave you, the array follows the ordering that the first element is 1, the second is 2 … Thus, in that context, it is an ordered array and everything else is an unordered array.
Why is this relevant? The example I gave you is not very useful, but you can have arbitrarily complex ordering rules. As long as you know what the ordering is, you can always implement a variant of binary search to search through efficiently. One such example is the Leetcode 852. Peak Index in a Mountain Array. This question is the next level up in difficulty, but if you apply this framework, you will actually solve this question relatively easily. Even harder problems can be solved once you master this. If you can find a common ordering in your given problem, then you can apply Binary Search. Try it out and see for yourself.
Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke,
Go kill all,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd