Algorithm Practice (Part 1)

In this series of blogs, I’ll be working through some of the algorithm problems that I have encountered in my job search. Today, I’ll be solving one from Leetcode, called First Missing Positive. Here is their explanation of the problem:

So, we’re given an unsorted array of positive and negative integers and have to return the first positive number that is absent from the array.

Process

My first instinct with figuring out a solution for this algorithm is to use an object for iteration since the input argument is an unsorted array. Using an object makes sorting unnecessary in this case. I’ll initialize an empty object on the first line of the function:

function firstMissingPositive(nums) {
 const obj = {}
}

Next, I’ll initialize a variable called counter in order to keep track of the number for iteration and I’ll use it later on when I need to return the first positive number that is missing.

function firstMissingPositive(nums) {
  const obj = {}
  let counter = 1
}

The next step is to populate the object keys with each of the numbers in the array and the object values with the boolean value true. I do this using a for.. of loop. We’ll use this boolean value later to find the first positive number not in the array.

function firstMissingPositive(nums) {
    const obj = {}
    let counter = 1
    
    for (let num of nums) {
        obj[num] = true
    }
    // if nums === [1, 2, 3]
    // obj will look like this here: {1: true, 2: true, 3: true}
}

From here, we’ll use the counter variable we’ve defined in a for loop to iterate until we find a value in the object that is not true. Once that is found, I return the counter variable. The return statement at the end covers the case when the whole object is iterated through and all the values are true.

function firstMissingPositive(nums) {
    const obj = {}
    let counter = 1
    
    for (let num of nums) {
        obj[num] = true
    }
    // if nums === [1, 3, 4, 5]
    // obj will === {1: true, 3: true, 4: true, 5: true}
    
    for (counter; counter <= nums.length; counter++) {
        // the first iteration, counter === 1, 1 < 4;  
        // obj[1] === true, so this if statement isn't met
        // second iteration, counter === 2, 2 < 4
        // obj[2] === undefined, so the if statement is met
        if (obj[counter] !== true) {
            // 2 will be returned, and is the first missing positive
            // number in the input array
            return counter
        } 
    }
    
    return counter
};

Here is the solution without the comments:

function firstMissingPositive(nums) {
    const obj = {}
    let counter = 1
    
    for (let num of nums) {
        obj[num] = true
    }
    
    for (counter; counter <= nums.length; counter++) {
        if (obj[counter] !== true) {
            return counter
        } 
    }
    
    return counter
};

This solution’s time complexity is O(n), it’s time and space complexity is linear since the worst case scenario includes iterating through the entire input array. The amount of time that the function takes to complete correlates directly with the size of the array that is passed in.

Stay tuned for the next algorithms practice post!

Click here for part 2.