Divide and conquer algorithm

Question

I had a job interview a few weeks ago and I was asked to design a divide and conquer algorithm. I could not solve the problem, but they just called me for a second interview! Here is the question:

we are giving as input two n-element arrays A[0..n − 1] and B[0..n − 1] (which are not necessarily sorted) of integers, and an integer value. Give an O(nlogn) divide and conquer algorithm that determines if there exist distinct values i, j (that is, i != j) such that A[i] + B[j] = value. Your algorithm should return True if i, j exists, and return False otherwise. You may assume that the elements in A are distinct, and the elements in B are distinct.

can anybody solve the problem? Thanks

Answer 1

My approach is..

1. Sort any of the array. Here we sort array A. Sort it with the Merge Sort algorithm which is a Divide and Conquer algorithm.
2. Then for each element of B, Search for Required Value- Element of B in array A by Binary Search. Again this is a Divide and Conquer algorithm.
3. If you find the element Required Value - Element of B from an Array A then Both element makes pair such that Element of A + Element of B = Required Value.

So here for Time Complexity, A has N elements so Merge Sort will take O(N log N) and We do Binary Search for each element of B(Total N elements) Which takes O(N log N). So total time complexity would be O(N log N).

As you have mentioned you require to check for i != j if A[i] + B[j] = value then here you can take 2D array of size N * 2. Each element is paired with its original index as second element of the each row. Sorting would be done according the the data stored in the first element. Then when you find the element, You can compare both elements original indexes and return the value accordingly.

Answer 2

The following algorithm does not use Divide and Conquer but it is one of the solutions. You need to sort both the arrays, maintaining the indexes of the elements maybe sorting an array of pairs (elem, index). This takes O(n log n) time.

Then you can apply the merge algorithm to check if there two elements such that A[i]+B[j] = value. This would O(n)

Overall time complexity will be O(n log n)

Answer 3

I suggest using hashing. Even if it's not the way you are supposed to solve the problem, it's worth mentioning since hashing has a better time complexity O(n) v. O(n*log(n)) and that's why more efficient.

1. Turn A into a hashset (or dictionary if we want i index) - O(n)
2. Scan B and check if there's value - B[j] in the hashset (dictionary) - O(n)

So you have an O(n) + O(n) = O(n) algorithm (which is better that required (O n * log(n)), however the solution is NOT Divide and Conquer):

Sample C# implementation

  int[] A = new int[] { 7, 9, 5, 3, 47, 89, 1 };
  int[] B = new int[] { 5, 7, 3, 4, 21, 59, 0 };

  int value = 106; // 47 + 59 = A[4] + B[5]

  // Turn A into a dictionary: key = item's value; value = item's key 
  var dict = A
    .Select((val, index) => new {
      v = val,
      i = index, })
    .ToDictionary(item => item.v, item => item.i);

  int i = -1;
  int j = -1;

  // Scan B array
  for (int k = 0; k < B.Length; ++k) {
    if (dict.TryGetValue(value - B[k], out i)) {
      // Solution found: {i, j} 
      j = k;

      // if you want any solution then break
      break;

      // scan further (comment out "break") if you want all pairs
    }
  }

  Console.Write(j >= 0 ? $"{i} {j}" : "No solution");

Answer 4

Seems hard to achieve without sorting.

If you leave the arrays unsorted, checking for existence of A[i]+B[j] = Value takes time Ω(n) for fixed i, then checking for all i takes Θ(n²), unless you find a trick to put some order in B.

Balanced Divide & Conquer on the unsorted arrays doesn't seem any better: if you divide A and B in two halves, the solution can lie in one of Al/Bl, Al/Br, Ar/Bl, Ar/Br and this yields a recurrence T(n) = 4 T(n/2), which has a quadratic solution.

If sorting is allowed, the solution by Sanket Makani is a possibility but you do better in terms of time complexity for the search phase.

Indeed, assume A and B now sorted and consider the 2D function A[i]+B[j], which is monotonic in both directions i and j. Then the domain A[i]+B[j] ≤ Value is limited by a monotonic curve j = f(i) or equivalently i = g(j). But strict equality A[i]+B[j] = Value must be checked exhaustively for all points of the curve and one cannot avoid to evaluate f everywhere in the worst case.

Starting from i = 0, you obtain f(i) by dichotomic search. Then you can follow the border curve incrementally. You will perform n step in the i direction, and at most n steps in the j direction, so that the complexity remains bounded by O(n), which is optimal.

Below, an example showing the areas with a sum below and above the target value (there are two matches).

This optimal solution has little to do with Divide & Conquer. It is maybe possible to design a variant based on the evaluation of the sum at a central point, which allows to discard a whole quadrant, but that would be pretty artificial.