Sorting an array of zeros, negative and positive numbers with Comparable interface

Question

class pair implements Comparable<pair>{
int x, y;
pair(int x, int y){
    this.x = x;
    this.y = y;
}
public int compareTo(pair c){
    return this.y-c.y;
}}

class Solution {
public int findMinArrowShots(int[][] points) {
    ArrayList<pair> point = new ArrayList<>(); 
    for(int i=0; i<points.length; i++){
        point.add(new pair(points[i][0], points[i][1]));
    }
    
    Collections.sort(point);
    
    int minarr=1;
    int prev =0;
    for(int i=1; i<point.size(); i++){
        if(point.get(i).x>point.get(prev).y){
            minarr++;
            prev = i;
        }
    }
    return minarr;
}}

I want to sort the array on the basis of y coordinate: but with mix of positive and negative y values it is giving me wrong(unsorted) order

for eg: for the I/P : [[-2147483646,-2147483645], [2147483646,2147483647]] I need [-2147483646,-2147483645] first then [2147483646,2147483647] but it is ordering [2147483646,2147483647] as first then [-2147483646,-2147483645].

you're comparing one point's `x` to another point's `y` and counting how many times it's out of order, but it will *always* be in random order, because it's supposed to be ordering by `y`. Is that intentional? — Esther, Jun 23 '22 at 18:10
Can you use one digit value for your example? These numbers are way too big for us to read and make sense. — Cheng Thao, Jun 23 '22 at 18:12
the problem is that you're running into integer limits and you need to use 'long`. Java integers can't hold more than 2,147,483,647 or less than 2,147,483,648 (see [max value of integer](https://stackoverflow.com/questions/15004944/max-value-of-integer), so when you add/subtract them you can end up with integer overflow/underflow, which is probably what's happening. — Esther, Jun 23 '22 at 18:12
Use `return Integer.compare(y, c.y);` instead of `return this.y-c.y;` in your `compareTo` method of your `Pair` class. — Eritrean, Jun 23 '22 at 18:21

Esther · Accepted Answer · 2022-06-23T18:41:40.390

The problem is that you're running into integer limits. Java integers can't hold more than 2,147,483,647 or less than -2,147,483,648 (see max value of integer), so when you add/subtract them you can end up with integer overflow/underflow, which is what's happening here.

The solution to integer limit issues in general is to use long, which can hold values of up to 9,223,372,036,854,775,808 and as low as -9,223,372,036,854,775,807. However, here that is just stepping around the real issue: that you are inventing your own comparison method from scratch, when a built-in one designed to handle all edge cases already exists.

What you should be doing is calling the built-in compare() on the two y values. Instead of

return this.y - c.y

do

return Integer.compare(this.y, c.y)

which will call the built-in compare() method for integers, which is built to be able to handle all integers.

@AnandSharma you don't need to convert to long if you're doing `< and >`, only for math. And just use the built-in `Integer.compare()', it's literally done for you already. — Esther, Jun 23 '22 at 18:33
Even when you need to do arithmetic, the solution generally is not to promote operations to `long`. You should state the correct approach (`Integer.compare()`) first, and mention `long` at the end as a remark. — erickson, Jun 23 '22 at 18:41

score 0 · Answer 2 · answered Jun 23 '22 at 18:16

0

   if(point.get(i).x>point.get(prev).y){

Change to:

   if(point.get(i).y>point.get(prev).y){

answered Jun 23 '22 at 18:16

NovaDenizen

5,089
14
28

Sorting an array of zeros, negative and positive numbers with Comparable interface

2 Answers2