Blogs Hub

Minimum Time Visiting All Points - Array - Easy - LeetCode - MiniTV

Minimum Time Visiting All Points - Array - Easy - 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.

 

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]

Output: 7

Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   

Time from [1,1] to [3,4] = 3 seconds 

Time from [3,4] to [-1,0] = 4 seconds

Total time = 7 seconds

 

Example 2:

Input: points = [[3,2],[-2,2]]

Output: 5

 

Constraints:

points.length == n

1 <= n <= 100

points[i].length == 2

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

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
    public class MinTimeToVisitAllPointsSoln
    {
        public int MinTimeToVisitAllPoints(int[][] points)
        {
            if(points.Length == 0)
            {
                return 0;
            }

            int time = 0;
            int sourceX = points[0][0];
            int sourceY = points[0][1];
            for (int i = 1; i < points.Length; i++)
            {
                int destinationX = points[i][0];
                int destinationY = points[i][1];
                time += CalculateTimeBetweenPoints(sourceX, sourceY, destinationX, destinationY);

                sourceX = destinationX;
                sourceY = destinationY;
            }

            return time;
        }

        private int CalculateTimeBetweenPoints(int sourceX, int sourceY, int destinationX, int destinationY)
        {
            int time = 0;
            int diffX = Math.Abs(sourceX - destinationX);
            int diffY = Math.Abs(sourceY - destinationY);

            int diagonalMove = Math.Min(diffX, diffY);
            time = diagonalMove + Math.Abs(diffX - diffY);
            return time;
        }
    }
}

 

Time Complexity:O(n)

Space Complexity: O(1)

 

Unit Tests:

using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
    [TestClass]
    public class MinTimeToVisitAllPointsSolnTests
    {
        [TestMethod]
        public void MinTimeToVisitAllPointsSoln_First()
        {
            var arr = new int[,] {
                    { 1, 1 },
                    { 3, 4 },
                    { -1, 0 }
                };
            var output = 7;
            var res = new MinTimeToVisitAllPointsSoln().MinTimeToVisitAllPoints(ArrayMapper(arr));

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void MinTimeToVisitAllPointsSoln_Second()
        {
            var arr = new int[,] {
                    { 3 , 2 },
                    { -2, 2 }
                };
            var output = 5;
            var res = new MinTimeToVisitAllPointsSoln().MinTimeToVisitAllPoints(ArrayMapper(arr));

            Assert.AreEqual(output, res);
        }

        private int[][] ArrayMapper(int[,] matrix)
        {
            var arr = new int[matrix.GetLength(0)][];
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                arr[i] = new int[matrix.GetLength(1)];
                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    arr[i][j] = matrix[i, j];
                }
            }

            return arr;
        }
    }
}