Minimum Time Visiting All Points Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Bloomberg Facebook Media.net
algorithms Array coding Geometry Interview interviewprep LeetCode LeetCodeSolutionsViews 3767

The problem Minimum Time Visiting All Points Leetcode Solution provides us with an array or vector of points on coordinate axes. The problem after providing us with the input asks us to find the minimum time to visit all the points given in the input. When you move one unit in either of the x or y direction, you take 1 unit of time. When you move diagonally that is move 1 unit in both directions simultaneously. You encounter 1 unit time. Now, find out the minimum time required to visit all the given points. There is another condition. The condition states that we are required to travel all the points in the same order as given in input. So, without moving directly to the solution, let us take a look at some examples.

Minimum Time Visiting All Points Leetcode Solution

[[1,1],[3,4],[-1,0]]
7

Explanation: As also shown in the image, we need 3 unit time to move from first point to second. Then 4 unit time to move from second to last point. Thus, a total of 7 units of time is required.

Approach for Minimum Time Visiting All Points Leetcode Solution

The problem Minimum Time Visiting All Points Leetcode Solution asks us what is the minimum time to visit all the points given in the input. The problem also bounds us to travel the points in the same order as they are provided in the input. We are also told about the cost of each move. We can either move 1 unit in either of the two directions or we can move simultaneously 1 unit in both of the directions. All of these moves cost us 1 unit of time. So, generally one will try to move diagonally until one of the x or y value becomes equal to the x or y value of next point. Now, we are sure that one of the x or y is equal to the x or y of the current point. And now we need to move only vertically or horizontally.

the thinking seems a bit tough but the implementation of the problem turns out to be much simpler. Here, instead of doing the process separately where first we move diagonally and then in a single direction. We simply find the maximum difference of x and y values of the current and next point. This gives us a simple formula for each move.

Code

C++ code for Minimum Time Visiting All Points Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int ans = 0;
    int n = points.size();
    for(int i=1;i<n;i++){
        vector<int> cur = points[i], prev = points[i-1];
        int curVal = max(abs(cur[0] - prev[0]), abs(cur[1] - prev[1]));
        ans += curVal;
    }
    return ans;
}

int main(){
    vector<vector<int>> points({{1,1},{3,4},{-1,0}});
    cout<<minTimeToVisitAllPoints(points);
}

7

Java code for Minimum Time Visiting All Points Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        int n = points.length;
        for(int i=1;i<n;i++){
            int[] cur = points[i];
            int[] prev = points[i-1];
            int curVal = Math.max(Math.abs(cur[0] - prev[0]), Math.abs(cur[1] - prev[1]));
            ans += curVal;
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] points = {{1,1},{3,4},{-1,0}};
    System.out.println(minTimeToVisitAllPoints(points));
  }
}
7

Complexity Analysis

Time Complexity

O(N), because we have to traverse through the whole of the list and thus the time complexity is linear.

Space Complexity

O(1), because we used only a single variable to store the answer, Thus the space complexity is constant.

Translate »