LeetCode Problem 3516

Difficulty: 🟢 Easy
Topics: Math

Solution

LeetCode 3516 - Find Closest Person

Problem Understanding

This problem gives us three integers, x, y, and z, representing the positions of three people on a one-dimensional number line.

Person 1 starts at position x, Person 2 starts at position y, and Person 3 remains stationary at position z. Both Person 1 and Person 2 move directly toward Person 3 at exactly the same speed.

Since the two moving people travel at the same speed, the only factor that determines who arrives first is the distance they must travel. The person with the smaller distance to Person 3 will reach them sooner. If both distances are equal, they arrive at the same time.

The input consists of three integers:

• x: position of Person 1
• y: position of Person 2
• z: position of Person 3

The output should be:

• 1 if Person 1 reaches Person 3 first
• 2 if Person 2 reaches Person 3 first
• 0 if both reach Person 3 at the same time

The constraints are very small:

• 1 <= x, y, z <= 100

These constraints tell us that performance is not a concern. Even inefficient approaches would run instantly. However, the problem is fundamentally a simple mathematical comparison, so an optimal constant-time solution is straightforward.

Several edge cases are worth noting:

• One person may already be closer than the other.
• Both people may be exactly the same distance from Person 3.
• One person may already be standing at Person 3's position.
• Person 3 may lie between the two people or outside both of them.
• Distances must be computed using absolute values because positions can be on either side of Person 3.

Approaches

Brute Force Approach

A literal simulation approach would move both people one step at a time toward Person 3 and count how many steps each requires before reaching position z.

For example, if Person 1 starts at position 2 and Person 3 is at position 10, we could repeatedly increment Person 1's position until it reaches 10, counting the number of moves performed. We could do the same for Person 2 and then compare the totals.

This approach produces the correct answer because the number of simulated moves equals the distance traveled. However, it performs unnecessary work because the number of steps is already known mathematically.

Key Insight

Since both people move at the same speed, arrival time is proportional to distance.

The distance from Person 1 to Person 3 is:

$$|x-z|$$

The distance from Person 2 to Person 3 is:

$$|y-z|$$

We simply compare these two distances:

• If |x-z| < |y-z|, Person 1 arrives first.
• If |x-z| > |y-z|, Person 2 arrives first.
• Otherwise, both arrive simultaneously.

This eliminates all simulation and gives an immediate answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(1)	Simulates movement step by step, where d is the larger distance
Optimal	O(1)	O(1)	Directly compares absolute distances

Algorithm Walkthrough

1. Compute the distance from Person 1 to Person 3 using abs(x - z).
2. Compute the distance from Person 2 to Person 3 using abs(y - z).
3. Compare the two distances.
4. If the first distance is smaller, return 1 because Person 1 reaches Person 3 sooner.
5. If the second distance is smaller, return 2 because Person 2 reaches Person 3 sooner.
6. If the distances are equal, return 0 because both arrive at the same time.

Why it works

The key property is that both people travel at the same speed. When speed is identical, the person who travels the shorter distance always arrives first. The absolute difference between positions gives the exact distance on a number line, regardless of direction. Therefore, comparing |x-z| and |y-z| is equivalent to comparing arrival times, guaranteeing a correct result.

Problem Understanding

The problem asks us to determine which of two people, Person 1 or Person 2, reaches a stationary Person 3 first on a one-dimensional number line. The input consists of three integers x, y, and z, where x and y are the starting positions of Person 1 and Person 2, respectively, and z is the position of Person 3. Both moving persons travel at the same constant speed toward Person 3. The output should indicate who arrives first: return 1 if Person 1 arrives first, 2 if Person 2 arrives first, or 0 if both arrive simultaneously.

The constraints 1 <= x, y, z <= 100 indicate that the input values are small integers, so there is no risk of integer overflow or performance issues with direct computation. Important edge cases include situations where both persons start equidistant from Person 3, or when one or both persons start at the same position as Person 3.

Approaches

The brute-force approach would simulate movement step by step, incrementing the positions of Person 1 and Person 2 toward Person 3 until one reaches it. While this guarantees correctness, it is unnecessary because the relative arrival times are determined purely by the initial distances to Person 3. Even though the problem constraints make brute-force feasible, this approach introduces extra computation and complexity.

The optimal approach relies on a simple mathematical observation: because both persons move at the same speed, the time taken to reach Person 3 is directly proportional to the absolute distance between their starting positions and z. Therefore, computing abs(x - z) and abs(y - z) suffices to determine the result. This observation reduces the problem to a constant-time calculation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d) where d = max(	x-z	,
Optimal	O(1)	O(1)	Compute absolute distances directly and compare

Algorithm Walkthrough

1. Compute the absolute distance d1 between Person 1 and Person 3: d1 = |x - z|. This represents the number of units Person 1 must move to reach Person 3.
2. Compute the absolute distance d2 between Person 2 and Person 3: d2 = |y - z|.
3. Compare d1 and d2:

• If d1 < d2, return 1 since Person 1 is closer and arrives first.
• If d1 > d2, return 2 since Person 2 is closer and arrives first.
• If d1 == d2, return 0 since both arrive simultaneously.

Why it works: The invariant is that both persons move at the same speed. Consequently, the person with the smaller distance to Person 3 will arrive first. The comparison of absolute distances fully captures this logic without any need for iterative simulation.

Python Solution

class Solution:
    def findClosest(self, x: int, y: int, z: int) -> int:
        distance1 = abs(x - z)
        distance2 = abs(y - z)

        if distance1 < distance2:
            return 1

        if distance2 < distance1:
            return 2

        return 0

The implementation follows the algorithm directly.

First, it computes the distance from each person to Person 3 using Python's built-in abs() function. These values represent how far each person must travel.

Next, it compares the two distances. If Person 1's distance is smaller, the method returns 1. If Person 2's distance is smaller, it returns 2.

If neither distance is smaller, they must be equal, so the method returns 0.

Because only a few arithmetic operations and comparisons are performed, the solution runs in constant time and uses constant space. d1 = abs(x - z) d2 = abs(y - z) if d1 < d2: return 1 elif d1 > d2: return 2 else: return 0

In this implementation, we first compute the distances `d1` and `d2` using Python's built-in `abs()` function. We then perform a simple comparison to determine which person arrives first. Each conditional directly corresponds to the algorithmic step above, ensuring correctness and efficiency.

## Go Solution

```go
func findClosest(x int, y int, z int) int {
	distance1 := x - z
	if distance1 < 0 {
		distance1 = -distance1
	}

	distance2 := y - z
	if distance2 < 0 {
		distance2 = -distance2
	}

	if distance1 < distance2 {
		return 1
	}

	if distance2 < distance1 {
		return 2
	}

	return 0
}

The Go version follows the same logic as the Python solution. Since Go does not provide a built-in integer abs() function in the standard language primitives, the implementation manually converts negative differences into positive values.

No special handling for overflow is required because the constraints are very small. The solution still uses constant time and constant space.

Worked Examples

Example 1

Input: x = 2, y = 7, z = 4

Compute the distances:

Variable	Value
distance1	abs(2 - 4) = 2
distance2	abs(7 - 4) = 3

Comparison:

Check	Result
distance1 < distance2	2 < 3, true

Return:

1

Person 1 arrives first.

Example 2

Input: x = 2, y = 5, z = 6

Compute the distances:

Variable	Value
distance1	abs(2 - 6) = 4
distance2	abs(5 - 6) = 1

Comparison:

Check	Result
distance1 < distance2	4 < 1, false
distance2 < distance1	1 < 4, true

Return:

2

Person 2 arrives first.

Example 3

Input: x = 1, y = 5, z = 3

Compute the distances:

Variable	Value
distance1	abs(1 - 3) = 2
distance2	abs(5 - 3) = 2

Comparison:

Check	Result
distance1 < distance2	false
distance2 < distance1	false

Return:

0

Both people arrive simultaneously. d1 := x - z if d1 < 0 { d1 = -d1 } d2 := y - z if d2 < 0 { d2 = -d2 } if d1 < d2 { return 1 } else if d1 > d2 { return 2 } else { return 0 } }

The Go implementation mirrors the Python logic. Since Go lacks a built-in `abs()` function for integers in the core language, we manually compute the absolute values using a conditional check. All other steps, including the comparisons and return statements, follow the algorithm exactly.

## Worked Examples

**Example 1:** `x = 2, y = 7, z = 4`

| Variable | Computation | Value |
| --- | --- | --- |
| d1 |  | 2 - 4 |
| d2 |  | 7 - 4 |
| Result | d1 < d2 → return 1 | 1 |

**Example 2:** `x = 2, y = 5, z = 6`

| Variable | Computation | Value |
| --- | --- | --- |
| d1 |  | 2 - 6 |
| d2 |  | 5 - 6 |
| Result | d1 > d2 → return 2 | 2 |

**Example 3:** `x = 1, y = 5, z = 3`

| Variable | Computation | Value |
| --- | --- | --- |
| d1 |  | 1 - 3 |
| d2 |  | 5 - 3 |
| Result | d1 == d2 → return 0 | 0 |

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(1) | Only a few arithmetic operations and comparisons are performed |
| Space | O(1) | No extra data structures are allocated |

The algorithm computes two absolute differences and performs at most two comparisons. The amount of work never changes regardless of the input values, so the running time is constant. Similarly, only a fixed number of variables are used, giving constant auxiliary space usage.
| Time | O(1) | Computing absolute differences and performing comparisons are constant-time operations |
| Space | O(1) | Only two integer variables are used for distance calculations |

The reasoning is straightforward: no loops or recursive calls are necessary, and the number of variables does not scale with input size.

## Test Cases

sol = Solution()

assert sol.findClosest(2, 7, 4) == 1 # Person 1 is closer assert sol.findClosest(2, 5, 6) == 2 # Person 2 is closer assert sol.findClosest(1, 5, 3) == 0 # Equal distances

assert sol.findClosest(5, 10, 5) == 1 # Person 1 already at target assert sol.findClosest(10, 5, 5) == 2 # Person 2 already at target

assert sol.findClosest(1, 100, 50) == 0 # Symmetric distances assert sol.findClosest(1, 3, 2) == 0 # Equal distance on both sides

assert sol.findClosest(4, 8, 6) == 0 # Both two units away assert sol.findClosest(3, 9, 5) == 1 # Person 1 closer assert sol.findClosest(9, 3, 5) == 2 # Person 2 closer

assert sol.findClosest(1, 2, 100) == 2 # Target far to the right assert sol.findClosest(100, 99, 1) == 2 # Target far to the left

assert sol.findClosest(1, 100, 1) == 1 # Minimum boundary position assert sol.findClosest(100, 1, 100) == 1 # Maximum boundary position

### Test Summary

| Test | Why |
| --- | --- |
| (2, 7, 4) | Provided example where Person 1 wins |
| (2, 5, 6) | Provided example where Person 2 wins |
| (1, 5, 3) | Provided example with a tie |
| (5, 10, 5) | Person 1 starts at the destination |
| (10, 5, 5) | Person 2 starts at the destination |
| (1, 100, 50) | Equal distances with large separation |
| (1, 3, 2) | Symmetric tie case |
| (4, 8, 6) | Equal distances on opposite sides |
| (3, 9, 5) | Person 1 slightly closer |
| (9, 3, 5) | Person 2 slightly closer |
| (1, 2, 100) | Destination far to the right |
| (100, 99, 1) | Destination far to the left |
| (1, 100, 1) | Boundary value with Person 1 at target |
| (100, 1, 100) | Boundary value with Person 1 at target |

## Edge Cases

### Equal Distances

A common source of mistakes is forgetting the tie condition. For example, when `x = 1`, `y = 5`, and `z = 3`, both people are exactly two units away. A solution that only checks which distance is smaller could incorrectly return one of the people instead of returning `0`. The implementation explicitly checks both inequality cases and returns `0` when neither is true.

### One Person Already at the Destination

If one person's position already matches `z`, their distance is zero. For example, `x = 5`, `y = 10`, and `z = 5`. Person 1 requires no movement and should immediately be considered the first to arrive. Because the solution uses absolute distances, a distance of zero is naturally handled and correctly wins the comparison.

### Person 3 Outside Both Starting Positions

Person 3 does not have to lie between the two moving people. For example, `x = 1`, `y = 2`, and `z = 100`. Both people must move in the same direction, but the relevant quantity is still distance. Using absolute differences ensures the algorithm remains correct regardless of where Person 3 is located on the number line.

### Symmetric Positions Around Person 3

When the two people are equally far from Person 3 but on opposite sides, such as `x = 1`, `y = 100`, and `z = 50`, both travel the same distance even though they move in different directions. The use of absolute values removes directional effects and correctly identifies this as a tie.
# Provided examples
assert Solution().findClosest(2, 7, 4) == 1  # Person 1 closer
assert Solution().findClosest(2, 5, 6) == 2  # Person 2 closer
assert Solution().findClosest(1, 5, 3) == 0  # Both equidistant

# Boundary tests
assert Solution().findClosest(1, 100, 50) == 1  # Person 1 closer at lower boundary
assert Solution().findClosest(100, 1, 50) == 2  # Person 2 closer at lower boundary
assert Solution().findClosest(50, 50, 50) == 0  # Both start at Person 3's position
assert Solution().findClosest(1, 2, 1) == 1  # Person 1 at same position as Person 3
assert Solution().findClosest(2, 1, 1) == 2  # Person 2 at same position as Person 3

Test	Why
2,7,4	Basic case with Person 1 closer
2,5,6	Basic case with Person 2 closer
1,5,3	Equidistant case
1,100,50	Boundary condition with min input
100,1,50	Boundary condition with max input
50,50,50	Both start at target
1,2,1	Person 1 already at target
2,1,1	Person 2 already at target

Edge Cases

The first edge case occurs when both Person 1 and Person 2 are equidistant from Person 3. This could happen with symmetric positions relative to z. If handled incorrectly, a naive comparison might favor one arbitrarily, but using an equality check ensures the function returns 0.

The second edge case occurs when one of the persons starts exactly at z. The absolute distance computation correctly yields zero, guaranteeing immediate arrival. The algorithm properly returns that this person reaches first unless the other person is also at z.

The third edge case is at the boundaries of the input range (1 and 100). Ensuring correct handling of minimum and maximum values avoids off-by-one errors. Since we rely only on arithmetic differences and not iteration, the implementation is robust for these extreme values.