Array of 3 Pointers

In today's problem we are given 3 sorted arrays. Let A, B, C be the 3 arrays. We need to find a value such that max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])) is minimum. Consider the following example for a better understanding.

Input

A : [1, 4, 10]
B : [2, 15, 20]
C : [10, 12]

Output

5

Explanation

We choose 10 from A, 15 from B and 10 from C. Therefore, max(abs(10 - 15), abs(15 - 20), abs(10 - 10)) is 5, which is the minimum value possible.

Solution Approach

We use a 3 pointer approach to solve this problem. The 3 pointers are i, j and k which correspond to the indices of A, B and C arrays.

  • Initialise a result variable to INT_MAX.
  • Run a loop until the end of one of the array's is reached. 
  • Find the maximum of the difference between the 3 elements in each iteration. 
  • If the maximum value found is the difference between A[i] and B[j], increment the pointer value of the smaller of the two elements. 
  • Update the result value if the difference is smaller than the previous result value.

Program



Feel free to post your doubts below :)

Comments

Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming