title: Find a line passing the maximum number of points
body: <p>I found a Google Interview question on <a href="http://www.careercup.com/question?id=56605" rel="nofollow noreferrer">CareerCup</a></p>
  
  <blockquote>
    <p>Given a 2D plane, suppose that there are around 6000 points on it. Find a line which passes the most number of points.</p>
  </blockquote>
  
  <p>Many answers there say this question is hard and involving some kind of special algorithms.</p>
  
  <p>But my view is different and maybe I am wrong.</p>
  
  <p><strong>Here is my thinking:</strong></p>
  
  <p>First I will give a axis system to the 2D plane. Hence, every point will have its unique x and y, i.e., <code>{x, y}</code>. For simplicity, we can put the axis system's <code>{0, 0}</code> as the left bottom of the whole plane and therefore every x and y are bigger than 0.</p>
  
  <p>Then I have a theory:</p>
  
  <p>If several points are on the same line, then it must be in one of the following 3 cases:</p>
  
  <ol>
  <li>their <strong><code>x</code></strong> values are the same</li>
  <li>their <strong><code>y</code></strong> values are the same</li>
  <li>their <strong><code>x/y</code></strong> or <strong><code>y/x</code></strong> values are the same. But <code>x/y</code> case is the same as <code>y/x</code> case, so let's just focus on <strong><code>x/y</code></strong>.</li>
  </ol>
  
  <p>Then I will have 3 hashtables. </p>
  
  <ol>
  <li><p>The first one (<code>hashtable-x</code>) is with key of <code>x</code>, the value is the list of points which have the same <code>x</code>; </p></li>
  <li><p>the second one (<code>hashtable-y</code>) is with the key of <code>y</code> and the value is the list of points which have the same <code>y</code>;</p></li>
  <li>the last one (<code>hashtable-x-y</code>) is with the key of <code>x/y</code> and the value is the list of points which have the same <code>x/y</code>;</li>
  </ol>
  
  <p>Then I scan the whole 6000 points, for each point, I will get its <code>x</code> from <code>hashtable-x</code>, and put the point into the value (a list) of that slot; then I will do similar things to <code>hashtable-y</code> and <code>hashtable-x-y</code>. </p>
  
  <p>Finally, i will scan all lists in the 3 hashtables and find the longest list will contains the points of the desired line.</p>
  
  <p>How do you think of my algorithm?</p>
  
  <hr>
  
  <p>Ok, here is the duplicate, sorry that I didn't find that question before.</p>
  
  <p><a href="https://stackoverflow.com/questions/4179581/what-is-the-most-efficient-algorithm-to-find-a-straight-line-that-goes-through-m">What is the most efficient algorithm to find a straight line that goes through most points?</a></p>