1620. Coordinate With Maximum Network Quality
Problem Description
In this problem, we are given the locations and quality factors of several network towers. Each tower is represented as an array with three elements - the x-coordinate, the y-coordinate, and the quality factor. We have to find a point on an X-Y plane that has the maximum sum of the signal qualities from all the reachable towers.
A tower is considered reachable if it is within a given radius. The quality of the signal from a tower decreases as the distance from the tower increases, and it is calculated using the formula q_i / (1 + d), where q_i is the tower's quality factor and d is the Euclidean distance from the tower to the point of interest. We round down the calculated quality to the nearest integer.
We need to find the coordinates (cx, cy) where the network quality is the highest. If there are multiple such coordinates with the same quality, we return the smallest lexicographically coordinate, one that has the smallest non-negative x-coordinate, and if those are the same, then the one with the smallest non-negative y-coordinate.
Intuition
To solve this problem, we perform exhaustive search – basically, we iterate over all the possible coordinates and calculate the network quality at each point by summing up the signal quality from each tower that is within the given radius.
We initiate a variable mx to keep track of the maximum network quality found so far, and a variable ans to store the best coordinates corresponding to mx. We compute the network quality at every point by iterating over a predefined range (coordinates from (0, 0) to (50, 50) in this case, assuming these bounds are set by the problem context, i.e., the given x's and y's are expected to lie within this range).
For each point (i, j), we iterate over all towers checking their reachability. If a tower is reachable (distance d is less than or equal to radius), we calculate its contribution to the signal quality using the provided formula, rounding down to the nearest integer, and add it to the current network quality t.
If t exceeds mx, we update mx with t and set ans to the current coordinates (i, j). After checking all possible coordinates, ans will contain the coordinates with the highest possible network quality.
The reason for checking every point is that we aim to find the optimal location with maximum signal strength and we cannot deduce the best location without comparing the signal strengths at all possible locations due to the Euclidean distance factor and varying quality factors of the towers.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Solution Approach
The solution provided uses a brute-force approach to find the best coordinate with the maximum network quality.
-
For this, we use two nested loops to iterate over all possible coordinate points within the given constraints. In this case, it iterates through
(0, 0)to(50, 50)as the solution only examines points with integral coordinates within this range. -
We initiate a variable
mxto track the highest network quality observed and a listansto store the corresponding coordinates of this quality. -
Inside the inner loop, for every point
(i, j), another nested loop iterates through the list oftowers. For each tower, it calculates the Euclidean distancedfrom the current coordinate(i, j)using the formulasqrt((x - i)^2 + (y - j)^2). -
If the calculated distance is less than or equal to the
radius, the tower is reachable, and its quality contribution is computed using the floor division formulaq / (1 + d). This is because signal quality is integer-valued after flooring. -
The variable
trepresents the total signal quality at the point(i, j)and is calculated by summing up the contributions from all reachable towers. -
If at any point
(i, j), the total signal qualitytis greater thanmx,mxis updated tot, andansis updated to[i, j]. Iftis equal to the maximum found so far, it automatically retains the earliest (and therefore lexicographically smallest) coordinates due to how the loops are structured (starting from(0, 0)). -
The function
floor()is used to perform the floor division operation to ensure that the quality is an integer. -
Finally, after all the coordinates are checked, the function returns
ans, which points to the coordinate with the highest network quality.
This approach does not use any sophisticated algorithmic pattern but relies on a simple exhaustive search. It is feasible when the range of coordinates is small, as the computational complexity is O(n * m * t), where n and m are the ranges of x and y coordinates to be checked, and t is the number of towers.
Which of these pictures shows the visit order of a depth-first search?
Example Walkthrough
Consider the following small example to illustrate the solution approach:
Suppose we have two towers and the radius is given to be 2 units. The towers have the following properties:
- Tower 1 has coordinates
(1, 2)and a quality factor of5. - Tower 2 has coordinates
(3, 4)and a quality factor of10.
To simplify, let's consider our grid extends from (0, 0) to (5, 5).
We would iterate from (0, 0) to (5, 5) and calculate the total network quality at each point. For example, at point (0, 0):
- Compute the distance from Tower 1:
d1 = sqrt((1 - 0)^2 + (2 - 0)^2) = sqrt(1 + 4) = sqrt(5) - Since
d1is greater than the radius of2, Tower 1 is unreachable and contributes0to the network quality. - Compute the distance from Tower 2:
d2 = sqrt((3 - 0)^2 + (4 - 0)^2) = sqrt(9 + 16) = sqrt(25) - Since
d2is also greater than the radius of2, Tower 2 is unreachable and contributes0to the network quality. - The total network quality at point
(0, 0)is0.
Continuing this process for each point, assume we reach coordinate (2, 3):
- Compute the distance from Tower 1:
d1 = sqrt((1 - 2)^2 + (2 - 3)^2) = sqrt(1 + 1) = sqrt(2) - Tower 1 is reachable as
d1 <= 2, so the quality contribution from Tower 1 isfloor(5 / (1 + sqrt(2))). - Compute the distance from Tower 2:
d2 = sqrt((3 - 2)^2 + (4 - 3)^2) = sqrt(1 + 1) = sqrt(2) - Tower 2 is reachable as
d2 <= 2, so the quality contribution from Tower 2 isfloor(10 / (1 + sqrt(2))). - The total network quality at point
(2, 3)is the sum of quality contributions from both towers.
We continue this for all points on the grid from (0, 0) to (5, 5), keeping track of the maximum network quality and the corresponding coordinates. After we check all points:
- Let's say the highest network quality found was
12at point(2, 3). This would be ourmx. - Given the highest quality,
answould be[2, 3].
Finally, the coordinates (2, 3) with the highest network quality 12 would be returned.
The reason for choosing such a small grid is to explain the brute force approach clearly without diving deep into a complex calculation that would involve many iterations. This step-by-step progression through the solution approach provides insight into the methodology of searching for the best signal quality on a grid.
Solution Implementation
1from math import floor
2
3class Solution:
4 def bestCoordinate(self, towers: List[List[int]], coverage_radius: int) -> List[int]:
5 # Initialize max signal quality and answer coordinates.
6 max_quality = 0
7 best_coordinate = [0, 0]
8
9 # Iterate through each possible point on the grid.
10 for i in range(51):
11 for j in range(51):
12 total_quality = 0 # Sum of signal qualities from all towers for this point.
13
14 # Calculate the signal quality from each tower at the current point.
15 for x, y, q in towers:
16 # Calculate euclidean distance from the tower to the current point.
17 distance = ((x - i) ** 2 + (y - j) ** 2) ** 0.5
18
19 # Add quality to the total if inside the coverage radius.
20 if distance <= coverage_radius:
21 total_quality += floor(q / (1 + distance))
22
23 # If the total signal quality at this point is greater than the max,
24 # update max_quality and best_coordinate to this point.
25 if total_quality > max_quality:
26 max_quality = total_quality
27 best_coordinate = [i, j]
28
29 # After checking all points, return the coordinates with the highest signal quality.
30 return best_coordinate
311class Solution {
2 public int[] bestCoordinate(int[][] towers, int radius) {
3 int maxSignal = 0; // to keep track of the highest signal quality
4 int[] bestCoordinates = new int[]{0, 0}; // to hold the best coordinates
5
6 // Loop through each possible coordinate on the grid up to 50x50
7 for (int x = 0; x < 51; x++) {
8 for (int y = 0; y < 51; y++) {
9 int signalQuality = 0; // to calculate the total signal quality at the point (x, y)
10
11 // Check each tower's contribution to the signal quality at the point (x, y)
12 for (int[] tower : towers) {
13 // Calculate the distance between tower and point (x, y)
14 double distance = Math.sqrt(Math.pow(x - tower[0], 2) + Math.pow(y - tower[1], 2));
15
16 // Add the tower's signal contribution if it is within radius
17 if (distance <= radius) {
18 signalQuality += Math.floor(tower[2] / (1 + distance));
19 }
20 }
21
22 // Update the maximum signal quality and the best coordinates if the current point is better
23 if (maxSignal < signalQuality) {
24 maxSignal = signalQuality;
25 bestCoordinates = new int[]{x, y};
26 }
27 }
28 }
29
30 // Return the coordinates with the best signal quality
31 return bestCoordinates;
32 }
33}
341#include <vector>
2#include <cmath>
3using namespace std;
4
5class Solution {
6public:
7 // Function to find the best coordinate with the maximum signal quality
8 vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
9 int maxSignalQuality = 0; // To store the maximum signal quality
10 vector<int> bestCoord = {0, 0}; // To store the best coordinate
11
12 // Iterate through each possible x coordinate within the grid limit
13 for (int x = 0; x < 51; ++x) {
14 // Iterate through each possible y coordinate within the grid limit
15 for (int y = 0; y < 51; ++y) {
16 int currentSignal = 0; // Signal quality at the current coordinate
17
18 // Iterate through each tower to calculate its contribution
19 for (auto& tower : towers) {
20 // Calculate Euclidean distance from the current coordinate to the tower
21 double distance = sqrt((x - tower[0]) * (x - tower[0]) + (y - tower[1]) * (y - tower[1]));
22
23 // If the distance is within the effective radius, add the tower's signal quality
24 if (distance <= radius) {
25 currentSignal += static_cast<int>(floor(tower[2] / (1 + distance)));
26 }
27 }
28
29 // Check if the current signal quality is greater than the max found so far
30 if (maxSignalQuality < currentSignal) {
31 maxSignalQuality = currentSignal; // Update max signal quality
32 bestCoord = {x, y}; // Update the best coordinate
33 }
34 }
35 }
36 // Return the best coordinate after checking all possible points
37 return bestCoord;
38 }
39};
401type Tower = [number, number, number];
2
3// Function to calculate Euclidean distance between two points
4function calculateDistance(x1: number, y1: number, x2: number, y2: number): number {
5 return Math.sqrt(Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2));
6}
7
8// Function to find the best coordinate with the maximum signal quality
9function bestCoordinate(towers: Tower[], radius: number): [number, number] {
10 let maxSignalQuality: number = 0; // To store the maximum signal quality
11 let bestCoord: [number, number] = [0, 0]; // To store the best coordinate
12
13 // Iterate through each possible x coordinate within the grid limit
14 for (let x = 0; x < 51; ++x) {
15 // Iterate through each possible y coordinate within the grid limit
16 for (let y = 0; y < 51; ++y) {
17 let currentSignal: number = 0; // Signal quality at the current coordinate
18
19 // Iterate through each tower to calculate its contribution
20 for (let tower of towers) {
21 // Calculate Euclidean distance from the current coordinate to the tower
22 let distance: number = calculateDistance(x, y, tower[0], tower[1]);
23
24 // If the distance is within the effective radius, add the tower's signal quality
25 if (distance <= radius) {
26 currentSignal += Math.floor(tower[2] / (1 + distance));
27 }
28 }
29
30 // Check if the current signal quality is greater than the max found so far
31 if (maxSignalQuality < currentSignal) {
32 maxSignalQuality = currentSignal; // Update max signal quality
33 bestCoord = [x, y]; // Update the best coordinate
34 }
35 }
36 }
37
38 // Return the best coordinate after checking all possible points
39 return bestCoord;
40}
41What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Time and Space Complexity
Time Complexity
The given code runs three nested loops:
- The first two loops iterate over a fixed range of 51 each, resulting in
51 * 51iterations. - The innermost loop iterates over the list of towers. If
nis the total number of towers, this loop will executentimes for each iteration of the first two loops.
Therefore, the time complexity can be determined by multiplying the number of iterations in each loop. This gives us 51 * 51 * n, which simplifies to O(n) since the 51 * 51 is a constant.
Thus, the overall time complexity is O(n).
Space Complexity
The space complexity of the given code is quite straightforward. There are a few integers (mx, i, j, t, x, y, q, d) and a list ans of size 2 being used to store the answer, which do not depend on the input size.
Therefore, since no additional space is used that scales with the input size, the space complexity is O(1), or constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.