algoadvance

Leetcode 1779. Find Nearest Point That Has the Same X or Y Coordinate

Problem Statement

You are given two integers, x and y, which represent your current location on a Cartesian grid. You are also given an array points where each points[i] = [a_i, b_i] represents that a point exists at (a_i, b_i) on the grid. A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.

Return the index (0-based) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the smallest index. If there are no valid points, return -1.

The Manhattan distance between two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

Clarifying Questions

  1. Can the points array be empty?
    • Yes, it’s possible for the points array to be empty.
  2. Are there any constraints on the coordinates?
    • Conventional constraints associated with arrays and integer values usually apply. Specific problem constraints from the prompt should be taken into account.
  3. Is it guaranteed the points array contains at least one valid point?
    • No, it’s not guaranteed. If no valid points exist, the function should return -1.

Strategy

  1. Initialize Variables:
    • Initialize a variable to store the minimum distance found so far.
    • Initialize a variable to store the index of the closest valid point.
  2. Iterate Through Points:
    • For each point, check if it shares the same x or y coordinate with the current location.
    • If valid, calculate the Manhattan distance.
    • If this distance is smaller than the current minimum distance, update the minimum distance and the index.
  3. Return Result:
    • After iterating through all points, return the stored index of the closest valid point. If no valid point was found, return -1.

Code

#include <vector>
#include <cmath>
#include <climits>

class Solution {
public:
    int nearestValidPoint(int x, int y, std::vector<std::vector<int>>& points) {
        int minDistance = INT_MAX;
        int nearestIndex = -1;

        for (int i = 0; i < points.size(); ++i) {
            int a = points[i][0];
            int b = points[i][1];

            if (a == x || b == y) {
                int distance = std::abs(x - a) + std::abs(y - b);
                if (distance < minDistance) {
                    minDistance = distance;
                    nearestIndex = i;
                }
            }
        }
        
        return nearestIndex;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the number of points in the points array. This is because we iterate through each point exactly once, performing a constant amount of work for each point (checking coordinates and calculating Manhattan distance).

The space complexity is O(1) as we only use a fixed amount of extra space regardless of the size of the input.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI