Find Closest Person
EasyPrompt
You are given three integers x, y, and z, representing the positions of three people on a number line:
xis the position of Person 1.yis the position of Person 2.zis the position of Person 3, who does not move.
Both Person 1 and Person 2 move toward Person 3 at the same speed.
Determine which person reaches Person 3 first:
- Return 1 if Person 1 arrives first.
- Return 2 if Person 2 arrives first.
- Return 0 if both arrive at the same time.
Return the result accordingly.
Example 1:
Input: x = 2, y = 7, z = 4
Output: 1
Explanation:
- Person 1 is at position 2 and can reach Person 3 (at position 4) in 2 steps.
- Person 2 is at position 7 and can reach Person 3 in 3 steps.
Since Person 1 reaches Person 3 first, the output is 1.
Example 2:
Input: x = 2, y = 5, z = 6
Output: 2
Explanation:
- Person 1 is at position 2 and can reach Person 3 (at position 6) in 4 steps.
- Person 2 is at position 5 and can reach Person 3 in 1 step.
Since Person 2 reaches Person 3 first, the output is 2.
Example 3:
Input: x = 1, y = 5, z = 3
Output: 0
Explanation:
- Person 1 is at position 1 and can reach Person 3 (at position 3) in 2 steps.
- Person 2 is at position 5 and can reach Person 3 in 2 steps.
Since both Person 1 and Person 2 reach Person 3 at the same time, the output is 0.
Constraints:
1 <= x, y, z <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the step-by-step movement of Person 1 and Person 2 towards Person 3. We use a loop that continues until one or both people reach Person 3's position. In each iteration of the loop, we update the positions of Person 1 and Person 2, moving them one unit closer to Person 3, and check if they have arrived.
Algorithm
- Initialize a loop that runs indefinitely.
- In each iteration, check if Person 1 (
x) or Person 2 (y) has reached Person 3 (z). - If both have reached
zin the same step, return0. - If only Person 1 has reached
z, return1. - If only Person 2 has reached
z, return2. - If neither has reached, move both Person 1 and Person 2 one unit closer to
z.- If
x < z, incrementx. Ifx > z, decrementx. - If
y < z, incrementy. Ify > z, decrementy.
- If
- Repeat the process.
Walkthrough
This method literally simulates the physical movement described in the problem. We treat each iteration of a loop as a single unit of time. In each time unit, both Person 1 and Person 2 move one step closer to Person 3. We continuously check their positions. The first person to have their position equal to z is the winner. If both positions become equal to z in the same time unit, it's a tie.
class Solution { public int findClosestPerson(int x, int y, int z) { while (true) { boolean person1Reached = (x == z); boolean person2Reached = (y == z); if (person1Reached && person2Reached) { return 0; // Both reached at the same time } if (person1Reached) { return 1; // Person 1 reached first } if (person2Reached) { return 2; // Person 2 reached first } // Move Person 1 one step closer to z if (x < z) { x++; } else if (x > z) { x--; } // Move Person 2 one step closer to z if (y < z) { y++; } else if (y > z) { y--; } } }}Complexity
Time
O(max(|x-z|, |y-z|)) - The loop runs for a number of iterations equal to the distance of the person who is farther away from `z`. For the given constraints, this is at most 99 iterations.
Space
O(1) - We only use a few variables to store the positions, and the space required does not grow with the input values.
Trade-offs
Pros
It's a very literal interpretation of the problem statement.
Easy to conceptualize for beginners who think in terms of discrete time steps.
Cons
Highly inefficient as it performs unnecessary step-by-step calculations.
The code is more complex and longer than necessary.
Scales poorly if the distances are very large.
This is the most efficient approach. Since both people move at the same speed, the person who reaches Person 3 first is simply the one who is initially closer. The time to travel is directly proportional to the distance. Therefore, we can solve the problem by calculating the initial distances of Person 1 and Person 2 from Person 3 and comparing them.
Algorithm
- Calculate the distance between Person 1 and Person 3:
dist1 = |x - z|. - Calculate the distance between Person 2 and Person 3:
dist2 = |y - z|. - Compare the two distances:
- If
dist1 < dist2, return1. - If
dist2 < dist1, return2. - If
dist1 == dist2, return0.
- If
Walkthrough
The core of the problem is to determine who is closer to position z. The distance between two points a and b on a number line is the absolute value of their difference, |a - b|. We can use the Math.abs() function for this.
First, we calculate the distance for Person 1 to reach Person 3, which is dist1 = Math.abs(x - z). Then, we do the same for Person 2, dist2 = Math.abs(y - z). Finally, we compare these two distances to determine the result. This avoids any loops or simulation, leading to a constant time solution.
class Solution { public int findClosestPerson(int x, int y, int z) { // Calculate the absolute distance of Person 1 from Person 3 int dist1 = Math.abs(x - z); // Calculate the absolute distance of Person 2 from Person 3 int dist2 = Math.abs(y - z); // Compare the distances to find the result if (dist1 < dist2) { return 1; // Person 1 is closer } else if (dist2 < dist1) { return 2; // Person 2 is closer } else { return 0; // Both are at the same distance } }}Complexity
Time
O(1) - The solution involves a fixed number of arithmetic operations (subtraction, absolute value) and comparisons, regardless of the input values.
Space
O(1) - We only use a couple of extra variables to store the calculated distances. The space used is constant and does not depend on the input values.
Trade-offs
Pros
Optimal in terms of both time and space complexity.
The code is simple, concise, and easy to understand.
Directly addresses the core logic of the problem without unnecessary simulation.
Cons
There are no significant drawbacks to this approach; it is optimal.
Solutions
Solution
class Solution {public int findClosest(int x, int y, int z) { int a = Math.abs(x - z); int b = Math.abs(y - z); return a == b ? 0 : (a < b ? 1 : 2); }}class Solution {public: int findClosest(int x, int y, int z) { int a = abs(x - z); int b = abs(y - z); return a == b ? 0 : (a < b ? 1 : 2); }};class Solution: def findClosest(self, x: int, y: int, z: int) -> int: a = abs(x - z) b = abs(y - z) return 0 if a == b else (1 if a < b else 2)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.