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
int firstMissingPositive(int X[], int n)
{
for (int i = 1; i <= n + 1; i = i + 1)
{
bool missingFlag = true
for (int j = 0; j < n; j = j + 1)
{
if(X[j] == i)
{
missingFlag = false
break
}
}
if (missingFlag == true)
return i
}
}
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
int firstMissingPositive(int X[], int n)
{
heapSort(X, n)
int i = 0
While (X[i] < 1)
i = i + 1
missingPositive = 1
for (int j = i; j < n; j = j + 1)
{
if (missingPositive == X[i])
missingPositive = missingPositive + 1
else if (X[i] > missingPositive)
return missingPositive
}
return missingPositive
}
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
int firstMissingPositive(int X[], int n)
{
HashTable H
for (int i = 0; i < n; i = i + 1)
H[X[i]] = true
for (int i = 1; i <= n + 1; i = i + 1)
{
if (H[i] == false)
return i
}
}
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
int firstMissingPositive(int X[], int n)
{
int i = 0
while (i < n)
{
if (X[i] > 0 && X[i] <= n && X[X[i] - 1] != X[i])
swap(X[i], X[X[i]-1])
else
i = i + 1
}
for (i = 0; i < n; i = i + 1)
{
if (X[i] != i + 1)
return i + 1
}
return n + 1
}
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
int firstMissingPositive(int X[], int n)
{
int positiveEnd = partition(X, n)
for (int i = 0; i < positiveEnd; i = i + 1)
{
if (X[i] - 1 < positiveEnd)
X[X[i] - 1] = - X[X[i] - 1]
}
for (int i = 0; i < positiveEnd; i = i + 1)
{
if (X[i] > 0)
return i + 1
}
return positiveEnd + 1
}
int partition(int X[], int n)
{
int j = n - 1, i = 0
while (i <= j)
{
if (A[i] <= 0)
{
swap(A[i], A[j])
j = j - 1
}
else
i = i + 1
}
return i
}
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!
The Least Recently Used (LRU) is one of the popular caching strategies, which defines the policy to discard the least recently used items first from the cache and make room for new elements when the cache is full. It is used to organize items in order of their use, which allows identifying items that have not been used for a long time.
You are given an array X[] consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. This is an excellent matrix problem that can be solved in linear time complexity. The best part is — we are using the sorted order property and nested loops to improve the solution over the binary search approach.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!