New update is available. Click here to update.

Last Updated: 25 Apr, 2021

Difficulty: Moderate

- In one second, the ninja can either:
- Move vertically by one unit, i.e., along the y-direction.
- Move horizontally by one unit, i.e., along the x-direction.
- Move diagonally by ‘sqrt(2)’ units, i.e., move one unit horizontally then one unit vertically.

- The ninja must visit the points in the exact order as they are given the ‘POINTS’ array.
- The ninja is allowed to pass through points that may be given later in the order, but these points will not be counted as visited.

```
‘POINTS = [ [3, 1], [-1, 3], [2, 0] ]’, ‘N = 3’
```

```
The path with minimum time is: ‘[3,1] -> [2,2] -> [1,3] - > [0,3] -> [-1,3] -> [0,2] -> [1,1] -> [2,0]’.
Time taken from [3,1] to [-1,3] = 4 seconds.
Time taken from [-1,3] to [2,0] = 3 seconds.
Total time = 7 seconds. Thus, you should return ‘7’ as the answer.
```

```
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.
The first line of each test case contains an integer ‘N’ denoting the number of points. Then, ‘N’ lines follow.
Each line contains two integers, ‘X’ and ‘Y’, representing an element of the array ‘POINTS’.
```

```
For every test case, the minimum time to visit all the points in the given order.
```

```
You do not need to print anything; it has already been taken care of. Just implement the function.
```

```
1 <= T <= 100
1 <= N <= 1000
Each element of ‘POINTS’ contains exactly two integers ranging from [-10^5, 10^5].
Time limit: 1 second
```

SIMILAR PROBLEMS

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximize

Posted: 9 Dec, 2022

Difficulty: Easy

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: