Algorithm Talk! Day 5: Taking a Crack at an Easy Leetcode Problem

So I have already written 4 blog posts about different algorithms on array sorting and tree traversal. Though helpful to know, what I’ve found is that many interview problems don’t necessarily rely on your algorithm and data structure knowledge alone, but also your problem solving skills. We need to be comfortable enough with our tools to be able to solve a problem presented to us. By no means am I an expert at this, but I thought I would walk through my solution for this easy level Leetcode problem known as ‘Remove Element’.

The Process

I usually like to break down problem solving into concrete steps.

1. Read the problem thoroughly.

It might be tempting to try to speed read or skim the problem to try to save time on actually solving the problem itself. Resist this temptation! Avoiding mishaps such as having to skim again at a later point, or worse, solving the wrong problem, will save much more time than the few minutes we will be spending reviewing the prompt carefully.

Pay special attention to words like ‘given’, ‘arguments’(or ‘parameters’), and ‘return’. Ensure you have a clear picture of what values, types, etc. are expected as inputs and outputs.

From this, we can see we will be working with an array and a single value (presumably the of the type that the array contains, if we’re working with a strongly-typed language). We want to return a length value, so we will be returning the array.length property after we are done manipulating this array.

We can also see that we are expected to modify this array in place, meaning we cannot create another array.

2. Make use of your resources

If you are on a live-call with an interviewer, ask any questions you can think of. You don’t have to ask all of them at once, you can always ask while you’re in the midst of solving the problem. The important thing is to communicate your thought process, as this is the purpose of these types of questions/problems.

In this case, and for many of these coding challenge websites, whether you are using them for practice or a real interview, there will not be another human with you so you are unable to ask any clarifying questions. However, they usually provide a set of example inputs and outputs, and some really nice ones explain why the output is so. Keep these examples in mind and make sure you understand the process at which you would arrive at the output.

Leetcode is pretty nice in this regard.

3. Choose a coding language

At this point, unless your interviewer is specifically looking for your use of a particular language, feel free to choose whichever language you are most comfortable with. There is also the possibility that your interviewer will tell you to just use ‘pseudo-code’. Personally, I chose JavaScript, because it is a relatively succinct language and would save me some time not having to worry about typing and syntax (Some of you will have already noticed this was a mistake, and I will explain this in the next section).

When you select a language on Leetcode, it will automatically populate the code area with a set of given code.

var removeElement = function(nums, val) {
    //Our code goes here
}

4. Brute Force!

It is always suggested by many coding interview resources and authorities to get a solution down, even if it’s not perfectly efficient or optimal.

Since we are working with an array in-place, we need two pointers or variables for index. Addressing the mistake I made above, JavaScript does not support pointers, which made this a little more difficult to conceptualize, at least for me. I suggest that you use C++ for this problem if you are well-versed in pointers.

I ended up using just two variables, i and j.

let i = 0, j = 0; 

My basic idea was to have i iterate through the array step-by-step and to have any values that match val get ‘squeezed out’ using my index j.

At this point, I figured we’re going to need to compare every value inside the parameter array nums to val, so I started a while loop, assigning the current index i of nums to a temporary variable and comparing to val. If the value does not equal val, then I move the value to index position j, and increment j.

while (i < nums.length) {
  //Assign to a temp variable
  let temp = nums[i];
  //Compare to val, squeezing out any that equals val
  if (temp !== val) {
    nums[j++] = temp;
  }
  
  //Increment i before continuing loop
  i++;
}

In JavaScript, we can simply reassign the length property of an array and it will automatically cut off the array at index position length-1. So after this while loop, I simply assign the value of j to nums.length, and return it:

nums.length = j;
return nums.length;

5. Analyze your solution

Now that we have something down, we can take a look at our solution and start getting an idea of what our time and space complexity is. The latter is pretty easy to determine, since the question itself stipulated that we need to modify in place, which means if we did it correctly, we should be using O(1) space complexity since we are not creating any new arrays.

Generally the easiest way to determine time complexity, is to look at how many times we are looping through our array. Since in our code we looped only once, this results in a time complexity of O(n).

This is pretty good! Normally our next step would be:

6. Optimize (or at least try to) your solution

…But in this case we actually have the most ideal solution (at least for JavaScript). When optimizing your solutions for other types of problems, especially those you find that your brute force solution was O(n²), try to employ the use of ‘zero-time’ transactions such adding or removing from Stacks/Queues, or using Hashes( JS Objects) .