Solution of a coding interview problem. It finds the lowest positive integer that does not exist in the given integers array

MissingPositive.java

package org.jugistanbul;

/**
 * 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.
 * https://dailycodingproblem.com/
 *
 * @author hakdogan ([email protected])
 * Created on 20.11.2021
 ***/
public class MissingPositive
{
    private MissingPositive() {}

    /**
     * Method finds and returns missing positive number within specified rules
     * 
     * @param intArray
     *
     * @return missing positive
     */
    public static int findMissingPositive(final int[] intArray) {

        //You can modify the input array in-place
        sort(intArray, 1);

        var last = 0; //last positive number read
        var ignore = 0; //counter for non-positive numbers

        for(int i = 0; i < intArray.length; i++){

            if(intArray[i] > 0){

                // The missing positive number is 1
                // if the first element in the sorted array is greater than 1
                if(last == 0 && intArray[i] > 1){
                    return 1;
                }

                //If the difference between two consecutive items in the sorted array is greater than 1,
                // the missing positive number is the first item + 1
                if(i < intArray.length - 1) {
                    last = intArray[i];
                    if(intArray[i + 1] - intArray[i] > 1){
                        return intArray[i] + 1;
                    }
                }
            } else {
                ++ignore;
            }
        }

        //If the missing positive number is not found in the array,
        // the missing positive number is the count of positive numbers in the array + 1
        return (intArray.length + 1) - ignore;
    }

    /**
     * The method sorts the array passed as an argument in ascending order
     *
     * @param intArray
     * @param position
     */
    public static void sort(final int[] intArray, final int position) {

        int pos = position;

        if (intArray[position] < intArray[position - 1]) {

            var lowest = intArray[position];
            intArray[position] = intArray[position - 1];
            intArray[position - 1] = lowest;

            if(pos - 1 != 0){
                --pos;
            }

        } else {
            ++pos;
        }

        if (pos > 0 && pos < intArray.length) {
            sort(intArray, pos);
        }
    }
}

MissingPositiveTest.java

package org.jugistanbul;

import org.junit.Test;
import static org.junit.Assert.*;

import static org.jugistanbul.MissingPositive.findMissingPositive;


/**
 * @author hakdogan ([email protected])
 * Created on 21.11.2021
 ***/
public class MissingPositiveTest
{
    @Test
    public void checkMissingPositive(){
        assertEquals(2, findMissingPositive(new int[] {3, 4, -1, 1}));
        assertEquals(3, findMissingPositive(new int[]{1, 2, 0}));
        assertEquals(2, findMissingPositive(new int[]{3, 4, -2, 1}));
        assertEquals(1, findMissingPositive(new int[] {4, 3, 6, -1}));
        assertEquals(5, findMissingPositive(new int[] {2, 1, 4, 3}));
        assertEquals(5, findMissingPositive(new int[] {2, -4, 1, 1, 6, -2, 4, 3}));
    }
}

@gungoren Öncelikle değerli katkınız için teşekkür ediyorum.

int[] intArray = new int[] {3, 4, 2, 1} input durumunda beklenen sonuç 5 iken bu durum da ayrıca ele alınmalı.

Aslında bu ifadeniz çözümde atladığım temel bir başka noktayı daha yakalamama vesile oldu. new int[] {3, 4, -1, 1} inputunda beklenen 0 olmadığına göre, verilen dizi sıralanıp, eksik tamsayı sıralanmış dizinin ilk elemanı baz alınarak bulunmalı.

Gist'i güncelledim.

Selamlar,
intStream içerisinde ki filterda her bir eleman için tekrar Array.stream çalışacağı için karmaşıklığın O(n^2) olduğunu düşünüyorum.

Teorik olarak HashMap lere get ve put için O(1) düşünerek methodunuzu şu şekilde düzenledim, teorik olarak zaman karmaşıklığı O(n) e düşmüş oldu.

public static int findMissingPositive(final int[] intArray) {
        var numberMap = new HashMap<Integer, Boolean>();
        Arrays.stream(intArray)
                .filter(i -> i > 0)
                .forEach(i -> numberMap.put(i, true));

        var missingPositive = IntStream.iterate(1, i -> i + 1)
                .limit(numberMap.size())
                .filter(i -> !numberMap.containsKey(i))
                .findFirst()
                .orElse(numberMap.size() + 1);

        return missingPositive;
 }

Selam @eroberer

intStream içerisinde ki filterda her bir eleman için tekrar Array.stream çalışacağı için karmaşıklığın O(n^2) olduğunu düşünüyorum

Haklısın. Aslında Array.stream ile bir liste referansı alıp, IntStream içinde onunla da O(n) arama yapılabilir ama map daha performanslı, artı ilk eleman için sort'a gerek kalmıyor.

Çözümünde 0'ları dışarda bırakma, orElse ile size + 1 döndürme ve {4, 3, 6, -1} benzeri bir case'i yönetme için, ilk elemanı kullanma kısımlarını refactor ederek, giste yansıttım.

Katkın için teşekkürler.

Selamlar, soruda bizden istenilen array içerisindeki kayıp olan en küçük pozitif sayıyı bulmamız. Bu durumda en küçük sayıyı aramaya 1'den başlamamız gerektiğini düşünüyorum.

Yani assertEquals(5, findMissingPositive(new int[] {4, 3, 6, -1})); kısmında beklenilen output 5 değil 1 olmalı.

Selamlar @GulerEnes

Sen de haklısın :) Düşündüm, muhtemelen 0 için negatif olmayan(nonnegative) denmesinin tortusuyla burada 0'ı hesaba kattım, bu ilk elemanı tespit gibi ek bir işlemi de doğurdu.

Çözüm constant space'i de ihlal ediyor, müsait zamanda update edeceğim; katkı için teşekkürler.