First Missing Positive - C Solution

1. Introduction

In this blog post, we will tackle a critical problem in array manipulation using C programming: finding the first missing positive integer in an unsorted array. This problem is essential in data analysis and has real-world applications in areas like database management and error detection.

Problem

Given an unsorted array of integers, the task is to find the smallest positive integer that does not appear in the array. The challenge is to implement a solution that is efficient in both time and space complexity.

2. Solution Steps

1. Segregate positive and negative numbers: rearrange the array so that all non-positive numbers are at the beginning.

2. Mark the presence of positive integers: for each positive number 'x' in the modified array, mark the x-th position in the array (if possible).

3. Scan for the first unmarked position: this position corresponds to the first missing positive integer.

4. Handle edge cases, such as when all numbers in the original array are negative.

3. Code Program

#include <stdio.h>

// Function to swap elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to segregate positive and non-positive numbers
int segregate(int arr[], int size) {
    int j = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] <= 0) {
            swap(&arr[i], &arr[j]);
            j++;
        }
    }
    return j;
}

// Function to find the first missing positive integer
int findMissingPositive(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int pos = abs(arr[i]) - 1;
        if (pos < size && arr[pos] > 0) {
            arr[pos] = -arr[pos];
        }
    }

    for (int i = 0; i < size; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }
    return size + 1;
}

// Main function to find the first missing positive integer
int firstMissingPositive(int arr[], int size) {
    int shift = segregate(arr, size);
    return findMissingPositive(arr + shift, size - shift);
}

// Main function to demonstrate firstMissingPositive function
int main() {
    int arr[] = {3, 4, -1, 1}; // Example input
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    int missing = firstMissingPositive(arr, arrSize); // Call the function
    printf("Output: %d\n", missing); // Print the result
    return 0;
}

Output:

2

Explanation:

The program efficiently finds the first missing positive integer in the array [3, 4, -1, 1]. It first segregates the positive and non-positive numbers. 

Then, it uses the index of the array to mark the presence of elements. The first unmarked position indicates the missing positive integer. In this case, the number 2 is missing, which is the smallest positive integer not present in the array. 

The approach used here optimizes the problem by utilizing the array's indices and works in place with constant extra memory.