Checking whether an Array equals another Array Backwards using divide and conquer

user_18679733 0
Viewed 80

I've been trying to make a simple function which checks if an array is the same as another array reversed.

For instance, comparing [0, 1, 2] and [2, 1, 0] would return true, but comparing [0, 1, 2] and [2, 1, 1] would return false.

I am also trying to use the divide and conquer method, using function recursively.

This is what I have coded, but it doesn't work as intended, returning false when it should return true:

public class ReverseCheck {

    // Check if an array is the reverse of another array
    // Use divide and conquer
    public static boolean isReverse(int[] a, int[] b) {
        if (a.length != b.length) {
            return false;
        }
        return isReverse(a, b, 0, a.length - 1);
    }

    private static boolean isReverse(int[] a, int[] b, int start, int end) {
        if (start == end) {
            return a[start] == b[end];
        }
        int mid = (start + end) / 2;
        return isReverse(a, b, start, mid) && isReverse(a, b, mid + 1, end);
    }

    public static void main (String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6};
        int[] b = {6, 5, 4, 3, 2, 1};
        int[] c = {1, 2, 3, 4, 5, 6, 7};
        int[] d = {6, 5, 5, 3, 2, 1};
        System.out.println(isReverse(a, b)); // Should return true, returns false
        System.out.println(isReverse(a, c)); // Should return false, returns false
        System.out.println(isReverse(a, d)); // Should return false, returns false
    }

}
divide-and-conquer recursion arrays algorithm java
1 Answers

There's a couple of issues in your solution:

  • The base case has a logical flaw in it. The return value represents the result of comparison a[start] == b[end] when indices are equal. Which isn't the correct way to validate whether the one array is a reversed copy of another. Let's consider the two arrays a = [1, 2, 3] and b = [3, 2, 1]. We have to check whether a[0] == b[2], a[1] == b[1] and a[2] == b[0]. As you can see the case when indices are equal take place only once and only if the length is odd, if the length is even indices in all pair of elements will be different.

  • The second issue is the overall approach that you've taken. For this problem, we have to check all pairs of values. The divide and conquer approach is fruitless here because we can't reduce the amount of operations, in the worst case every pair of values needs to be compared.

I suggest addressing this problem with backtracking by simply moving the indices of both arrays by 1 at each method call, without utilizing the divide and conquer because we can't benefit from it.

First, let's fix the base case of recursion.

There are two cases when recursion should terminate: when values in the pair don't match and the last valid index has been reached.

The condition for the first case, when values that correspond to the current indices are not equal, will look that:

if (a[start] != b[end]) return false;

And the second part might be written like that:

if (start == a.length - 1) return a[start] == b[end];

or

if (start == a.length - 1) return true;

The meaning of both is almost the same - we've managed to compare all the pair of values (or the last pair is being compared). The first version is slightly better, it'll spare one method call.

In the recursive case, we are simply calling the method by passing the start incremented by 1 and the end decremented by 1.

private static boolean isReverse(int[] a, int[] b, int start, int end) {
    if (start == a.length - 1) {
        return a[start] == b[end];
    }
    if (a[start] != b[end]) {
        return false;
    }

    return isReverse(a, b, start + 1, end - 1);
}

main()

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6};
    int[] b = {6, 5, 4, 3, 2, 1};
    int[] c = {1, 2, 3, 4, 5, 6, 7};
    int[] d = {6, 5, 5, 3, 2, 1};
    System.out.println(isReverse(a, b)); // Should return true, returns false
    System.out.println(isReverse(a, c)); // Should return false, returns false
    System.out.println(isReverse(a, d)); // Should return false, returns false
}

Output

true
false
false

Fix for the initial divide and conquer version

As I've said earlier, the problem resides in the base case. Instead of comparing the elements at the same position a[start] == b[end] (when start equals to end it will not make sense), we need to adjust the end index:

    if (start == end) {
        return a[start] == b[(b.length - 1) - end];
    }

That's the only change that needs to be applied to the original code listed in the question.

user_179499450
Related