Minimum Triplet from 3 Arrays

[Question]
You are given with three sorted arrays ( in ascending order), you are required to find a triplet (one element from each array) such that distance is minimum.

Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
      distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))

Please give a solution in O(n) time complexity.


[Analysis]
Approach 1:
Assume the triplet with minimum distance is (a[i], b[j], c[k[) and b[j] is the median of the three numbers. This implies a[i] is the closest to b[j] among array a, and c[k] is the closest to b[j] among c[k]. 


So for a given j, if b[j] closest a[i] and closest c[j] are a[i]<=b[j]<=c[k] or c[k]<=b[j]<=a[i], then this triplet is one of the candidates for the minimum distance. 


The algorithm can scan array a, b, c and examine those candidates for the final result. The scan is in linear time. But this requires multiple scans which can be redundant.


Approach 2:
Suppose data in 3 arrays line up, the minimum triplet can must have the pattern of (X, Y, Y*, Z) where X, Y, Z come from different arrays (* denotes 0 or n appearances). So we can collect all such triplets that meet such pattern, measure their distances (which is Z-X) and find the minimum.


In code, a priority queue (that mimics heap) of size 3 is used. It ensures we get data from 3 arrays in a non-descending order. Then we found the pattern triplets (X, Y, Y*, Z) using class Pattern. Finally, the distances of all such triplets are calculated and measured. 

[Solution]

import java.util.*;


public class MinimumTripletTest {
public class Triplet {
int i, j, k;
}


public class Node implements Comparable{
char  arrId;   // 0-a, 1-b, 2-c
int  index;   // array index;
int  value;

Node (char t, int i, int v) {
arrId = t;
index = i;
value = v;
}


@Override
public int compareTo(Object a) {
// TODO Auto-generated method stub
if (!(a instanceof Node)) {
return -1;
}
Node n = (Node)a;

if (value< n.value) return -1;
if (value> n.value) return 1;
return 0;
}
}

public class Pattern {
List<Node> nodes;

Pattern() {
nodes = new ArrayList<Node> ();
}

boolean fulfilled() {
return nodes.size() == 3;
}

void add (Node a) {
if (nodes.size()==2 && a.arrId == nodes.get(1).arrId) {
nodes.set(1, a);
}
else if (nodes.size()==2 && a.arrId == nodes.get(0).arrId) {
nodes.set(0, nodes.get(1));
nodes.set(1, a);
}
else if (nodes.size()==1 && a.arrId == nodes.get(0).arrId) {
nodes.set(0,  a);
}
else {
nodes.add(a);
}
}

Node pop () {
if (nodes.size()==0) return null;
return nodes.remove(0);
}

int distance() {
if ( !fulfilled() ) return -1;
return nodes.get(2).value - nodes.get(0).value;
}

Triplet getTriplet() {
if (!fulfilled()) return null;
Triplet t = new Triplet();
for(Node n: nodes) {
if (n.arrId == 'a') {
t.i = n.index;
}
else if (n.arrId == 'b') {
t.j = n.index;
}
else if (n.arrId == 'c') {
t.k = n.index;
}
}
return t;
}
}

public Triplet findMinimumTriplet(int[] a, int[] b, int[] c) {
Pattern pat = new Pattern();
PriorityQueue<Node> pq = new PriorityQueue<Node>();

int min = Integer.MAX_VALUE;
int i,j,k;
i=j=k=0;

pq.add(new Node('a', i, a[i]));
pq.add(new Node('b', j, b[j]));
pq.add(new Node('c', k, c[k]));
Triplet t = null;

while (i<a.length || j<b.length || k<c.length) {
Node next = pq.remove();
pat.add(next);
if (pat.fulfilled()) {
if (pat.distance() < min) {
min = pat.distance();
t = pat.getTriplet();
}
pat.pop();
}

if (next.arrId == 'a' && ++i<a.length) {
pq.add(new Node('a', i, a[i]));
} 
else if (next.arrId == 'b'&& ++j<b.length) {
pq.add(new Node('b', j, b[j]));
}
else if (next.arrId == 'c' && ++k<c.length) {
pq.add(new Node('c', k, c[k]));
}
}

return t;
}

public static void main (String[] args) {
int[] a = {1,3,5,7, 9, 10, 13, 15, 24, 28, 29, 30,};
int[] b = {12, 12, 14, 17, 19, 22, 25, 28};
int[] c = {4, 9, 15, 22, 28, 38, 49, 50};

MinimumTripletTest test = new MinimumTripletTest();
MinimumTripletTest.Triplet t = test.findMinimumTriplet(a, b, c);

System.out.println("result: "+a[t.i]+","+b[t.j]+","+c[t.k]);
}
}

// result: 28,28,28