Difficulty: Hard, Asked-in: Google, Amazon, Samsung
Key takeaway: One of the best searching problems to learn step-by-step optimization using various approaches. In-place hashing solution is an intuitive problem-solving approach that uses the same input array to process values and generate correct output.
Given an array that includes positive and negative numbers, write a program to find the smallest missing positive integer.
Example 1
Input: X[] = [2, -9, 5, 11, 1, -10, 7], Output: 3
Explanation: Consecutive positive integers 1 and 2 are present in the array. So the first missing positive is 3.
Example 2
Input: X[] = [2, 3, -2, 1], Output: 4
Explanation: Consecutive positive integers 1, 2, and 3 are present in the array. So the first missing positive is 4.
Example 3
Input: X[] = [4, 6, 5, 3, 8], Output: 1
Explanation: All values are positive, but the first positive integer 1 is missing in the input. So the output is 1.
Solution Idea
The positive number starts from the value 1 on the number scale. If the first missing positive number is some number k, then all the positive numbers from 1 to k-1 will be present in the array. The critical question is: What would be the maximum possible value of missing positive if we have an array of size n? Think!
If the size of the array is n, then the maximum possible missing positive number would be n+1 i.e, the scenario when all numbers from 1 to n are present in the array. So basic approach would be to search all positive integers starting from 1 to n+1 linearly. If any positive integer is missing in the sequence, then we return that value as an output.
Solution Pseudocode
Time and space complexity analysis
We are running two nested loops where both loops will run n times in the worst-case scenario. Time complexity in the worst-case = O(n²), Space Complexity = O(1)
Solution Idea and Steps
If we sort the input array, then all the positive numbers get lined up in increasing order, and we can linearly search to find the first missing positive integer. We can use efficient sorting algorithms like heap sort, merge sort, or quicksort to sort the input array. Suppose we are using in-place O(nlogn) sorting algorithm heap sort.
Solution Pseudocode
Time and space complexity analysis
Time complexity = Time complexity of sorting + Linear scan for finding the first missing positive = O(nlogn) + O(n) = O(nlogn). Space complexity = O(1) (Think!)
Solution Idea
This is a searching problem where we need to look for positive integers starting from 1 to n + 1. To improve the time complexity further, we can use a hash table instead of a linear search to enhance the searching efficiency. The hash table performs searching and insertion efficiently in the O(1) average.
Solution Steps
Solution Pseudocode
Time and space complexity analysis
Time complexity = Inserting n elements in hash table + Searching n elements in hash table = O(n) + O(n) = O(n). Space complexity = O(n), for the hash table of size n.
Solution Idea and Steps
Now the critical question is: can we solve this problem in place? Let’s think!
The best part of this idea is: we are modifying the same array and storing the results to get the correct output.
Solution Pseudocode
Time and space complexity analysis
We visit each number and put it in its right place at most once. In another way, we are running two separate single loops n times. So time complexity in the worst case = time complexity of modifying the array + time complexity of searching first missing positive = O(n) + O(n) = O(n)
Space complexity = O(1), as we use the same input array to place the elements at their correct position. That's why such approaches are always a premium approach to problem-solving!
Solution Idea and Steps
Here is an idea similar to the above approach, but here we first divide the array into two parts: the first part consists of positive numbers, and the second part consists of negative numbers. We are assuming the array can be modified.
We can better understand this approach via an example.
Initial Array: 1 -1 -5 -3 3 4 2 8
Step 1: Partition: 1 8 2 4 3 | -3 -5 -1, positiveEnd = 5
Step 2: Modifying the input array.
1 < positiveEnd, we change the sign of value at index 1 - 1 = 0
Array changes to: -1 8 2 4 3 | -3 -5 -1
2 < positiveEnd, we change the sign of value at index 2 - 1 = 1
Array changes to: -1 -8 2 4 3 | -3 -5 -1
4 < positiveEnd, we change the sign of value at index 4 - 1 = 3
Array changes to: -1 -8 2 -4 3 | -3 -5 -1
3 < positiveEnd, we change the sign of value at index 3 - 1 = 2,
Array changes to: -1 -8 -2 -4 3 | -3 -5 -1
Step 3: Traversing from index 0 to positiveEnd, we find X[4] = 3 > 0. The answer is 4 + 1 = 5
Why this approach is working perfectly? What is the critical reason behind it? We are leaving this intuition for the learners to think! Enjoy thinking!
Solution Pseudocode
Time and space complexity analysis
Time complexity = Time complexity of the partition + time complexity of modifying the input array + Linear scan to find the missing positive = O(n) + O(n) + O(n) = O(n)
Space complexity = O(1), we are solving the problem in place using the same input array!
Enjoy learning, Enjoy algorithms!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.