prasanth
BAN USERTraverse the tree in-order, while keeping track of the last encountered leaf node. During the traversal, set the right of last encountered leaf-node to the next encountered leaf-node.
Time-complexity : O(n)
Space-complexity : O(height-of-tree)
public static void populateRightOfLeaves(Node root) {
populateRightOfLeaves(root, null);
}
private static Node populateRightOfLeaves(Node root, Node prev) {
if (root == null) {
return prev;
}
if (root.left() == null && root.right() == null) { // if leaf
if (prev != null) {
prev.setRight(root);
}
return root;
}
prev = populateRightOfLeaves(root.left(), prev);
return populateRightOfLeaves(root.right(), prev);
}
Count the number of negatives in the array, at the same time check for any zeroes in the array.
If there is a zero in the array, get the max-product from the left and right sub-arrays and find the max of them.
If there are no zeroes :
1. if no. of negatives is even, max-product is the product of all numbers.
2. if it is odd, iterate the array in both forward and backward directions and compute the product until you discover a negative number. Now, ignore the side where the product's absolute value is lesser.
eg : [ -100, 2, 25, -1, 8, -5, 22]
no. of negatives are 3 here.
When you iterate the array from both directions : fwd-product is -100 and bwd-product is -110. So ignore the values in the forward direction. So the max-product is 44000
public static int findMaxProduct(int[] array, int begin, int end) {
int noNegs = 0; // count of negative numbers in the array
int zeroIndex = -1; // index where a '0' is present
for ( int i = begin; i < end; ++i) {
if (array[i] < 0) {
++noNegs;
}
if (array[i] == 0) {
zeroIndex = i;
}
}
if (zeroIndex > 0) {
int l = findMaxProduct(array, begin, zeroIndex);
int r = findMaxProduct(array, zeroIndex+1, end);
return Math.max(l, r);
}
if (noNegs % 2 == 0) {
int product = 1;
for (int i = begin; i < end; ++i) {
product *= array[i];
}
return product;
}
int fi, bi; // forward and backward indices
int fp = 1, bp = 1; // forward and backward products
for (fi = begin; fi < end; ++fi) {
fp *= array[fi];
if (array[fi] < 0) {
break;
}
}
for(bi = end-1; bi >= begin; --bi) {
bp *= array[bi];
if (array[bi] < 0) {
break;
}
}
int product = 1;
int pbegin = (fp>bp) ? fi+1 : begin;
int pend = (fp>bp) ? end : bi;
for (int i = pbegin; i < pend; ++i) {
product *= array[i];
}
return product;
}
No need to sort the array. Iterate on the array and find each element in the tree. Mark all the nodes visited during the traversal.
Use a hash to track the discovered numbers. O(g) extra space.
Time complexity : O(g+depth of tree)
public static boolean samePathGroup(Node node, int[] numbers) {
if (node == null || numbers.length == 0) {
return false;
}
Map<Integer, Boolean> hash = new HashMap<Integer, Boolean>();
for (int i = 0; i< numbers.length;++i) {
hash.put(numbers[i], Boolean.FALSE);
}
int count = 0, i = 0;
Integer cur = numbers[0];
while(node != null) {
if (hash.get(cur)) { // already discovered
if (++i == numbers.length) {
break;
}
cur = numbers[i];
continue;
}
Integer curNodeVal = node.get();
if (cur == curNodeVal) {
hash.put(cur, Boolean.TRUE);
++count;
if (++i == numbers.length) {
break;
}
cur = numbers[i];
continue;
} else if (cur < curNodeVal) {
node = node.left();
} else {
node = node.right();
}
if (hash.containsKey(curNodeVal) && !hash.get(curNodeVal)) {
++count;
hash.put(curNodeVal, Boolean.TRUE);
}
}
return (count == numbers.length);
}
@raj, the stack space would take only the space equivalent to height of the tree. In the average case, it would be logN. All I suggested was that we need not store all the leaf nodes, but just the last leaf node.
- prasanth September 22, 2013