Scale Engineer

Find Closest Person

Easy
#3128Time: 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.
Patterns
Math

Prompt

You are given three integers x, y, and z, representing the positions of three people on a number line:

  • x is the position of Person 1.
  • y is the position of Person 2.
  • z is 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 z in the same step, return 0.
  • If only Person 1 has reached z, return 1.
  • If only Person 2 has reached z, return 2.
  • If neither has reached, move both Person 1 and Person 2 one unit closer to z.
    • If x < z, increment x. If x > z, decrement x.
    • If y < z, increment y. If y > z, decrement y.
  • 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.

Solutions

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);  }}

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.

← Previous

Previous problem

Next →

Next problem