Smallest Missing Positive Integer

arrayUtils.js

function swap(arr, indexLeft, indexRight) {
    const temp = arr[indexLeft];
    arr[indexLeft] = arr[indexRight];
    arr[indexRight] = temp;
    return arr;
}

function deleteIndex(arr, indexToDelete) {
    for (let i = indexToDelete; i < arr.length; i++) {
        if (i + 1 < arr.length) {
            arr[i] = arr[i + 1];
        }
    }
    arr[arr.length - 1] = null;
    return arr;
}

module.exports = {
    swap,
    deleteIndex
};

smallestMissingPositiveInt.js

const { swap } = require('../../lib/arrayUtils');

//--------------------------------------------------------------------------------------------------
// Smallest Missing Integer with Space
//--------------------------------------------------------------------------------------------------

function smallestMissingWithSpace(arr) {
    const check = [];
    let response;

    arr.forEach(n => {
        check[n] = 1;
    });

    for (let i = 1; i <= check.length; i++) {
        if (!check[i]) {
            response = i;
            break;
        }
    }
    return response;
}

//--------------------------------------------------------------------------------------------------
// Smallest Missing Integer without Space
//--------------------------------------------------------------------------------------------------

function smallestMissingWOutSpace(arr) {
    let response;

    // Reorder array with positive numbers to the left and negatives to the right
    let i = 0;
    let j = arr.length - 1;
    do {
        if (arr[i] < 0 && arr[j] >= 0) {
            swap(arr, i, j);
            j--;
            i++;
        } else if (arr[i] < 0) {
            j--;
        } else if (arr[j] >= 0) {
            i++;
        } else {
            j--;
            i++;
        }
    } while (i < j);

    // Where a number exists, mark the corresponding index (0 based) with an x
    // If marking an index to the right of the current location, swap the values first
    for (let z = 0; z <= arr.length; z++) {
        const currentVal = arr[z];
        if (currentVal > 0 && currentVal < arr.length && currentVal !== 'x') {
            if (currentVal > arr[currentVal - 1] && currentVal > z + 1) {
                swap(arr, z, currentVal - 1);
                arr[currentVal - 1] = 'x';
                z--;
            } else {
                arr[currentVal - 1] = 'x';
            }
        }
    }

    // Find the first non-x index and return that (0 based, so plus 1)
    for (let y = 0; y <= arr.length; y++) {
        if (arr[y] !== 'x') {
            response = y + 1;
            break;
        }
    }

    return response;
}

module.exports = {
    smallestMissingWOutSpace,
    smallestMissingWithSpace
};

smallestMissingPositiveInt.test.js

const { assert } = require('chai');
const {
    smallestMissingWOutSpace,
    smallestMissingWithSpace
} = require('./smallestMissingPositiveInt');

describe('smallestMissingPositiveInt', () => {
    describe('smallestMissingWOutSpace', () => {
        it('should work with positive numbers in decending order', () => {
            const input = [6, 5, 3, 2, 1];
            const expected = 4;
            const actual = smallestMissingWOutSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with missing 1', () => {
            const input = [2, 3, 4, 5];
            const expected = 1;
            const actual = smallestMissingWOutSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with negative numbers', () => {
            const input = [-4, 3, -3, 4, -1, 5, 1];
            const expected = 2;
            const actual = smallestMissingWOutSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with other negative numbers', () => {
            const input = [-4, 3, -3, 4, 1, 5];
            const expected = 2;
            const actual = smallestMissingWOutSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with a 0 number', () => {
            const input = [-4, 3, -3, 4, -1, 0, 5, 1];
            const expected = 2;
            const actual = smallestMissingWOutSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with all negatives', () => {
            const input = [-2, -3, -4, -5];
            const expected = 1;
            const actual = smallestMissingWOutSpace(input);
            assert.equal(actual, expected);
        });
    });

    describe('smallestMissingWithSpace', () => {
        it('should work with positive numbers in decending order', () => {
            const input = [6, 5, 3, 2, 1];
            const expected = 4;
            const actual = smallestMissingWithSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with missing 1', () => {
            const input = [2, 3, 4, 5];
            const expected = 1;
            const actual = smallestMissingWithSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with negative numbers', () => {
            const input = [-4, 3, -3, 4, -1, 5, 1];
            const expected = 2;
            const actual = smallestMissingWithSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with other negative numbers', () => {
            const input = [-4, 3, -3, 4, 1, 5];
            const expected = 2;
            const actual = smallestMissingWithSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with a 0 number', () => {
            const input = [-4, 3, -3, 4, -1, 0, 5, 1];
            const expected = 2;
            const actual = smallestMissingWithSpace(input);
            assert.equal(actual, expected);
        });

        it('should work with all negatives', () => {
            const input = [-2, -3, -4, -5];
            const expected = 1;
            const actual = smallestMissingWOutSpace(input);
            assert.equal(actual, expected);
        });
    });
});