lexicographical comparison of two arrays in java

Question

I would like to implement a method that takes 2 arrays and returns the one that is lexicographically smaller than the other. I tried to do it according to the definition of lexicographic order, but it does not work. Here is my code:

public boolean lexicoSmaller(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    int m = 1;
    int n = list1.size() -1;


    while(m <= n)
    {
        boolean firstFound = true;
        for(int i=0; i<m; i++)
        {
            if(!Objects.equals(list1.get(i), list2.get(i)))
            {
                firstFound = false;
                break;
            }
        }

        if(firstFound && list1.get(m) < list2.get(m)) return true;
        m++;
    }

    return false;
}

The code above doesn't give the right answer.

For example for the inputs 0 5 7 9 14 16 18 23 and 1 3 6 11 12 17 20 22, the answer should be true, but I got false.

Answer 1

When the two arrays are sorted, we can just check for any i, if array1[i] < array2[i] then array1 is lexicografically smaller then array2.

Answer 2

Since Java 9, Arrays.compare provides a standard way of doing this.

Compares two Object arrays, within comparable elements, lexicographically.

There's also versions of Arrays.compare for arrays of longs, doubles, etc.

Answer 3

// The below function can be used for comparing two arraylists lexicographically.

public int lexicoSmaller(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    int n = list1.size();

    for(int i = 0; i < n; i++)
    {
        if(list1.get(i) < list2.get(i)) 
        {
            return 1; //list1 is smaller lexicographically
        }
        if(list1.get(i) > list2.get(i))
        {
            return -1; //list2 is smaller lexicographically
        }
    }
    
    return 0;  //list1 and list2 are equal
}

Answer 4

The definition of lexicographic order is much simpler than what you have implemented.

public boolean lexicoSmaller(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    int n = list1.size();

    for(int i = 0; i < n; i++)
    {
        if(list1.get(i) < list2.get(i)) 
        {
            return true;
        }
    }

    return false;
}

Note. Normally you want to apply these methods in comparators. Because then you can apply your comparison in the java collection framework for sorting arrays of arrays etc. So I would, rather than returning boolean, return int. More specifically,

class LexicoComparator implements Comparator<ArrayList<Integer>> {
    @Override
    public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
        for(int i = 0; i < a.size() && i < b.size(); ++i) {
            int diff = a.get(i) - b.get(i);

            if (diff != 0) {
                return diff;
            }
        }

        return a.size() - b.size();
    }
}