gururaj.kosuru
BAN USERI think it works in linear time complexity to the number of nodes if we store them for quick access.
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> n = new HashMap<Integer, Integer>();
int maxDiameter(node root) {
if(root == null)
return 0;
if( n.containsKey(root.key))
return n.get(root.key);
int temp = max(maxDiameter(root.left), maxDiameter(root.right), findMaxDepth(root.left) + findMaxDepth(root.right) + 1);
n.put(root.key, temp);
return temp;
}
int findMaxDepth(node root) {
if(root == null)
return 0;
if(m.containsKey(root.key))
return m.get(root.key);
int temp = max(findMaxDepth(root.left), findMaxDepth(root.right)) + 1;
m.put(root.key, temp);
return temp;
}
}
- gururaj.kosuru February 24, 2013I am not sorting by the index but by the value so that I have a list of all starting and ending points of the circles which is my data structure B.
- gururaj.kosuru February 24, 2013This solution occupies O(n) extra space and works in O(logn), Does it sound correct?:
I write down the max and min points of the circles and store them in an array using a data structure to identify the index of each point. Then, I sort them in nlogn.
Next I iterate through the array keeping note of circle starts and ends using a hashmap and whenver a circle ends, all the circles which are enveloping it add to the number of intersections. Hence, I add them up.
import java.util.Arrays;
import java.util.HashMap;
public class Circle {
class node implements Comparable<node>{
int value;
int index;
node(int index, int value) {
this.index = index;
this.value = value;
}
public int compareTo(Circle.node o) {
return this.value - o.value;
}
}
int[] A;
node[] B;
Circle(int[] in) {
this.A = in;
B = new node[A.length*2];
for( int i = 0 ;i < A.length; i++) {
B[2*i] = new node(i, i - A[i]);
B[2*i+1] = new node(i, i + A[i]);
}
}
int process() {
Arrays.sort(B);
int sum = 0, envelopes = 0, i =0;
HashMap<Integer, Boolean> m = new HashMap<Integer, Boolean>();
while( i < B.length) {
System.out.println("node " +B[i].index +" value "+ B[i].value);
if(m.containsKey(B[i].index))
{
m.remove(B[i].index);
envelopes--;
sum += envelopes;
}else{
m.put(B[i].index, true);
envelopes++;
}
i++;
}
return sum;
}
public static void main(String args[]) {
int[] A = {1,5,2,1,4,0};
Circle c = new Circle(A);
System.out.println(c.process());
}
}
@Barry : yep, missed the n in nlogn.
- gururaj.kosuru March 03, 2013@Zythum : thanks for the feedback.
@Arthur: If there are two circles and one circle lies completely inside other, I used the word enveloping.