The Gateway to Computer Science Excellence
+23 votes
1.7k 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)$
in Algorithms by Boss (16.3k points)
edited by | 1.7k views
+5
0
@swagnikd

You should post this as the answer
0
NICE ARTICLE.
+5

Reference ->

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

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

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

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

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

by Boss (33.8k points)
edited by
+6
Gradient will be max , when y2-y1 will be max , why are u not considering this fact??
+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??
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.
+4
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))
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.,
+1
Why will it take o(n) to find min difference... As we already sorted the points.. Should be o(1)
+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).

+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
+6 votes
B) arrange the x coordinates in ascending order and then find the smallest difference between the neighbours.
by Loyal (6.9k points)
+2
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)
0
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:
https://www.careercup.com/question?id=4787065684230144

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
195,856 comments
102,232 users