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

Its B. O(n log n)

25 votes

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

- $\Theta\left(n\right)$
- $\Theta\left(n\log n\right)$
- $\Theta\left(n\log^2 n\right)$
- $\Theta\left(n^2\right)$

5

Reference ->

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

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

35 votes

Best answer

Answer: **B**

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

2

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.

2

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??

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??

0

Yeah we should compare both x and y values so above solution is not correct. @Arjun Sir can u help in this one?

0

shouldn't we find gradient of all the points and then sort them up.

bcoz, gradient depends on both X & Y values.

bcoz, gradient depends on both X & Y values.

5

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

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

0

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.,

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

anyone can help.,

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).

1

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.

Thanks in advance

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

Thanks in advance

6 votes

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

4 votes

3 votes

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

**option B**

3 votes

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

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