Java code to check whether two arrays are similar

Question

I got this coding problem from a website. The question was as follows:

Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements in one of the arrays.

Given two arrays, check whether they are similar.

Example

For A = [1, 2, 3] and B = [1, 2, 3], the output should be areSimilar(A, B) = true.

The arrays are equal, no need to swap any elements.

For A = [1, 2, 3] and B = [2, 1, 3], the output should be areSimilar(A, B) = true.

We can obtain B from A by swapping 2 and 1 in B.

For A = [1, 2, 2] and B = [2, 1, 1], the output should be areSimilar(A, B) = false.

Any swap of any two elements either in A or in B won't make A and B equal.

This is the solution I gave:

boolean areSimilar(int[] A, int[] B) {
    if(A.length != B.length) return false;

    int[] copyA = A, copyB = B;
    Arrays.sort(copyA); Arrays.sort(copyB); 
    int countSwap = 0;

    if(!Arrays.equals(copyA, copyB)) return false;

    for(int i = 0; i < A.length; i++) {
        if(A[i] != B[i]) countSwap++;
    }

    return (countSwap == 2 || countSwap == 0);
}

This code gave correct results for the following arrays:

1. A: [1, 2, 3]
   B: [1, 2, 3]

2. A: [1, 2, 3]
   B: [2, 1, 3]

3. A: [1, 2, 2]
   B: [2, 1, 1]

4. A: [1, 1, 4]
   B: [1, 2, 3]

5. A: [1, 2, 3]
   B: [1, 10, 2]

6. A: [2, 3, 1]
   B: [1, 3, 2]

But still the website displays "INCORRECT" every time I try to submit the code. It fails to pass two out of six hidden tests and I cannot figure out why. Is this the correct code? Is there any other, more easier way?

Answer 1

Here is a Kotlin solution for this. No sort needed, iterate only once.

fun solution(a: MutableList<Int>, b: MutableList<Int>): Boolean {
        var diffCount = 0
        
        var lastSwappedA: Int? = null
        var lastSwappedB: Int? = null
        
        a.forEachIndexed{ index, aElement->
            val bElement = b[index]
            if(aElement!=bElement){
                diffCount++
                lastSwappedA?.let{
                    if(bElement != lastSwappedA || aElement != lastSwappedB){
                        return false
                    }
                }
                lastSwappedA = aElement
                lastSwappedB = bElement
            }
        }
        
        return diffCount == 2 || diffCount == 0
    }

Answer 2

Instead of creating a separate copy or modifying the same array by sorting, we can use HashMap to get the frequency, and then counting the swap count in the actual array will be the fastest and most accepted solution.

boolean solution(int[] a, int[] b) {
    Map<Integer, Integer> mapA = new HashMap<>();
    Map<Integer, Integer> mapB = new HashMap<>();
    for(int index = 0; index < a.length; index++) {
        mapA.put(a[index], mapA.getOrDefault(a[index], 0) + 1);
        mapB.put(b[index], mapB.getOrDefault(b[index], 0) + 1);
    }
    
    for(int key : mapA.keySet()) {
        if (mapA.get(key) != mapB.getOrDefault(key, 0)) return false;
    }
    // Count the swaps
    int swapCount = 0;
    for(int i = 0; i < a.length; i++) {
        if (a[i] != b[i]) swapCount++;
    }
    
    if (swapCount > 2) return false;
    
    return true;
}

Answer 3

areSimilar([4, 6, 3],[3, 4, 6]); // example arrays


boolean areSimilar(int[] a, int[] b) {
    
    boolean isSimular = false;
        int count = 0;
        int temp = 0;
        
        if(a.length!=b.length) { // check two arrays length
            return false;
        }
        
        for (int i = 0; i < a.length; i++) {
            if (a[i] == b[i]) {
                isSimular=true;
            } else {
                count++;
                if(count>1) {
                    isSimular =false;
                    return isSimular;
                } 
                for (int j = 0; j < a.length; j++) {
                    if(a[i]==b[j] && a[j]!=b[j]) {
                                                
                        temp=b[i];
                        b[i]=b[j];
                        b[j]=temp;
                        break;
                        
                        
                        
                        
                    }
                }
            }
        }

        
        return isSimular;
}

Answer 4

def areSimilar(a, b):
    n = 0
    if len(a)!=len(b):
        return False
    else:
        for i in range(len(a)):
            if a[i]!=b[i]:
                n+=1
                if n>2:
                    return False
            if a[i] not in b:
                return False
        print(n)
        return True

Answer 5

The problem in your program

Instead of creating and sorting copies of the arrays, you used assignment.

copyA = A

This means that copyA is still a reference to the original array, and therefore, the original arrays will be sorted when you try to count the swaps.

This means that when you try to check two arrays that have the same elements but many swaps, you'll get true when you are supposed to get false.

An array should be copied by:

• A.clone()
• Arrays.copyOf(A, A.length)
• or copyA = new int[A.length]; System.arrayCopy(A,0,copyA,0,A.length);

Sets instead of sorting

Instead of copying the arrays, sorting and comparing, you can use sets. The reason that you are sorting is to check that both arrays have exactly the same elements. In that case, you can put the elements into sets and compare the sets, without sorting.

Set<Integer> setA = new HashSet<>(Arrays.asList(A));
Set<Integer> setB = new HashSet<>(Arrays.asList(B));
if ( ! setA.equals(setB) ) {
    return false;
}

The equals method for sets returns true if and only if the two sets contain exactly the same elements (order does not matter in sets).

The set approach will only work if your arrays are guaranteed not to have repeating values. Frequency maps could work for arrays with repetitions, but frankly, it would be unreadable.

A linear approach

Your approach takes O(n log n) because of the sorts, in addition to linear memory. In fact, the problem as it stands can be solved in linear time and constant memory.

• Check that the lengths are equal. If not, return false.
• Let ind be an array of two elements for indices of the positions where there are differences.
• Loop over the arrays (as you do now) counting the differences.
• If you encounter a difference, if countSwap < 2, put i in ind[countSwap], and then increment countSwap.
• At the end of the loop, if countSwap is 0, return true.
• If countSwap is 1 or greater than 2, return false.
• If countSwap is 2, check the items at the indices that you kept. If A[ind[0]] == B[ind[1]] and A[ind[1]] == B[ind[0]], return true, otherwise return false.

Explanation

If there is 1 or 3 and above differences between the two arrays, then of course they are not "similar".

But if you have 2 differences exactly, these can be either because there are completely different values in those two places, or because there was a swap.

So you check if the 2 differences are because of a swap.

There is no need to sort. The only reason you are sorting is to see if the two arrays have exactly the same elements. But the number of differences can tell you that without sorting.

By the way, you can break out of the loop once countSwap reaches 3.

Answer 6

Your code is not working because you sorted the original arrays here ...

copyA = A, copyB = B;
Arrays.sort(copyA); Arrays.sort(copyB);

then you are comparing the sorted arrays instead of original arrays for checking if they can be converted using only one swap!!

You should do something like this...

boolean areSimilar(int[] A, int[] B) {
    if(A.length != B.length) return false;

    int countSwap = 0;
    int[] copyA = Arrays.copyOf(A, A.length);
    int[] copyB = Arrays.copyOf(B, B.length);

    // checking both contain the same elements...
    Arrays.sort(copyA); Arrays.sort(copyB); 
    if(!Arrays.equals(copyA, copyB)) return false; 

    // checking for min 2 swaps using original arrays...
    for(int i = 0; i < A.length; i++) {
        if(A[i] != B[i]) countSwap++;
    }

    return (countSwap == 2 || countSwap == 0);
}

more efficient solution ...

boolean areSimilar(int[] A, int[] B) {
  ArrayList<Integer> ids = new ArrayList<>();
  for (int i = 0; i < A.length; i++) {
    if ( A[i] != B[i] ) {
      ids.add(i);
    }
  }
  if (ids.size() == 0) {
    return true;
  }
  if (ids.size() != 2) {
    return false;
  }
  int id1 = ids.get(0);
  int id2 = ids.get(1);
  if (A[id1] == B[id2] && A[id2] == B[id1]) {
    return true;
  }
  return false;
}