1
$\begingroup$

While solving This algorithm problem I was unable to come up with condition for the collision to occur ( other than the naive O(n^2) algorithm ) on reading the explanation they say

Let’s deepen the observation. For a set of people with the same y coordinate, let’s consider “in what condition does a collision occurs?” Then we can see that a collision occurs if and only if the following two people collides: the leftmost person facing right, and the rightmost person facing left. In other words, among the people with the same y coordinate, all the people except for the two mentioned above is unimportant.

I am unable to understand how the two people who are at extremes of some y=k satisfy the condition it is quite possible that the two at extremes of this y=k face the same direction and there could exist some pair in between these extremes that satisfy the condition, can you help me understand if I'm wrong in understanding the solution?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Your concern is legitimate.

However,

  • "the leftmost person facing right" means the leftmost person among all persons who face right.
  • "the rightmost person facing left" means the rightmost person among all persons who face left.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Yes I came to realize that and it worked, thanks for the clarification. $\endgroup$
    – Pawan Nirpal
    Mar 19, 2022 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.