4,437 views

Let $P_1, P_2,\dots , P_n$be $n$ points in the $xy$-plane such that no three of them are collinear. For every pair of points $P_i$ and $P_j$, let $L_{ij}$ be the line passing through them. Let $L_{ab}$ be the line with the steepest gradient among all $n(n -1)/2$ lines.

The time complexity of the best algorithm for finding $P_a$ and $P_b$ is

1. $\Theta\left(n\right)$
2. $\Theta\left(n\log n\right)$
3. $\Theta\left(n\log^2 n\right)$
4. $\Theta\left(n^2\right)$

NICE ARTICLE.

Reference ->

https://stackoverflow.com/questions/8222108/max-slope-from-set-of-points

On above link take a look on Mcdowella's explanation.

We need to use stable sorts like Merge sort ... Correct me if i am wrong ...

Gradient $= y_2 - y_1 / x_2 - x_1$

For gradient to be maximum $x_2 - x_1$ should be minimum. So, sort the points (in $\Theta(n\log n)$ time) according to $x$ coordinate and find the minimum difference between them (in $\Theta(n)$ time).

Best complexity: $\Theta(n\log n +n)$ which leads to B.

https://www.careercup.com/question?id=4787065684230144

https://stackoverflow.com/questions/8222108/max-slope-from-set-of-points

Gradient will be max , when y2-y1 will be max , why are u not considering this fact??
Himanshu1 is right. Rather than comparing x distances we should compare slope of consecutive points. Otherwise for example (1,1), (2,2), (4,10) will give us wrong answer. Although I don't know how to prove this.
does it work for cordinates (1,1) (2,3) (4,8) (6,9)

it remains same after sorting
then we get min difference of x cordinates at (1,1) (2,3)
We get slope of 2

But highest slope is for (2,3) (4,8) which is 2.5??
Yeah we should compare both x and y values so above solution is not correct. @Arjun Sir can u help in this one?
shouldn't we find gradient of all the points and then sort them up.

bcoz, gradient depends on both X & Y values.
x coordinate and y coordinate both will be arrange in ascending or descending order ,it will take o(n(logn))..

now find minimum of (Xi+1 - Xi) and maximum of (Yi+1 - Yi) (it will take 0(n)) then slope will be maximum

so total time = 0(n(logn)) + 0(n)

=0(n(logn))
to solve and understand this type of question , what kind of basic information need to know or necessary ,

bcoz of i am nothing able to understand this question and answer.,  this question what saying,?

anyone can help.,
Why will it take o(n) to find min difference... As we already sorted the points.. Should be o(1)

actually we need to check if any two point gives diferredif "0" ( x- coordinates ) so that gradient will be "infinity" , for that we need O(n).

I have a basic doubt, if we want the gradient to be minimum, then we want x2-x1 as max, so instead of sorting entire array in nlogn time, why can't we take the max and min values of x which will take O(n) time, then difference between this max and min x value will always be max. Similarly we can get first 2 min elements of Y in O(n) time. What crucial part I'm missing I'm not getting

I went through the mentioned links however it didn't help to solve this query.

Why max and min values of x? We want x1 and x2 to be as close as possible, so we have to sort it first, then find minimum difference between consecutive points.
even the part 1 of this combined question tells that only adjacent points can give max. slope.so sorting the points on the basis of x axis is perfect; it takes O(nlogn).(we must keep separate array for y coordinate too and arrange it as per x, it would be later used.this wont increase time complexity as its done simultaneously)

but now, instead of taking just min. of adjacent x coordinates, we must find “slope” between adjacent points and keep a variable MAX. which can be updated as we traverse the entire array. this is mandatory because we may take 2 points whose difference in x might not be minimum amongst other pairs, still  its difference in y is so big as to give a higher slope).this will still take O(n).

hence,TC=O(nlogn +n)=O(nlogn).

I think we need to consider both $x$ and $y$ coordinates. Here is a counter-example of why the answer could be wrong.

As per the answer, the point $(A,B)$ has the lowest difference in $x$ coordinates, however the slope of $(B,C)$ is highest among all the $^3C_2$ lines.

If it asked to find the gentle slop then (x2 – x1) should be maximum.

So in that case we can find the minimum and maximum in O(n).

So time complexity will be O(n).
edited

samarpita

As the list is sorted considering the x co-ordinates  then if we take first two element it will have the minimum difference in constant time and thus O(1).

is this correct?

@Pranavpurkar no it will be O(n), if the points are sorted in ascending order acc to x- coordinate.

Just take sample example:

(1,2),(7,5),(9,6),(14,9)

So, acc to this first two minimums are 1 and 7 and after the subtraction, it will be 6.

Then you will consider between 7 and 9 and after the subtraction, it will be 2.

Then you will consider between 9 and 14 and after the subtraction, it will be 5.

For, the steepest slope the difference between the x-coordinate should be minimum and that is the line between (7,5) and (9,6).

So, to find that we have to scan the entire x-coordinate. Therefore, it will be O(n).

YES ! got it now.

Thanks :)

B) arrange the x coordinates in ascending order and then find the smallest difference between the neighbours.

### 1 comment

Y coordinates also matter in slope. (y2-y1/x2-x1)
I think D, for each and every pair we have to check.

### 1 comment

To see 3 points are linear or not, we can do binary search.
then we have to find theta.

Answer is well explained in this link:
https://www.careercup.com/question?id=4787065684230144

option B

by