java - Square with minimum area enclosing K points among given N points -

this question asked me in online test. there n points given in cartesian plane. integer k given. aim find area of square (minimum) enclosing @ least k points. sides of square should parallel axis.the vertices of square should integers. points lying on sides not considered inside square.

i solve k=n (i.e. points lie in square).

my solution -

    static int minarea(int[] x, int[] y, int k) {     //find max y     int maxval = integer.min_value;     for(int : y){         if(i > maxval){             maxval = i;         }     }     //find min y     int minval = integer.max_value;     for(int : x){         if(i < minval){             minval = i;         }     }      int ylength = (maxval-minval)+2;      //find max x     maxval = integer.min_value;     for(int : x){         if(i > maxval){             maxval = i;         }     }     //find min x     minval = integer.max_value;     for(int : x){         if(i < minval){             minval = i;         }     }      int xlength = (maxval-minval)+2;     int sqside = (ylength > xlength)?ylength:xlength;     return sqside*sqside;  } 

one approach general solution find possible combination of k points among n points , applying above method combinations not good. please advise.

it can seen can move square have points on left , bottom edges. we'll iterate through combinations of left , bottom edges of square. need find upper or right edge of square. every point can determine @ edge lie. example if point.x - left > point.y - bottom point lie on right edge of square , resulting area ( point.x - left )^2. we'll need sort points area of squares: area = ( max( point.x - left, point.y - bottom ) )^2 , select k-th point sorted list. smallest square enclosing @ least k points specified left bottom corner. complexity of solution o(n^3) not nice, faster iterating on combinations of k points. solution in java: https://ideone.com/139c7a