41. First Missing Positive

Problem Statement

First Missing Positive - LeetCode Apna College Video

Related: Pattern 1-n range array

---

Related : Cycle Sort

Naive Solution

N time N Space Solution

// naive approach O(n) space
int findNumber(int* arr, int n) {
    // create freq arr of positive number
    const int N = 1e6 + 2;
    bool freq_arr[N] = {false};
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0)
            freq_arr[arr[i]] = true;
    }
 
    // find gap
    bool ansFound = false;
    int ans = 1;
    for (ans; ans < N; ans++)
        if (freq_arr[ans] == false) {
            ansFound = true;
            break;
        }
 
    if (!ansFound)
        return -1;
 
    return ans;
}
 
// optimized approach O(1) Space
 

N time 1 Space Solution

Cycle sort Solution

• Assume that array only contains numbers from 1-n
• while element at ith position is not i+1, then swap it to its correct positon
  • if el is negative or greater than n, moce onto next element
  • if target el is same as target element, move onto next element

Transclude of Cycle-Sort#range-1-n