TikTok is growing, and the developers need more servers to keep up with all the new users. They have installed n servers across different locations, and each server is placed on a large grid. The jth server is located at the point (x[j], y[j]) on this grid.
The cost of connecting two servers, i and j, is the smaller of the two differences:
|x[i] - x[j]|, or|y[i] - y[j]|
Here, |a| means the absolute value of the number a (ignoring any negative signs).
Your task is to find the minimum cost to build a network where all the servers can communicate with each other, either directly or through other servers.
Function Description
Complete the function minCostToConnectServers in the editor.
minCostToConnectServers has the following parameters:
- 1.
int[] x: an array of integers representing the x coordinates of the servers - 2.
int[] y: an array of integers representing the y coordinates of the servers
Returns
int: the minimum cost to connect all servers
Example 1:
Input: x = [2, 4, 8], y = [6, 10, 9]
Output: 3
Explanation:To connect the servers, here's the strategy:
- Connect the first and second servers: The servers are at (2, 6) and (4, 10). The cost is calculated as min(|2 - 4|, |6 - 10|) = 2.
- Connect the second and third servers: The servers are at (4, 10) and (8, 9). The cost is min(|4 - 8|, |10 - 9|) = 1.
- Connect the first and third servers: The servers are at (2, 6) and (8, 9). The cost is min(|2 - 8|, |6 - 9|) = 3. However, we already have a cheaper way to connect them indirectly through the second server.
So, the optimal way to connect the first and second servers for 2, and then the second and third servers for 1. Thus, the total minimum cost is 2 + 1 = 3.
2 <= n <= 1050 <= x[i], y[i] <= 109The can be multiple servers at the same coordinates
input:
output: