Hit most balloons Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/4e75764f8f1638eb4f1c5478ca1986043e15e39a/1#

(It is also the problem of the day for 28-02-2022)

Solution:

 int max=0;

       for(int i=0;i<n;i++){

           HashMap<Double,Integer>map=new HashMap<Double,Integer>();

             int x1=arr[i][0];

              int y1=arr[i][1];

              int count=0;

           for(int j=0;j<n;j++){

               int x2=arr[j][0];

               int y2=arr[j][1];

               

               if(x1==x2 && y1==y2){

                   //same point

                   count++;

                   //continue;

               }

               else{

                   double tan=(y2-y1)/(1.0*(x2-x1));

                   if(map.containsKey(tan)){

                       map.put(tan,map.get(tan)+1);

                   }

                   else{

                       map.put(tan,1);

                   }

               }

               

           }

           for(double a:map.keySet()){

               max=Integer.max(max,map.get(a)+count);

           }

       }

       return max;

TIME COMPLEXITY: O(N*N)[Nested Loops][GFG Time: 0.7/17.1]

SPACE COMPLEXITY: O(N*N)[2D array is used]

AUXILIARY SPACE: O(N)[Usage Of Map]

TOTAL TEST CASES: 152

Approach:

The approach used here is to find out the slopes of all the points with respect to one fixed point and count the number of points that will be lying on the straight line ie points that have the same slope.

For finding out the maximum number of points having the same slope, we need to check with respect to every point present in the array. which clearly means that time complexity will be O(n^2).

Here we will find slope using (y2-y1)/(x2-x1) but the thing is slope can be in fractions also so we will use double for that and modify equation as   (y2-y1)/((1.0)*(x2-x1)).

The thing is here if we fixed one point for different points there will be different angles and those angles will be repeated a different number of times so for storing that information we will use a hashmap and this hashmap will be created every time ie O(N) time as with respect to every point there will be a different value of slope for every other point.

At last, we know slope is basically tan(theta) and tan(theta)=!0/0 which actually means undefined or not possible. Here in our question, this means the point is the same as y2-y1 will give us 0  and x2-x1 is also 0.

For that reason, we have one counter variable count which will be incremented when the point will be the same. 

And this counter variable will be used every time while finding out the max value. This is so because every time we need to compare map.get(tan) with current max but while doing this we should not forget that same point(ie fixed point) can be repeated several times in the array so to cover that case only we used counter variable and compare map.get(tan)+count with current max.

This is also the reason we have not used HashSet which stores unique points and filters put duplicates. If we have used HashSet then it only calculates the value ith respect to one occurrence of that fixed point while we need to calculate with all the occurrences of that fixed point including duplicates which also means we ignored some points which were falling on the same slope line which we should not.

 

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"