The Gateway to Computer Science Excellence
+23 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

  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)$
in Algorithms by Boss (16.3k points)
edited by | 1.7k views

You should post this as the answer

Reference ->

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

5 Answers

+29 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.

by Boss (33.8k points)
edited by
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)

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)

@shubham shende 

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.

Thanks in advance
+6 votes
B) arrange the x coordinates in ascending order and then find the smallest difference between the neighbours.
by Loyal (6.9k points)
Y coordinates also matter in slope. (y2-y1/x2-x1)
+3 votes
I think D, for each and every pair we have to check.
by Active (4.5k points)
To see 3 points are linear or not, we can do binary search.
then we have to find theta.
+3 votes

Answer is well explained in this link:

option B

by Junior (755 points)
+3 votes
by Boss (13.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
102,232 users