# O(1) space 6ms Java solution

• Running time not quite stable. Am trying to avoid calculate mean (which might not be int thus probably error-prone). Bit tricky is right part needs to be sorted in different y-order as left side.

``````public boolean isReflected(int[][] points) {
int n = points.length;
if (n <= 1)
return true;
int min = points[0][0];
int max = points[0][0];
for (int i = 1; i < n; i++)
if (points[i][0] < min)
min = points[i][0];
else if (points[i][0] > max)
max = points[i][0];
final int xmax = max;
final int xmin = min;
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] pa, int[] pb) {
if (pa[0] != pb[0])
return pa[0] - pb[0];
return pa[0] - xmin <= xmax - pa[0] ? pa[1] - pb[1] : pb[1] - pa[1]; // reverse for right side
}
});
for (int i = 0, j = n-1; i <= j; i++, j--)
if ((points[i][0] - min != max - points[j][0]) || (points[i][0] * 2 != min + max && points[i][1] != points[j][1]))
return false;
return true;
}``````

• It is great to come up a creative way for comparable. However, when we use Arrays.sort, we can not assume O(1) space and better than O(n^2) running time. Arrays.sort is O(n^2) by default unless you provide your own algorithm such as modified MergeSort.

• How did you get the idea that it's not O(n log n)?

• Arrays.sort is QuickSort in java, which is nlogn on AVERAGE, but it is O(n^2). Please look at http://stackoverflow.com/questions/4305004/why-arrays-sort-is-quicksort-algorithm-why-not-another-sort-algorithm . Thanks.

• If that is the case, you can not claim O(1) space any more. It is in O(n).

• can not pass test case [[1,1],[-1,1],[1,1]]

• You answer is not correct when there exists duplicate points.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.