## How it works?

The folks at Daily Coding Problem send you a problem that was asked at a top company every day for you to solve. The premium membership also offers the opportunity to verify your solution.

# Problem #4

```
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.
```

# My solution

```
using System;
using System.Collections.Generic;
using System.Linq;
namespace DailyCodingProblem.Solutions.Problem04
{
public class Solution
{
public static void Test()
{
var input = Console.ReadLine()
.Split(' ')
.Select(int.Parse)
.ToHashSet();
var minPositiveNumber = GetMinimalPositiveNumber(input);
Console.WriteLine(minPositiveNumber);
}
public static int GetMinimalPositiveNumber(HashSet<int> input)
{
var minPositiveNumber = 1;
while (true)
{
if (!input.Contains(minPositiveNumber))
{
break;
}
minPositiveNumber++;
}
return minPositiveNumber;
}
}
}
```

Solutions are posted in my Github account

# DailyCodingProblem

This repository contains solutions of the Daily Coding Problem tasks

.

Feel free to leave a like and post a comment.

If you also have any better solution in mind, by all means, share it, so we can learn from each other.

## Discussion

Here is my solution in Rust:

Being allowed to modify the input array is a key hint, and my solution utilizes this to semi-sort the array. I swap every number I encounter to it's "correct" place - it's 1-based index. If that index is outside the range of the array, or the array already has a duplicate of that number in that position, I don't move it. When I do swap, I check again the number I've swapped with, and swap it as well if necessary. I do this until I reach a number that I don't swap - and then I move to the next cell in the array.

Note that I check each number at least once. If it wasn't swapped before I reach it, then I check it when I reach it. And if it was swapped - I check it after the swap (I may also check it again if I encounter it)

After this phase, each cell will contain it's "correct" number if and only if that number was in the original input:

So, all that's left is to iterate through the array and return the 1-based index of the first cell that does not contain the "correct" number. If there is no such cell, that means that the original input had all the numbers from 1 to N and thus we return N + 1.

Space complexity is constant, because we did not use any collection (other than the original array, which we were allowed to modify)

Linear time complexity is a bit trickier to prove, because in the first iteration we are spending

`O(N)`

on each cell (at worst case we can do N swaps with the first cell). But this is amortized - after each swap one cell gets its "correct" number, and after that we no longer swap with or from that cell. This gives us`O(N)`

swaps - each constant time, together with the check we do before it - plus`O(N)`

for N constant checks that result in no swap (we advance to the next cell once we do a check that does not result in a swap), plus another`O(N)`

for doing the second pass on the modified array to find the missing number = linear time.Your solution is not constant space because you are using a hashset.