Maximum Time

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in company
Adobe

Problem statement

You are given ‘N’ locations. You are provided with an integer representing the speed. You have to find the maximum time it will take traveling between any two locations.

Each location has two integer values representing the ‘x’ and ‘y’ coordinates, respectively.

Note: 
You have to use Euclidean distance i.e., sqrt((y2 - y1)^2 + (x2 - x1)^2)
You have to return the time with the precision of up to 6 decimal places.
For example: 
You are given ‘locations’ = [[0, 2], [0, 0], [2, 0]], and ‘speed’ = 2, then the maximum time will be between points [0, 2], [2, 0] which is 1.41421356237. Hence the answer rounded up to 6 decimal places is 1.414214.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
 The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, 'N' and 'speed', representing the number of locations and speed, respectively.

The next ‘N’ lines contain two space-separated integers, ‘x’ and ‘y’, representing the point in coordinate space as a location.
Output Format: 
For each test case, print a positive real number, up to 6 decimal places, representing the maximum time it will take traveling between any two locations.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= N <= 10^5
1 <= speed <= 10^5
2 <= x, y <= 10^5

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
3 2
0 0
2 0
0 2
3 1
1 0
0 0
2 0
Sample Output 1:
1.414214
2.000000
Explanation:
For the first test case, locations = [[0, 2], [0, 0], [2, 0]], and speed = 2, then the maximum time will be between points [0, 2], [2, 0] which is 1.41421356237. Hence the answer rounded up to 6 decimal places is 1.414214.

For the second test case, locations = [[1, 0], [0, 0], [2, 0]], and speed = 1, then the maximum time will be between points [0, 0], [2, 0] which is 2.0. Hence the answer rounded up to 6 decimal places is 2.000000.
Sample Input 2:
2
4 2
0 2
0 3
0 4
0 1
2 2
1 0
Sample Output 2:
1.500000    
0.500000
Hint

 Try to find the points with the maximum distance between them.

Approaches (2)
Brute Force

In this approach, we will sort all the points by their X Coordinates. Then we will iterate through every possible coordinate combination and find the maximum distance among all points.

Then divide the maximum distance by speed to find the maximum time.
 

Algorithm:

  • Set maxDistance as 0
  • Sort the locations array
  • Iterate i from 0 to n - 1
    • Iterate j from i + 1 to n -1
      • Set distance as sum of the absolute value of (locations[i][0] + locations[j][0])^2 and absolute value of (locations[i][0] + locations[j][0]) ^ 2
      • Set maxDistance as the maximum of distance and maxDistance
  • Set the float ans as maxDistance  divided by X
  • Round ans to 6 floating points
  • Finally, return ans
Time Complexity

O(N^2), where N is the number of locations.

 

We are checking each location, and for each location, we are iterating over the whole array. This will take O(N^2) time. Hence the overall time complexity is O(N^2).

Space Complexity

O(1),

 

No extra space is being used. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Maximum Time
Full screen
Console