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));
up vote 0 down vote accepted

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)\$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.