JavaScript Problem Solvers: Minimum Time Visiting All Points

CASE 011: Snakes On An Inclined Plane

I seemed to have fallen into a web of nested arrays, matrices and pattern matching. Today’s problem isn’t as complex as last week’s Onion Swap hullabaloo, but technically still deals with matrices. Technically technically, we are dealing with a graph, but at the same time, we aren’t.

I have also been working on my skills with recursion. One of the ways I’ve been practicing is by going back to problems I have already solved and refactoring them using recursion. So, at the end of this blog, I will also be providing a solution using Tail Call Recursion.

Anyways, let’s get solving.

THE PROBLEM

Here is a link to the problem on LeetCode

On a plane there are n points with integer coordinates points[i] = [xi, yi]. 
Your task is to find the minimum time in seconds to visit all points.
You can move according to the next rules:
- In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
- You have to visit the points in the same order as they appear in the array.

THE CONSTRAINTS

points.length == n

This isn’t really a necessary constraint, but provides a definition for the next constraint. n is only used in the problem’s explanation, and is not used anywhere else.

1 <= n <= 100

Here we get a range for how many sets of points we should expect, with the lower limit of 1 and an upper limit of 100. This tells us we don’t have to worry about a given array being empty.

points[i].length == 2

We are given a static value for how many elements each set of points will have. Each set of points, or points[i], should have an x value and y value, or [x, y] or points[i][x, y]. We can use this information to avoid nesting iterations in our solution.

-1000 <= points[i][0], points[i][1] <= 1000

This gives us the size of the coordinate plane, and a range for where we should expect to see any points. points[i][0] is the x value for each set of points, and points[i][1] is the y value, meaning we need to account for points appearing in the range of [-1000, -1000] to [1000, 1000]. In other words, the entire plane.

THE TESTS

THE BREAK DOWN

With our constraints dissected and test cases observed, let’s start breaking down the problem’s explanation and figuring out what we need to do:

On a plane there are n points with integer coordinates points[i] = [xi, yi].

Here is the context for the problem. n (or points.length) is a set of points on 2-D graph (coordinate plane), and points[i] represents each set of points. The elements of points[i] are the x and y position for each point, with points[i][0] being the x position, and points[i][1] being the y position. We can use static values for x and y thanks to the constraint points[i].length == 2.

Your task is to find the minimum time in seconds to visit all points.

This is our task, obviously. We simply have to find the shortest distance between each set of points, starting with points[0], and ending with points[points.length - 1]. I say distance because we can only move 1 unit on the coordinate plane per second. We get some more information about how time works relative to this problem in the rules below.

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).

This is why time and distance is relatively interchangeable. Speed is a fixed value at 1. We can only traverse through the coordinate plane 1 point at a time.

Moving diagonally between two points is the equivalent of incrementing or decrementing points[i][0] and points[i][1] at the same time. Moving horizontally is equal to incrementing/decrementing only points[i][0], while moving vertically is equal to incrementing/decrementing points[i][1].

You have to visit the points in the same order as they appear in the array.

This is more of a constraint than anything else. It tells us we must iterate through the elements in points as they are indexed. We must start at the beginning and move through to the end.

Since we can only move 1 point at a time, we will need to compare points[i] and points[i + 1]. We are strictly dealing with adjacent pairs.

THE SUSPECT

Based off the problem’s explanation and with the extra information we gained through breaking down each part, I came up with 6 things we need to do:

1.) Iterate from 0 until i < points.length — 1

This is the basic setup. We need to use a for loop and iterate through the entire set of points so we can access the next set of points relative to i. We need to set our upper limit to points.length - 1 since we are going to be accessing the next adjacent element of i.

2.) Find the distance between points[i][0] and points[i + 1][0]

Since we can move diagonally, we need to find the greatest difference between two sets of adjacent points. For the x axis, that is the difference between points[i][0] and points[i + 1][0].

We might encounter a problem though. If the value of points[i + 1][0] is larger than points[i][0], we will get a negative difference. We don’t want that. But, we can fix this by finding the absolute value of the difference between points[i][0] and points[i + 1][0] instead.

3.) Find the distance between points[i][1] and points[i + 1][1]

This is the same thing as step 2, but for the y values for each set of points. Everything we do in step 2 can be reapplied to step 3.

4.) Find the maximum of each difference

We can set the absolute value of the difference between points[i][0] and points[i + 1][0] to an out scoped variable xDist. We can do the same for the absolute value of the difference between points[i][1] and points[i + 1][1], and set the result to another out scoped variable yDist.

We can then compare the values of xDist and yDist to find which is greater.

Since we can move diagonally, the only thing that matters is how many steps we need to purely take horizontally or vertically. If points[i][0] === points[i][1], we can walk diagonally the entire time we are travelling between two points and the difference doesn’t matter. But as soon as points[i][0] !== points[i][1], we will need to travel horizontally or vertically at least once without moving diagonally. This is why the maximum difference between x and y values also represent the minimum distance between two points.

5.) Add the maximum difference of each pair to the total

Once we have compared xDist and yDist and found which is greater, we can add this to the total distance variable called totalDist.

6.) Return the total amount of distance between each set of points.

Once we have iterated through the entire set of points, found the absolute value of the difference for each set of points, found the maximum difference and added the maximum difference to the total distance, totalDist should equal the minimum time to visit all points, and we can return totalDist.

THE PSEUDO CODE

Let’s take the 6 steps we’ve outlined and condense them down into to some easier to digest pseudo code:

THE CODE

With our pseudo code looking good, let’s start writing out a solution.

First, let’s define the 3 variables xDist, yDist, and totalDist. Then, set up the basics for the for loop:

Next, we can add the logic to reassign xDist and yDist to the absolute difference of the x and y values for each set of points:

Then, at the end of each iteration, we can add the maximum value of xDist and yDist to totalDist:

And finally, add our return value of totalDist:

If we run our solution against the 3 test cases we have, we should be passing all of them without any problems:

Nice.

THE RECURSION

As promised here is the recursive version of our solution using Tail Call Optimization. I won’t go into too much detail here because recursion is a whole other can of worms, but I will outline some of the basic refactoring we would have to do.

We can set up our base case equal to the upper limit of our for loop. When we hit that base case, we want to return totalDist:

Then, we want to take the 3 variables we are using to keep track of distances (xDist, yDist, totalDist), add them to the function’s arguments, and set their default values to 0. We also want to add i with a default value of 0 as well:

Finally, we want to return our recursive function call. Since we want to use Tail Call Recursion, we need to make sure we are not creating a new local execution context on each recursive invocation. We can do so by updating each variable within the arguments of our recursive invocation:

If we run our recursive solution against our 3 test cases, we should be passing them once more:

Nice.

THE FINAL SOLUTIONS

Let’s take a final look at our solutions without the comments, and clean up some of our syntax:

Non-recursive:

LeetCode Submission Detail

Recursive:

LeetCode Submission Detail

Seems like the recursive solution is a little bit faster. Interesting.

MISSION COMPLETE

While minTimeToVisitAllPoints isn’t the most complicated problem out there, I felt like the solution we came up with was interesting enough to share, and refactoring it with Tail Call recursion was interesting enough as well.

Recursion can be an overwhelming topic to tackle and remains somewhat of a mystery to me, so I think adding a little recursion to each blog (where applicable) would be a good way for me to practice and improve.

I definitely understand my solutions won’t be the best or most efficient, but either way I hope they help you or someone else figure out a way to solve a problem you encounter on this journey we call JavaScript.

Either way, I hope you got some useful information, and may all your functions return true, and all your requests respond with 200.

Stay safe…stay healthy…and keep fighting the good fight.