4
\$\begingroup\$

This question is from a recently concluded competition on Codechef.

You are given an array A of size n, and there are q queries of the form a, b, c, d such that a <= b and c <= d.

For each query, we need to check if the sub arrays A[a:b] and A[c:d] are similar. The sub-arrays are of same length and are similar if their sorted representations contains only one mismatch in all of their positions. It is also possible that two sub arrays can overlapped.

For example

A = [36, 24, 12, 24, 60]
a = 0, b = 2, c = 2, d = 4
sorted A[a:b] = [12, 24, 36]
sorted A[c:d] = [12, 24, 60]

They differ at only one index, so they are similar.

I tried to solve this in brute-force method which could solve preliminary test cases, but getting TLE for large inputs. Following is my code. How can we efficiently solve this problem?

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by renaganti on 6/11/17.
 */
public class Cloning {
    public static void main(String []args) {
        Scanner reader = new Scanner(System.in);
        int t = reader.nextInt();
        while(t-- > 0) {
            int n = reader.nextInt();
            int q = reader.nextInt();
            int i;
            int []arr = new int[n];
            for(i = 0; i < n; i++) {
                arr[i] = reader.nextInt();
            }

            for(i = 0; i < q; i++) {
                int a = reader.nextInt();
                int b = reader.nextInt();
                int c = reader.nextInt();
                int d = reader.nextInt();
                if( similar(arr, a, b, c, d) )
                    System.out.println("YES");
                else
                    System.out.println("NO");

            }
        }
    }
    private static boolean similar(int []arr, int a, int b, int c, int d) {
        int [] arr1 = new int[b-a+1];
        int [] arr2 = new int[d-c+1];

        for(int j = a-1, k = c-1, l = 0; j < b; j++, k++) {
            arr1[l] = arr[j];
            arr2[l] = arr[k];
            l++;
        }

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int diff = 0;
        for(int j = 0; j < arr1.length; j++) {
            if( arr1[j] != arr2[j])
                diff++;
            if( diff > 1 )
                break;
        }
        if( diff < 2 )
            return true;
        else
            return false;
    }
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Here is some discussion on the question. It seems like a very tough problem. \$\endgroup\$ Jun 16, 2017 at 15:55

1 Answer 1

2
\$\begingroup\$

Test for the easy cases

    private static boolean similar(int []arr, int a, int b, int c, int d) {

This misses several quick and easy to check possibilities.

          if (a == c && b == d) {
              // each segment is similar to itself
              return true;
          }

Check if it's the same segment. If so, done.

          if (b - a != d - c) {
              // if different sizes, not similar
              return false;
          }

The segments have to be the same size to be similar.

          if (a < c) {
              if (b >= c) {
                  int temp = b + 1;
                  b = c - 1;
                  c = temp;
              }
          } else {
              if (d >= a) {
                  int temp = d + 1;
                  d = a - 1;
                  a = temp;
              }
          }

If either segment overlaps the other, then we can remove the overlap. We don't have to check those elements, as we already know that they are the same. This eliminates all the work of checking the overlap. In particular, we don't have to copy or sort those elements.

The two cases are a < c < b < d and c < a < d < b. We test for the order of the first three, and the final one must be in that order to keep the sizes equal. I.e. b = a + size - 1, so d = c + size - 1. Therefore if a < c, then b < d.

Consider the worst case for your code. That's when a and c both equal 0, while b and d equal arr.length - 1. Your code copies the entire array twice, then sorts the entire array twice, and finally iterates over both arrays to compare each element. This code would simply return true in constant time.

There's a method for that.

        int [] arr1 = new int[b-a+1];
        int [] arr2 = new int[d-c+1];

        for(int j = a-1, k = c-1, l = 0; j < b; j++, k++) {
            arr1[l] = arr[j];
            arr2[l] = arr[k];
            l++;
        }

We could use Arrays.copyOfRange, as such:

        int[] arr1 = Arrays.copyOfRange(arr, a, b + 1);
        int[] arr2 = Arrays.copyOfRange(arr, c, d + 1);

Then we don't have to write out the logic.

Don't do extra checks

        for(int j = 0; j < arr1.length; j++) {
            if( arr1[j] != arr2[j])
                diff++;
            if( diff > 1 )
                break;
        }
        if( diff < 2 )
            return true;
        else
            return false;

You could rewrite this as

        for (int j = 0; j < arr1.length && diff <= 1; j++) {
            if ( arr1[j] != arr2[j]) {
                diff++;
            }
        }

        return diff <= 1;

That's shorter but takes no less time.

The simpler return is a common pattern. In Java, you can simply return the result. You don't need to process it with an if/else.

I prefer to compare to 1 rather than 2, as 1 is what appears in the problem statement. I prefer to keep the code as close to the problem statement as possible to make it easier to read later.

Even better might be

        for (int j = 0; j < arr1.length; j++) {
            if ( arr1[j] != arr2[j]) {
                diff++;
                if ( diff > 1 ) {
                    return false;
                }
            }
        }

        return true;

We only need to check diff if we increment it. The rest of the time, it stays the same as it was.

Binary search

I haven't tried to write up a solution, but you don't have to copy and sort both array segments. If you copy and sort one, you can just iterate over the other and binary search the first. If there is a match, you go to the next one. If no match, you mark off the value as if matched and increase the difference count.

This won't give any asymptotic improvement, but it may make the program a little faster.

Dynamic programming

Again, I haven't tried to write up a solution, but realize that two segments are similar if their first elements are the same and the remainder of the segments are similar. So it might be worthwhile saving the work that we've done in sorting and comparing previous segments. Then we can reduce new queries to previous queries with some added entries.

This would likely be memory intensive.

New data structure

Consider the possibility of a data structure that kept track of the original order and the sorted order and could map between them. At the simplest level, a sorted order that remembered the original placement. But at a more complex level, possibly a trie-like structure.

Again, this would likely be memory intensive.

\$\endgroup\$
2
  • \$\begingroup\$ (Checking interval lengths is defensive.) Do the overlap removal first: if remaining interval length 1, at most, the original ones were similar (no need to check for identity separately). \$\endgroup\$
    – greybeard
    Jun 17, 2017 at 6:11
  • \$\begingroup\$ Thanks for all the improvements suggested. I will try to incorporate them in the code and see if it passes some more test cases. It is given in the problem statement that both the subarrays are equal in size. That's why I have not included them in my code. \$\endgroup\$ Jun 17, 2017 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.