First Missing Positive in c#

Programming C#
1

To find the first missing positive integer in an unsorted integer array, you can use a clever approach that utilizes the properties of array indices. Here’s a concise implementation in C# along with an explanation:

C# Implementation

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int n = nums.Length;

        // Step 1: Place each number in its right place, e.g., 1 at index 0, 2 at index 1, etc.
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // Swap nums[i] with nums[nums[i] - 1]
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        // Step 2: Identify the first missing positive
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1; // Missing positive is i + 1
            }
        }

        // If all positions are filled correctly, return n + 1
        return n + 1;
    }
}

Explanation

  1. Rearrangement Phase:

    • The idea is to rearrange the array such that each positive integer x (where 1 ≤ x ≤ n) is placed at the index x - 1.
    • We loop through the array and, for each element nums[i], we check if it is in the correct range (i.e., > 0 and <= n). If it is, and it is not already in the correct position, we swap it with the value at its target position. This continues until all possible swaps are made.
    • The inner while loop ensures that we keep swapping until the current number is either out of the valid range or already in its correct position.

  2. Finding the Missing Positive:

    • After rearranging, we perform a second pass through the array to find the first index i where nums[i] is not equal to i + 1.
    • The first index where this condition is true indicates that the number i + 1 is missing from the array.
    • If all indices are filled correctly, then the missing positive integer would be n + 1 (since all numbers from 1 to n are present).

Complexity

  • Time Complexity: O(n), since we essentially make two passes over the array.
  • Space Complexity: O(1), as we modify the array in place without using extra space.

This method is efficient and leverages the properties of indices and values effectively, making it a popular solution for the problem.