Finding First Missing Positive Integers the Right Way

Problem Statement

Stripe asked this problem.

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

You can modify the input array in-place.

Solution

For a given input, if we ensure that positive input value is in the correct index position (done using swap operation), then we can return first non-positive index as the missing value.
Let's break it down

1. Ensure Positive input value is in the correct index position and swap position if required

• Input Array with indices:
  [3, 4, -1, 1]
  0 1 2 3
• Placing value at index 0 to correct position:
  [-1, 4, 3, 1]
  0 1 2 3
• Placing value at index 1 to correct position, since index 0 is non positive:
  [-1, 1, 3, 4]
  0 1 2 3
• Placing new value at index 1 to correct position:
  [1, -1, 3, 4]
  0 1 2 3

2. Iterate first non-positive index as the missing value

• Return value 2 as solution
  [1, -1, 3, 4]
  0 1 2 3

Note: In C#, indexes starts from 0

C# Solution Code

Please find the running version of the below program at http://rextester.com/NLHZN78509

//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            /*
            This problem was asked by Stripe.
            Given an array of integers, find the first missing positive integer in linear time and constant space. 
            In other words, find the lowest positive integer that does not exist in the array. 
            The array can contain duplicates and negative numbers as well.
            For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
            You can modify the input array in-place.
            */
            var input = new [] {3, 4, -1, 1};
            Console.WriteLine(FindFirstMissingPositiveNumber(input));
            
            input = new [] {1, 2, 0};
            Console.WriteLine(FindFirstMissingPositiveNumber(input));
            
            input = new [] {3, 4, -1, 4};
            Console.WriteLine(FindFirstMissingPositiveNumber(input));

            input = new [] {4, 4, -1, 4};
            Console.WriteLine(FindFirstMissingPositiveNumber(input));
            
            input = new[]{7,8,9,11,12};
            Console.WriteLine(FindFirstMissingPositiveNumber(input));

            input = new int[]{};
            Console.WriteLine(FindFirstMissingPositiveNumber(input));
        }
        
        // Find the first missing positive number
        public static int FindFirstMissingPositiveNumber(int[] input){
            if(input == null || input.Length == 0){
                return 1;
            }
            for(int i = 0, j = 1; i < input.Length; i+=j)
            {
                // Ensure Value is in correct place, positive, within confinement of length and not already placed correctly 
                // example:
                // input value 1 at index 0
                // input value 3 at index 2
                var valuePositiveAndNotInCorrectOrder = input[i] != i+1 && input[i] > 0 && input[i] <= input.Length && input[i] != input[input[i]-1];
                if(!valuePositiveAndNotInCorrectOrder)
                {
                    // Skip negative values and values in correct place
                    // example value 1 at index 0
                    // value 3 at index 2
                    j = 1;
                    continue;
                }
                
                // Swap the elements in their correct order
                // Example:
                // Given array [3, 4, -1, 1]
                // For, i = 0 and input value = 3
                // we swap the value present at index 0 with index 2 (3-1)
                // [-1, 4, 3, 1]
                // eventually after few iterations we get 
                // [1, -1, 3, 4]
                var temp = input[input[i] - 1];
                input[input[i] - 1] = input[i];
                input[i] = temp;
                
                // Check the newly swapped value
                j = 0;
            }
            
            // Loop and return the first negative integer value[1, -1, 3, 4]
            for(int i = 0, j = 1; i < input.Length; i++)
            {
                // Return first index with non equal value
                if(input[i] != i+1)
                {
                    return i+1;                
                }
            }
            
            // Must be greater than the input length
            return input.Length + 1;
        }
        
    }
}