Find Closest Person

Difficulty: Easy | Acceptance: 89.00% | Paid: No Topics: Math

You are given a 0-indexed integer array positions where positions[i] represents the position of the i-th person on a number line. You are standing at position yourPosition.

Return the minimum distance between you and any person.

If the array positions is empty, return -1.

• Examples
• Constraints
• Approach 1: Linear Scan
• Approach 2: Sorting and Binary Search

Examples

Input: positions = [1, 2, 3], yourPosition = 2
Output: 0
Explanation: You are standing at position 2, which is exactly where a person is located.

Input: positions = [1, 5], yourPosition = 3
Output: 2
Explanation: The closest person is at position 1 (distance 2) or position 5 (distance 2).

Input: positions = [10], yourPosition = 0
Output: 10
Explanation: The only person is at position 10.

Constraints

1 <= positions.length <= 10⁵
-10⁹ <= positions[i] <= 10⁹
-10⁹ <= yourPosition <= 10⁹

Approach 1: Linear Scan

Intuition Since we need to find the minimum distance, we can iterate through the array once, calculating the absolute difference between each person’s position and our position, keeping track of the smallest value found.

Steps

• Initialize min_dist to infinity.
• Iterate through each position in the array.
• Calculate the absolute difference between the current position and yourPosition.
• Update min_dist if the current difference is smaller.
• Return min_dist.

class Solution:
    def findClosestPerson(self, positions: list[int], yourPosition: int) -> int:
        if not positions:
            return -1
        min_dist = float('inf')
        for p in positions:
            dist = abs(p - yourPosition)
            if dist < min_dist:
                min_dist = dist
        return min_dist

Complexity

• Time: O(N)
• Space: O(1)
• Notes: Most efficient for a single query on an unsorted array.

Approach 2: Sorting and Binary Search

Intuition If the array were sorted, we could use binary search to find the insertion point of yourPosition. The closest person would either be at that insertion point or the one immediately before it.

Steps

• Sort the positions array.
• Perform a binary search to find the index where yourPosition would be inserted.
• Check the elements at the found index and the previous index (if they exist).
• Return the minimum distance among the neighbors.

class Solution:
    def findClosestPerson(self, positions: list[int], yourPosition: int) -> int:
        if not positions:
            return -1
        positions.sort()
        import bisect
        idx = bisect.bisect_left(positions, yourPosition)
        if idx == 0:
            return abs(positions[0] - yourPosition)
        if idx == len(positions):
            return abs(positions[-1] - yourPosition)
        return min(abs(positions[idx] - yourPosition), abs(positions[idx-1] - yourPosition))

Complexity

• Time: O(N log N)
• Space: O(1) or O(N) depending on the sorting implementation.
• Notes: Useful if multiple queries are made on the same static array, but slower for a single query due to sorting.