Coordinate With Maximum Network Quality: Brute Force Simulation

You are given an array of network towers where towers[i] = [xi, yi, qi] represents a tower at coordinate (xi, yi) with signal quality qi. You are also given an integer radius. For any coordinate (x, y), the network quality is the sum of floor(qi / (1 + d)) for every tower where the Euclidean distance d = sqrt((x - xi)^2 + (y - yi)^2) is at most radius. Return the lexicographically smallest coordinate with the maximum network quality.

This is LeetCode 1620: Coordinate With Maximum Network Quality, and it is a clean example of solving a problem by brute force simulation over a bounded search space.

Why this problem matters

Not every problem needs a clever algorithm. Sometimes the constraints are small enough that you can try every possibility and pick the best one. This problem teaches you to recognize when brute force is not just acceptable but optimal. The grid is small, the math is simple, and the answer falls out of a triple nested loop. Learning to spot these bounded simulation problems saves you from overengineering solutions that do not need optimization.

The key insight

Tower coordinates are at most 50, so the answer must lie somewhere in the [0, 50] x [0, 50] grid. That is only 51 * 51 = 2601 candidate points. For each candidate, you loop through all towers, compute the Euclidean distance, check if it is within the radius, and accumulate the quality using the floor formula. Track the maximum quality seen so far, and if there is a tie, keep the lexicographically smaller coordinate (the one that comes first when you scan left to right, top to bottom).

The algorithm:

1. Enumerate every coordinate (x, y) where x and y range from 0 to 50.
2. For each candidate, sum up the signal contribution from every in-range tower.
3. If this total quality beats the current best, update the answer.
4. Return the best coordinate.

The solution

import math

def best_coordinate(towers: list[list[int]], radius: int) -> list[int]:
    best_quality = 0
    best = [0, 0]

    for x in range(51):
        for y in range(51):
            quality = 0
            for xi, yi, qi in towers:
                d = math.sqrt((x - xi) ** 2 + (y - yi) ** 2)
                if d <= radius:
                    quality += int(qi / (1 + d))
            if quality > best_quality:
                best_quality = quality
                best = [x, y]

    return best

Let's walk through each piece.

The outer two loops enumerate every candidate coordinate from (0, 0) to (50, 50). Because we scan x from small to large and y from small to large, we naturally visit lexicographically smaller coordinates first. The strict > comparison (not >=) in the update ensures we keep the first coordinate that achieves the maximum quality.

The inner loop iterates over every tower. For each tower, it computes the Euclidean distance d between the candidate and the tower. If d is within the given radius, the tower contributes floor(qi / (1 + d)) to the total quality at that point. The int() call in Python truncates toward zero, which matches the floor operation for non-negative values.

After evaluating all towers for a candidate, we compare its total quality against our running best. If it is strictly greater, we update both the best quality and the best coordinate.

Visual walkthrough

Let's trace through a concrete example with towers = [[1,2,5],[2,1,7],[3,1,3]] and radius = 2. Watch how each candidate coordinate is evaluated against all towers.

The brute force approach is systematic: try every point, compute the quality, keep the best. There is no pruning, no optimization, and no cleverness needed. The small search space guarantees it finishes fast.

Complexity analysis

Time is O(51 * 51 * n) where n is the number of towers. You evaluate 2601 candidate coordinates, and for each one you check every tower. Since 51 is a constant, you could simplify this to O(n), but the constant matters in practice. With n up to 50, the total work is at most ~130,000 distance computations.

Space is O(1). You only track the current best quality and the best coordinate. No auxiliary data structures are needed.

The building blocks

1. Grid enumeration

for x in range(51):
    for y in range(51):
        # evaluate candidate (x, y)

This is the simplest form of brute force search: try every point in a 2D grid. The key is recognizing when the grid is small enough. You will see this pattern in problems like "Largest Plus Sign," "Maximal Rectangle," and any problem where coordinate bounds are explicitly small. The enumeration order also matters here because the problem asks for the lexicographically smallest coordinate on ties.

2. Euclidean distance check

d = math.sqrt((x - xi) ** 2 + (y - yi) ** 2)
if d <= radius:
    quality += int(qi / (1 + d))

The Euclidean distance formula determines whether a tower is close enough to contribute signal. The int() call floors the division result. This two-line pattern, compute distance then conditionally accumulate, appears in spatial problems like "K Closest Points to Origin" and "Minimum Time Visiting All Points."

Edge cases

Before submitting, think through these scenarios:

• Single tower at the origin: the best coordinate is the tower itself. Distance is 0, quality is qi.
• All towers out of range from each other: each coordinate can only "see" the tower it sits on, if any. The best coordinate is the tower with the highest quality.
• Multiple coordinates with the same quality: return the lexicographically smallest one. Scanning x then y in ascending order with strict > handles this automatically.
• Radius is 0: only coordinates that sit exactly on a tower receive signal. The best coordinate is the tower position with the highest qi.
• All towers at the same position: the quality at that point is the sum of all qi values. No other point can beat it if they are spaced far enough apart.

From understanding to recall

You have seen how brute force enumeration over a bounded grid solves this problem cleanly. The logic is three nested loops, a distance check, and a running maximum. But writing it correctly under time pressure means remembering the details: the range is 0 to 50 inclusive, the formula uses 1 + d in the denominator, you floor the result, and you use strict > for lexicographic tie-breaking.

Spaced repetition is how you lock these details in. You practice writing the grid enumeration, the distance computation, and the accumulation loop from memory. After a few rounds, the pattern becomes automatic. You see "bounded coordinates" in a problem statement, and the brute force template flows out without hesitation.

Related posts

• Spiral Matrix - Grid traversal with coordinate tracking
• Set Matrix Zeroes - Grid-based simulation
• Koko Eating Bananas - Search over a bounded solution space

CodeBricks breaks Coordinate With Maximum Network Quality into its grid enumeration and Euclidean distance building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a simulation problem shows up in your interview, you do not think about it. You just write it.