Coordinate With Maximum Network Quality - Practice Coding Problems

Coordinate With Maximum Network Quality - Problem

Array Enumeration Medium

You are given an array of network towers towers, where towers[i] = [xi, yi, qi] denotes the ith network tower with location (xi, yi) and quality factor qi. All the coordinates are integral coordinates on the X-Y plane, and the distance between the two coordinates is the Euclidean distance.

You are also given an integer radius where a tower is reachable if the distance is less than or equal to radius. Outside that distance, the signal becomes garbled, and the tower is not reachable.

The signal quality of the ith tower at a coordinate (x, y) is calculated with the formula ⌊qi / (1 + d)⌋, where d is the distance between the tower and the coordinate. The network quality at a coordinate is the sum of the signal qualities from all the reachable towers.

Return the array [cx, cy] representing the integral coordinate (cx, cy) where the network quality is maximum. If there are multiple coordinates with the same network quality, return the lexicographically minimum non-negative coordinate.

Note: A coordinate (x1, y1) is lexicographically smaller than (x2, y2) if either: x1 < x2, or x1 == x2 and y1 < y2.

Input & Output

Example 1 — Basic Case

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

› Output: [2,1]

💡 Note: At coordinate (2,1): Tower1 distance=√2≈1.41, quality=⌊5/(1+1.41)⌋=2. Tower2 distance=0, quality=⌊7/(1+0)⌋=7. Tower3 distance=1, quality=⌊9/(1+1)⌋=4. Total=2+7+4=13, which is maximum.

Example 2 — Multiple Optimal Points

$ Input: towers = [[23,11,21]], radius = 9

› Output: [23,11]

💡 Note: Only one tower, so the coordinate at the tower location (23,11) gives maximum quality: ⌊21/(1+0)⌋=21.

Example 3 — No Signal Case

$ Input: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 0

› Output: [1,2]

💡 Note: With radius=0, only coordinates exactly at tower locations get signal. Tower at (1,2) has highest quality 13, so return [1,2].

Constraints

1 ≤ towers.length ≤ 50
towers[i].length == 3
0 ≤ xi, yi, qi ≤ 50
1 ≤ radius ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Network towers with positions and quality factors, plus radius

Process

Calculate signal quality at each coordinate using distance formula

Output

Coordinate with maximum total network quality

Key Takeaway

🎯 Key Insight: The optimal coordinate is usually close to high-quality towers, so we can optimize by only checking coordinates within tower coverage areas.

Asked in

G Google 12 a Amazon 8 🍎 Apple 6

The key insight is to systematically check coordinates that can receive signals from towers. The brute force approach checks all coordinates in a bounded area, while the optimized approach only checks coordinates within the radius of at least one tower. Best approach: Optimized with Time: O(T×R² + C×T), Space: O(C).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Search - Focus on Tower Vicinity	O(T × R² + C × T)	O(C)	Limit search area to coordinates near towers for better efficiency
Brute Force - Check All Coordinates	O(R² × T)	O(1)	Check every possible coordinate in a reasonable range around the towers

Optimized Search - Focus on Tower Vicinity — Algorithm Steps

Step 1: For each tower, generate all coordinates within its radius
Step 2: Collect unique candidate coordinates
Step 3: Calculate network quality only for candidate coordinates

Visualization

Tap to expand

Step-by-Step Walkthrough

Tower Coverage

Mark all coordinates within radius of each tower

Candidate Set

Collect unique coordinates that are reachable

Quality Check

Calculate network quality only for candidates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_CANDIDATES 10000

struct Coordinate {
    int x, y;
};

int* solution(int towers[][3], int towerCount, int radius) {
    struct Coordinate candidates[MAX_CANDIDATES];
    int candidateCount = 0;
    
    // Generate candidate coordinates within radius of each tower
    for (int i = 0; i < towerCount; i++) {
        int tx = towers[i][0], ty = towers[i][1];
        
        // Check all coordinates in square around tower
        for (int x = (tx - radius > 0) ? tx - radius : 0; x <= tx + radius; x++) {
            for (int y = (ty - radius > 0) ? ty - radius : 0; y <= ty + radius; y++) {
                // Only add if actually within radius
                double distance = sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));
                if (distance <= radius) {
                    // Check if already exists
                    int exists = 0;
                    for (int j = 0; j < candidateCount; j++) {
                        if (candidates[j].x == x && candidates[j].y == y) {
                            exists = 1;
                            break;
                        }
                    }
                    if (!exists && candidateCount < MAX_CANDIDATES) {
                        candidates[candidateCount].x = x;
                        candidates[candidateCount].y = y;
                        candidateCount++;
                    }
                }
            }
        }
    }
    
    // If no candidates, return [0, 0]
    if (candidateCount == 0) {
        int* result = malloc(2 * sizeof(int));
        result[0] = 0; result[1] = 0;
        return result;
    }
    
    long long bestQuality = -1;
    int* bestCoord = malloc(2 * sizeof(int));
    bestCoord[0] = 0; bestCoord[1] = 0;
    
    // Check quality at each candidate coordinate
    for (int i = 0; i < candidateCount; i++) {
        int x = candidates[i].x, y = candidates[i].y;
        long long quality = 0;
        
        // Calculate quality from all towers
        for (int j = 0; j < towerCount; j++) {
            int tx = towers[j][0], ty = towers[j][1], tq = towers[j][2];
            double distance = sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));
            
            if (distance <= radius) {
                quality += (long long)(tq / (1 + distance));
            }
        }
        
        // Update best coordinate (lexicographically smallest)
        if (quality > bestQuality || (quality == bestQuality && (x < bestCoord[0] || (x == bestCoord[0] && y < bestCoord[1])))) {
            bestQuality = quality;
            bestCoord[0] = x;
            bestCoord[1] = y;
        }
    }
    
    return bestCoord;
}

int main() {
    // Simple parsing for demo
    int towers[50][3];
    int towerCount = 2;
    towers[0][0] = 1; towers[0][1] = 2; towers[0][2] = 5;
    towers[1][0] = 2; towers[1][1] = 1; towers[1][2] = 7;
    int radius = 2;
    
    int* result = solution(towers, towerCount, radius);
    printf("[%d,%d]\n", result[0], result[1]);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(T × R² + C × T)

T towers × R² coordinates per tower radius + C unique candidates × T towers

✓ Linear Growth

Space Complexity

O(C)

Set to store C unique candidate coordinates

✓ Linear Space

8.9K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Search - Focus on Tower Vicinity — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler