Sort multidimensional array based of the difference in the value

Question

Sort multidimensional array based of the difference in the value, if value is same sort on first column.

Constrains:

No of rows can be any but fixed no of column ie 2. Example:

int arr[][] = new int[5][2]
 [0] [1]
[0] 0 6
[1] 0 7
[2] 4 5
[3] 2 3
[4] 0 1

Final Output:

 [0] [1]
[0] 0 1
[1] 2 3
[2] 4 5
[3] 0 6
[4] 0 7

Explanation:

difference between: arr[0][1] - arr[0][0] -> 6-0 -> 6
difference between: arr[1][1] - arr[1][0] -> 7-0 -> 7
difference between: arr[2][1] - arr[2][0] -> 5-4 -> 1 — same length ie 1
difference between: arr[3][1] - arr[3][0] -> 3-2 -> 1 — same length ie 1
difference between: arr[4][1] - arr[4[0] -> 1-0 -> 1 — same length ie 1

I want to sort on the difference, in cases where difference is same I want to sort those with same difference on column [0]

So in this case, the below 3 have same difference:

difference between: arr[2][1] - arr[2][0] -> 5-4 -> 1 — same difference ie 1
difference between: arr[3][1] - arr[3][0] -> 3-2 -> 1 — same difference ie 1
difference between: arr[4][1] - arr[4[0] -> 1-0 -> 1 — same difference ie 1

Need to sort the above 3 based on there column[0] value:

arr[2][1] - arr[2][0] -> 5-4 -> 1 — value here is 4 ie arr[2][0] 
arr[3][1] - arr[3][0] -> 3-2 -> 1 — value here is 2 ie arr[3][0]
arr[4][1] - arr[4[0] -> 1-0 -> 1 — value here is 1 ie arr[4][0]

So the the one with the least value in column[0] should be first, in final output:

arr[4][1] - arr[4[0] -> 1-0 -> 1 ——> 1st
arr[3][1] - arr[3][0] -> 3-2 -> 1 ——> 2nd
arr[4][1] - arr[4[0] -> 1-0 -> 1 ——> 3rd 
arr[0][1] - arr[0][0] -> 6-0 -> 6 ——> 4th
arr[1][1] - arr[1][0] -> 7-0 -> 7 ——> 5th

I would like to know the time complexity of my code. In short, what is the complexity of sorting a 2D array? 1d array --> O(n.logn) 2d --> ?

private static int solve(int pathLength, int[][] floristIntervals) {
 // TODO Auto-generated method stub
 System.out.println(Arrays.deepToString(floristIntervals));
 Arrays.sort(floristIntervals, new Comparator<int[]>(){
 @Override
 public int compare(int[] o1, int[] o2) {
 // TODO Auto-generated method stub
 /*System.out.println(o1[0]);
 System.out.println(o1[1]);
 System.out.println(o2[0]);
 System.out.println(o2[1]);*/
 if(o2[1]-o2[0] == o1[1]-o1[0]){
 if(o2[0] > o1[0]){
 return -1;
 }
 return 1;
 }
 if (o2[1]-o2[0] > o1[1]-o1[0])
 return 1;
 else
 return -1;
 }
 });
 System.out.println(Arrays.deepToString(floristIntervals));

Answer 1

Comparator → Total Ordening

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

compare({0, 1}, {0, 1}) == 1

In its current form, the used comparator cannot return 0, and returns 1 for equals elements.

Does not solve problem?

The example input gives this as output:

[[0, 7], [0, 6], [0, 1], [2, 3], [4, 5]]

 @Override
 public int compare(int[] o1, int[] o2) {
 if(o2[1]-o2[0] == o1[1]-o1[0]){
 if(o2[0] > o1[0]){
 return -1;
 }
 return 1;
 }
 if (o2[1]-o2[0] > o1[1]-o1[0])
 return 1; // <-- should be -1
 else
 return -1; // <-- should be +1
 }

Review

pathLength isn't used. What is it for?

The method solve is declared to return int, but doesn't.

Consider adding braces to all code blocks—including if and else. This will prevent errors from adding lines later.

o1 and o2 could be replaced with lhs (left-hand side) and rhs (right-hand side), but that's a bit nitpicking.

In order to implement returning 0 for equal elements, try using Integer.compare:

@Override
public int compare(int[] lhs, int[] rhs) {
 int rv = Integer.compare(lhs[1] - lhs[0], rhs[1] - rhs[0]);
 return rv != 0 ? rv : Integer.compare(lhs[0], rhs[0]);
}

Time Complexity

Unchanged: \$O(n\ log\ n)\$ by virtue of the comparison function being \$O(1)\$.