1200. Minimum Absolute Difference

1200. Minimum Absolute Difference

Brute Force: Time Limit Exceed

class Solution {
    public List<List> minimumAbsDifference(int[] arr) {
        List<List> out = new ArrayList();
        int minAbs = Integer.MAX_VALUE;
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++){
            for (int j= i+1; j < arr.length; j++){
                minAbs = Math.min(minAbs, Math.abs(arr[i] - arr[j]));
            }
        }
        
         for (int i = 0; i < arr.length; i++){
            for (int j= i+1; j < arr.length; j++){
                if(Math.abs(arr[i] - arr[j]) == minAbs) {
                    ArrayList pair = new ArrayList();
                    pair.add(arr[i]);
                    pair.add(arr[j]);
                    out.add(pair);
                }
            }
        }
     return out;   
    }
}

Easy Optimization:

class Solution {
    public List<List> minimumAbsDifference(int[] arr) {
        List<List> out = new ArrayList();
        int minAbs = Integer.MAX_VALUE;
        Arrays.sort(arr);
        //LinkedHashMap to preserve the insertion order
        LinkedHashMap index = new LinkedHashMap();
        for (int i = 0; i  Math.abs(arr[i+1] - arr[i])){
                minAbs = Math.abs(arr[i+1] - arr[i]);
                index = new LinkedHashMap();
                index.put(i,i+1);
            }
        }
        
        for (Integer a : index.keySet()){
            ArrayList in = new ArrayList();
            in.add(arr[a]);
            in.add(arr[index.get(a)]);
            out.add(in);
        }
     return out;   
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s