loading...

Daily Coding Problem #4

cwetanow profile image Ivan ・1 min read

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

.

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.

Posted on by:

Discussion

markdown guide
 

Here is my solution in Rust:

fn first_missing_positive(numbers: &mut [isize]) -> isize {
    let target_range = 1..=(numbers.len() as isize);
    for i in 0..numbers.len() {
        loop {
            if !target_range.contains(&numbers[i]) {
                break; // target cannot be moved
            }
            let correct_place = numbers[i] as usize - 1;
            if numbers[correct_place] == numbers[i] {
                break; // correct place already contains a duplicate of that number
                // NOTE: this may also mean that our number is already at the correct place, and is
                // its own duplicate.
            }
            numbers.swap(i, correct_place);
        }
    }
    numbers.iter().copied().enumerate()
        .find_map(|(i, number)| {
            if (i + 1) as isize == number {
                None
            } else {
                Some(i + 1)
            }
        })
        .unwrap_or_else(|| numbers.len() + 1) as isize
}

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:

  • If the number was not in the original input, it won't be anywhere in the array - because we are just swapping cells so the resulting array is a permutation of the original one.
  • If the number was in the original input, then at some point we have reached it and swapped it with this cell - unless that cell already had that number.

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.