Solving Leetcode’s (1437): Check If All 1’s Are at Least Length K Places Away

At time of writing this post, this problem was relatively new, with less than 10 JavaScript solutions offered up in the discussions. And the ones I saw were hard for me to understand what’s going on and why. So I thought this might be a good one to tackle in my typical, beginner-friendly style of step-by-step solution.

The problem states that we’re given an array called nums of 1s and 0s, like this one [1,0,0,0,1,0,0,1], and an integer (k), representing the amount of places, or distance, between all the 1s we want there to be, let’s say 2. In our example, if all the 1s are at least 2 places away from each other, we should return true. If not, we should return false. In this example we’d return true, because :

• The 1 in position 0, and the next 1 in position 4, are 3 positions apart…
• The 1 in position 4, and the next one in position 7, are 2 positions apart…
• And the 1 in position 0 and 7 are 6 places apart.

This can be represented by this diagram:

Let’s tackle the solution below.

Originally I thought that a hash map would be good for this, in order to get the values of the array, and what position they’re in. But then I realized, we really only need to know where the ones are, so that we can compare their relative positions to k. Let’s first initialize an array to put the locations of the 1s:

function checkOnes(nums, k) {
  let onesPositions = [];
}

Next, let’s iterate through the nums array, and populate our new created onesPositions array with the index of where the 1s are located in our input array:

function checkOnes(nums, k) {
  let onesPositions = [];
 for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 1) {
      onesPositions.push(i);
    }
  }
}

After this iteration completes, the onesPostions array will be this: [0, 4, 7]

If we look at this array, we can plainly see all the numbers are separated by at least 2. But how do we do test this in code? My method was to subtract one index from the other, and get the absolute value. If that value is greater or equal to k (2 in our example), then we should return true. If not, we should return false.

For illustrative and readability purposes, I wrote the algorithm to be verbose. So next, let’s create a variable that will help us test the distance between the first 1 and the last one:

function checkOnes(nums, k) {
  let onesPositions = [];
for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 1) {
      onesPositions.push(i);
    }
  }
const largestDistance =
    Math.abs(onesPositions[0] - onesPositions[onesPositions.length - 1]) - 1;
}

What we’re doing here is taking the first 1s position of the array (0), and subtracting the last position of the 1s array (7). We take the absolute value of that (we’re not dealing with negative distance here), and that gives us 7. We subtract 1 due to the nature of 0 index for the first position of an array in JavaScript, giving us 6. Because 6 is greater or equal to 2, we know that this satisfies our constraint of being at least k distances apart from each other

Next, let’s do the same thing for every number in between with a for loop. But while we’re at it, and since we’re iterating, why not do a test to see if the current 1 position we’re iterating with, and the next 1 position we’d look at is at least k distance apart? If it is, let’s push true to a results array. If it’s not, let’s push false in there.

function checkOnes(nums, k) {
  let onesPositions = [];
  let results = [];
for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 1) {
      onesPositions.push(i);
    }
  }
const largestDistance =
    Math.abs(onesPositions[0] - onesPositions[onesPositions.length - 1]) - 1;

  for (let i = 0; i < onesPositions.length - 1; i++) {
    let currentDistance = Math.abs(onesPositions[i] - onesPositions[i + 1]) - 1;

if (largestDistance && currentDistance >= k) {
      results.push(true);
    } else {
      results.push(false);
    }
  }

}

At the end of this iteration, our results array will looks like this: [true, true]. We need to make another quick test: if all the values in results are true, then we know every 1 in our nums array is at least 2 distances apart, and our function can return true. Here’s a quick, one liner to do that:

return results.every((val) => val === true);

The every() array method tests whether or not a function passes a test provided. The “test” I’m asking is if whether or not every value in my results array is true. Thus, in our example, this evaluates to true. Here’s the full code reference:

function checkOnes(nums, k) {
  let onesPositions = [];
  let results = [];
for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 1) {
      onesPositions.push(i);
    }
  }
const largestDistance =
    Math.abs(onesPositions[0] - onesPositions[onesPositions.length - 1]) - 1;

  for (let i = 0; i < onesPositions.length - 1; i++) {
    let currentDistance = Math.abs(onesPositions[i] - onesPositions[i + 1]) - 1;
if (largestDistance && currentDistance >= k) {
      results.push(true);
    } else {
      results.push(false);
    }
  }
  return results.every((val) => val === true);
}

If any value in the results array were anything beside true, our function would return false.

Can this be done with less lines of code? Absolutely. But this algorithm is still pretty time/space efficient O(n), and the primary goal is to understand a relatively easier, readable, step-by-step, explanation. If you did…

If you didn’t feel free to ask questions in the comments.

Thanks for reading!

And remember: grit > talent.