[Solution]Problem 73: Find the smallest positive number missing from an unsorted array [Apple]
Problem Solving, Pointer Manipulation, 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 the full articles and support my writing, consider subscribing if you haven’t already!
p.s. you can learn more about the benefits of the paid plan here.
Before starting off with the solution, I have a special announcement for you.
This post will be free. Since this is a difficult question, I figured I’d open the access to everyone. Take a look through this, to get an understanding of how you can solve these very challenging problems on your own. If you want access to more such solutions, consider joining the cool kids in the premium tiers of the cult.
Let’s get into it.
Problem
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. You can modify the original array.
Examples
Input: {2, 3, 7, 6, 8, -1, -10, 15}
Output: 1
Input: { 2, 3, -7, 6, 8, 1, -10, 15 }
Output: 4
Input: {1, 1, 0, -1, -2}
Output: 2
Step 1: Reading the Problem
There are two things that stand out to me. Firstly, the question uses the word element instead of an integer. Remember that mathematically, there is no smallest positive number (try proving this), so it’s fair to assume the smallest missing positive integer. However, if there is an interviewer make sure you ask them this qualifying question. It’s easy brownie points and a good way to demonstrate your attention to detail.
Secondly, In its wording, this question gives you a huge hint. This hint carries with how to solve the problem. Any guesses on what this hint is?
Take a look at the following statement in the problem- You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
Generally speaking, these statements tell you two important things-
You’re dealing with a challenging problem. These constraints tell you that there is a very tricky solution, which meets these costs.
There exists a simpler more obvious solution, that will be slower than the expected solution.
To some of you, this might seem obvious. But remember, in high-pressure situations like interviews/competitive coding competitions, your mind will tend to rush and you will overlook little details.
There is another important aspect that this line brings in. It sets your expectations. By explicitly mentioning the time constraint requirements, it subconsciously anchors your mind to them. It will make your mind automatically discard any slower solutions. This is a problem. Why?
Regular readers of the Leetcode solutions know that to solve harder problems smoothly, creating a brute-force solution and optimizing your solution incrementally is a good bet. The mention of the expected time-space complexity anchors your thought process towards that, which can stop you from exploring the slower (and thus easier) solutions first.
So how do we counter this? Once you recognize this, the key is to temporarily ignore that constraint. Forget about the optimal solution, and solve an easier problem first. Let’s dive into that.
Step 2: The Simple Solution
Can we come up with an easy solution for solving this problem?
The easiest solution we can use is to implement sets. We build a set containing the positive numbers in our array. Then we start a loop starting from 1 (the first positive number). We check off all the values present in the set with a loop till we hit the missing value.
This takes advantage of two things-
Sets have constant lookup. Since they don’t take duplicate elements/key-value pairs, they will be more memory efficient than hash maps. To those of you that want to understand sets and hashing better, read this Math Monday here.
At a minimum, the missing value for an array of length l will have value l+1 missing. Think about why this is true.
The solution has O(n) time and O(n) space.
How can we improve this? First, it’s important to see which avenues we can optimize along. This question tells us that O(n) time is expected, so we want to focus on removing the space complexity. But what if we hadn’t been given that piece of information? How would we know what dimension to optimize?
Since we have to traverse an unordered array, it’s unlikely we can improve the O(n) time complexity. Therefore we will be better off spending time optimizing space. Remember you have limited time in an interview. So you want to get maximum bang for your buck.
So how do we optimize? Once again, we rely on simplification.
Step 3: Simplifying the Problem
Something I always tell my students about hard problems is, “Hard Problems are often easy/medium questions with additional constraints”. So if we have a problem, one way to solve them is to build a solution to the easier version. This might give us some hints on how to approach a harder problem.
An easier version of this problem might be with an array containing only positive elements. We could use the index of the array to mark the presence of the value in the array. This way we don’t have to care about the space. We traverse through the array, and for every value, change that value at that index to -1 (if it in bounds). Then traversing the modified array a second time means we just have to return the first index with a positive value. This is a pretty straightforward code. Write it yourself to practice. Share it in the comments below (or with me in DMs) for code review.
Step 4: Building up from the Simpler Problem.
Now that we have a solution, the next step is simple: turn our simple solution into a more complex solution. To do so, we can take our code, and continuously simplify conditions till we can link to our already solution. You will see this technique applied in proofs for Theoretical Computer Science (and a lot of upper-level math). It’s similar to the technique called reduction. To those of you who are still students, make sure to learn this technique very well.
So how can we reduce this problem to a simpler solution? What if we could somehow shift all the negative values to the left? Then we just take the values starting from starting positive values and check from there. Thus we can break down our problem into two aspects.
Segregate positive numbers from others i.e., move all non-positive numbers to left side. In the following code, the segregate() function does this part.
Ignore non-positive elements and consider only the part of the array which contains all positive elements. Traverse the array containing all positive numbers. To mark the presence of an element x, change the sign of value at index x to the negative. Traverse the array again and print the first index which has a positive value. In the following code, the findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.
Our segregate function is pretty straightforward. Note that we return the index after the last negative value (post-swapping) so that we know where to start.
def segregate(arr,size):
j = 0
for i in range(size):
if (arr[i] <= 0):
arr[i], arr[j] = arr[j], arr[i]
j += 1 # increment count of non-positive integers
return j
The next tricky part is shifting the elements. There are two things we want to keep track of, our index value is not out of bounds and repeating index values. We handle them both using the conditions:
if (abs(arr[i]) - 1 < size and arr[abs(arr[i]) - 1] > 0):
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
The first condition handles the bounds (we only go when the pointed index is in bounds). Think about why we constructed the second question the way we did.
We know have all the pieces. Time to finish this problem.
Step 5: Coding It Up
Putting everything together, we get-
def segregate(arr, size):
j = 0
for i in range(size):
if (arr[i] <= 0):
arr[i], arr[j] = arr[j], arr[i]
j += 1 # increment count of non-positive integers
return j
''' Find the smallest positive missing number
in an array that contains all positive integers '''
def findMissingPositive(arr, size):
# Mark arr[i] as visited by
# making arr[arr[i] - 1] negative.
# Note that 1 is subtracted
# because index start
# from 0 and positive numbers start from 1
for i in range(size):
if (abs(arr[i]) - 1 < size and arr[abs(arr[i]) - 1] > 0):
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
# Return the first index value at which is positive
for i in range(size):
if (arr[i] > 0):
# 1 is added because indexes start from 0
return i + 1
return size + 1
''' Find the smallest positive missing
number in an array that contains
both positive and negative integers '''
def findMissing(arr):
size=len(arr)
# First separate positive and negative numbers
shift = segregate(arr, size)
# Shift the array and call findMissingPositive for
# positive part
return findMissingPositive(arr[shift:], size - shift)
Time Complexity- O(n)
Space Complexity- 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,
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