LeetCode 1620 - Coordinate With Maximum Network Quality

The problem asks us to find the integral coordinate on a 2D plane where the network quality is maximized. We are given s

leetcodemediumarrayenumeration

LeetCode Problem 1620

Difficulty: 🟡 Medium
Topics: Array, Enumeration

Solution

Problem Understanding

The problem asks us to find the integral coordinate on a 2D plane where the network quality is maximized. We are given several network towers, each defined by its (x, y) coordinates and quality factor q. A tower contributes to the network quality at a specific coordinate if it is within the given radius. The contribution of a tower at coordinate (x, y) is calculated using the formula ⌊qi / (1 + d)⌋, where d is the Euclidean distance from the tower to (x, y). The total network quality at a point is the sum of contributions from all towers within reach.

The expected output is the integral coordinate [cx, cy] where the network quality is highest. If multiple coordinates have the same network quality, the lexicographically smallest non-negative coordinate should be returned, meaning we prioritize smaller x, and if equal, smaller y.

Constraints tell us that the number of towers is limited (<=50), coordinates and quality factors are small (<=50), and radius is small (<=50). This implies that a brute-force solution over all possible coordinates on the grid is feasible. Edge cases include coordinates where multiple towers overlap, a single tower, or towers with zero contribution due to distance.

Approaches

Brute Force Approach

A brute-force approach is to consider every integral coordinate within the bounding box of all towers (from 0 to 50 for both x and y, due to constraints). For each coordinate (x, y), we calculate the sum of signal qualities contributed by all reachable towers using the given formula. We then track the coordinate with the maximum network quality. If multiple coordinates tie, we pick the lexicographically smallest one.

This works because the input size is small, but it requires checking every point in the 51x51 grid and iterating over each tower, which gives a time complexity of roughly O(51*51*n) = O(2601*n). For n=50, this is about 130,000 iterations, which is acceptable for this problem.

Key Insight for Optimization

Since the constraints are very small, there is no need for a complicated optimization. The brute-force approach is sufficient. We only need to ensure that we correctly handle the distance calculation, floor division, and lexicographical ordering. A minor optimization is to limit the grid to the bounding box around towers extended by radius, reducing unnecessary checks.

Comparison Table

Approach Time Complexity Space Complexity Notes
Brute Force O(n * R^2) where R = 51 O(1) Iterate over all integer coordinates in the bounding box, sum contributions from towers
Optimized Bounding Box O(n * r^2) O(1) Only iterate over coordinates that could be affected by at least one tower (radius around each tower)

Algorithm Walkthrough

  1. Determine the search space. Since all coordinates are integral and ≤50, we can safely iterate from 0 to 50 for both x and y.
  2. Initialize variables to track the maximum network quality and the corresponding coordinate (cx, cy).
  3. Iterate over each integral coordinate (x, y) within the search space.
  4. For each coordinate, initialize a temporary sum quality_sum = 0.
  5. Iterate over all towers:
  • Compute the Euclidean distance d from the tower to (x, y).
  • If d is less than or equal to radius, add ⌊qi / (1 + d)⌋ to quality_sum.
  1. After summing contributions from all towers, compare quality_sum with the current maximum:
  • If it is higher, update the maximum and the best coordinate.
  • If it is equal, update the best coordinate only if it is lexicographically smaller.
  1. After iterating all coordinates, return the best coordinate [cx, cy].

Why it works: Each integral coordinate within the possible grid is evaluated against all towers. The algorithm ensures that contributions outside the radius are ignored, and lexicographical ordering guarantees the correct tie-breaking.

Python Solution

from typing import List
import math

class Solution:
    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:
        max_quality = -1
        best_coord = [0, 0]

        for x in range(51):
            for y in range(51):
                quality_sum = 0
                for tx, ty, q in towers:
                    dist = math.sqrt((x - tx) ** 2 + (y - ty) ** 2)
                    if dist <= radius:
                        quality_sum += math.floor(q / (1 + dist))
                if quality_sum > max_quality or (quality_sum == max_quality and [x, y] < best_coord):
                    max_quality = quality_sum
                    best_coord = [x, y]

        return best_coord

Explanation: The code iterates over the 51x51 grid, computes the signal contribution from each tower if it is within the radius, and tracks the coordinate with the maximum quality. Lexicographical comparison is done using the list comparison [x, y] < best_coord.

Go Solution

import (
    "math"
)

func bestCoordinate(towers [][]int, radius int) []int {
    maxQuality := -1
    bestCoord := []int{0, 0}

    for x := 0; x <= 50; x++ {
        for y := 0; y <= 50; y++ {
            qualitySum := 0
            for _, tower := range towers {
                tx, ty, q := tower[0], tower[1], tower[2]
                dist := math.Sqrt(float64((x-tx)*(x-tx) + (y-ty)*(y-ty)))
                if dist <= float64(radius) {
                    qualitySum += int(math.Floor(float64(q) / (1 + dist)))
                }
            }
            if qualitySum > maxQuality || (qualitySum == maxQuality && (x < bestCoord[0] || (x == bestCoord[0] && y < bestCoord[1]))) {
                maxQuality = qualitySum
                bestCoord[0] = x
                bestCoord[1] = y
            }
        }
    }

    return bestCoord
}

Go-specific notes: The code converts integer distances to float64 for Euclidean computation and uses math.Floor to apply the floor operation. Lexicographical comparison requires manual comparison of x and y due to Go lacking built-in list comparison.

Worked Examples

Example 1: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2

Iterating coordinate (2,1):

Tower Distance Contribution
[1,2,5] √2 ≈ 1.414 ⌊5 / (1 + 1.414)⌋ = ⌊5 / 2.414⌋ = 2
[2,1,7] 0 ⌊7 / (1 + 0)⌋ = 7
[3,1,9] 1 ⌊9 / (1 + 1)⌋ = 4

Total = 2 + 7 + 4 = 13. No other coordinate exceeds 13. Return [2,1].

Example 2: towers = [[23,11,21]], radius = 9

Only one tower, best coordinate is [23,11].

Example 3: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2

Best coordinate [1,2] with total quality 13 + 2 + 4 = 19.

Complexity Analysis

Measure Complexity Explanation
Time O(51_51_n) = O(n) Iterate over 51x51 grid; for each coordinate, sum contributions from n towers
Space O(1) Only variables for max quality and best coordinate; no extra data structures

Because the grid and n are small, this brute-force approach is efficient enough for the problem constraints.

Test Cases

# Basic test cases from examples
assert Solution().bestCoordinate([[1,2,5],[2,1,7],[3,1,9]], 2) == [2,1]  # Example 1
assert Solution().bestCoordinate([[23,11,21]], 9) == [23,11]           # Example 2
assert Solution().bestCoordinate([[1,2,13],[2,1,7],[0,1,9]], 2) == [1,2] # Example 3

# Single tower at origin
assert Solution().bestCoordinate([[0,0,10]], 1) == [0,0]

# Multiple towers at same location
assert Solution().bestCoordinate([[1,1,5],[1,1,10]], 1) == [1,1]

# Tie in quality, pick lexicographically smallest
assert Solution().bestCoordinate([[0,0,10],[2,0,10]], 2) == [0,0]

# Tower out of radius, should not contribute
assert