To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
Take the next step by subscribing here
I got no clever introductions today,
So let’s get right into it. Since I really appreciate all the feedback you’ve all been giving me, this solution will be open-access to all. For access to more such high-quality solutions, get a premium subscription here.
Problem
A fixed point in an array is an element whose value is equal to its index. Given a sorted array of distinct elements, return a fixed point, if one exists. Otherwise, return False
.
For example, given [-6, 0, 2, 40]
, you should return 2
. Given [1, 5, 7, 8]
, you should return False
.
PS- There is something very tricky about this wording. Almost every developer I’ve worked with has missed a very crucial element and because of that their solution has been wrong. Can you guess what it is? Email me. If you get it right, I’ll give you free stuff. Hint- There is an ambiguity in the question wording that you absolutely have to clarify. See if you can spot it.
Step 0: Clarifying Question
Notice that the question uses the phrase elements, not numbers. This means that you could technically have anything inside the array (as long as you define a custom sorting order for it). Don’t miss this point to clarify and earn a brownie point.
Some interesting trivia for ya- According to some Computer Science purists, arrays have to be fixed lengths and only one type of element (this is to do with how your computer assigns memory). However, there are ways around this. For example, you can define an Object array in Java, and fill it with whatever you want. If you’re feeling extra greedy, you can mention this in your rationale for asking the clarification question. A great way to show off your knowledge and attention to detail.
Step 1: Making an easy assumption
Let’s start by operating under the assumption that we will get only numbers in the array, what do we do next? Once we solve this, easier variant, we can do the more chaotic version of the problem (by removing this assumption).
So what can we do to find a fixed point in an array of numbers? The easiest answer is to brute force it. Just loop through the entire array, and return the first fixed point. If you reach the end without hitting one, return false. This will be an O(n) time and O(1) solution. Is there any way to improve it?
We can also integrate a very easy base case that will help a lot with performance. If the first value in our array is already greater than the length of our array, we know that we can’t really find the fixed points.
if (len(array) < array[0]) return 0
Step 2: Improving the Brute Force
How can we improve a brute-force solution? Think back to the process I’ve detailed in this newsletter. Break your algorithm into multiple steps, and see how you could speed up individual components. If you can speed up one part of this, you will speed up the whole thing. If you attack the area with the biggest time complexity, you will bring down the order of magnitude of your code. The same principles apply to space complexity.
In our algorithm, the major component is loop traversal. If we can speed up this operation, we can speed the whole thing along. So to answer a smaller question- How can we speed up our array traversal?
This is where I want you to realize something. Our linear-search-like traversal hasn’t taken advantage of the sorted nature of the list. Since we know that the array is sorted, and we know what property we’re looking for, in comes your brother- Binary Search. We can just binary search through the array, and terminate when we catch a fixed point (or run out of points).
Now I know a lot of you already saw the Binary search coming. However, there’s a reason, I went through this song and dance. This is the thought process you can use to identify Binary Search and other optimizations, in harder problems. If you work through the steps and develop your mental muscles, then you’ll find your results shooting up.
The introduction of Binary Search drops our Time Complexity down to log(N). This is pretty much the best we can get since we can really traverse an array in Constant Time. This means that it’s a good time to handle the harder problem. How do we handle searching for a fixed point, in a mixed array? It’s easier than you’d think. Take a second to think about it. Proceed only when you have a solution or have given up.
…
No Peeking. You’re only cheating yourself.
Are you absolutely sure you want to go down? You won’t be able to take it back?
Proceed with caution.
Step 3: Using Comparators
Here is where we get a bit cheeky. Since we know that the array is sorted, we know that there is a predefined comparison order. Instead of reinventing the wheel, why not just use their comparison functionality? Essentially, we have to do nothing.
Feel like I cheated? Get over it. There’s a reason I tell you to take things nice and slow. It’s so you can spot little details like this, that make your work significantly easier.
Now let’s move on to coding it up.
Step 4: Coding It up
Our code will be fairly straightforward. In essence, this question is a naked Binary Search. So you should be able to code this up no problem. Take a look below-
def fixed_point(array):
if(array[0]>len(array)) return False
low, high = 0, len(array)
while low <= high:
mid = (low + high) // 2
if array[mid] == mid:
return mid
elif array[mid] < mid:
low = mid + 1
else:
high = mid - 1
return False
We use the equality operations and assume that they are overloaded to deal with our nuanced comparisons. This is a trivial assumption, so there’ll be no penalty for assuming this. As mentioned, you will only be rewarded for your attention to detail.
I’ll leave you with a design question- How would you build this comparison/sorting function? Would such a generalist comparison ever be useful? There are no wrong answers here. Just think about it.
Time Complexity- O(log N). We assume that the comparison can be done in Constant Time. This is a very safe assumption to make.
Space Complexity- O(1)
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. I’ll see you living the dream.
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
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75