function recursiveCheck(array, valToPlace) {
    let currIndex = valToPlace - 1
    let nextVal = array[currIndex];
    array[currIndex] = valToPlace;

    if (nextVal != undefined && nextVal != valToPlace && nextVal > 0 && nextVal <= array.length) {
        recursiveCheck(array, nextVal);
    }
}

function linearTimeConstantSpaceReworked(array) {
    for (let index = 0; index < array.length; index++) {
        let val = array[index];

        if (val != undefined && val - 1 != index) {
            array[index] = undefined;

            if (val > 0 && val <= array.length) {
                recursiveCheck(array, val);
            }
        }
    }

    for (let index = 0; index < array.length; index++) {
        if (array[index] == undefined) {
            return index + 1;
        }
    }

    return array.length + 1;
}


let mainArray = [3, 4, -1, 1];
console.log(linearTime(mainArray));