Three Identical Points Problem
Question:
You are given an nn-by-2, two-dimensional array which represents a list of nn points on the plane. For example, this array:
represents a list of 10 points with (xx,yy) coordinates of (3, 5), (20, -8), (9, 13), . . ., (3, 17).
Using a brute-force approach, write the method
public static int [ ] threeIdenticalPoints(int n, int [ ][ ] pts)
which takes an nn-by-2, two-dimensional array pts, where pts[i] is the array {x, y} giving the coordinates (xx, yy) of the iith point
The method determines if (at least) three of the points in the list are identical (meaning all three points have the same xx and the same yy coordinates). If this is the case, return an array of size 3 of the form {i, j, k} where the points in rows ii, jj, and kk are identical. If this is not the case, return the array {-1, -1, -1}.
In the example above, the array {2, 5. 8} would be returned since pts [2], pts [5], pts [8] all represent the point (9, 13).
public class ThreePoints {
public static void main(String [] args) {
}
// Write this method:
public static int [] threeIdenticalPoints(int n, int [][] pts) {
return new int[3];
}
public static int[][] pts = {
{3, 5},
{20, -8},
{9, 13},
{16, 17},
{20, 13},
{9, 13},
{3, 5},
{3, 40},
{9, 13},
{3, 17}
};
}
Solution:
public class App
{
public static void main(String[] args)
{
int[][] pts = {
{3, 5},
{20, -8},
{9, 13},
{16, 17},
{20, 13},
{9, 13},
{3, 5},
{3, 40},
{9, 13},
{3, 17}
};
int[] result = threeIdenticalPoints(10, pts);
System.out.println(String.format("Three identical points found at {%d, %d, %d}", result[0], result[1], result[2]));
}
// Brute force method
public static int[] threeIdenticalPoints(int n, int[][] pts)
{
// Define the array that will store the index of the points
// Define it to have by default, values of -1
int[] result = {-1, -1, -1};
// Iterathe through the points
for(int i = 0; i < n-2; i++)
{
int[] point_i = pts[i];
// Now iterate from point i+1 to N-1
for(int j = i+1; j < n-1; j++)
{
int[] point_j = pts[j];
// Now, iterate from point j+1 to N
for(int k = j+1; k < n; k++)
{
int[] point_k = pts[k];
// check if the three points are equal
if(point_i[0] == point_j[0] && point_j[0] == point_k[0] && point_i[1] == point_j[1] && point_j[1] == point_k[1]) // the three points are equal
return new int[] {i, j, k};
}
}
}
return result;
}
}