tarun.gupta.pec
BAN USERI think using a BFS and maintaining lastNode of next level can help us set the neighbours. I am using Deque to peek the last node in the queue.
Below is solution in java.
public void setNeighbours() {
if (root == null) {
return;
}
TreeNode2 lastNode = root;
Deque<TreeNode2> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode2 node = queue.remove();
if (node.getlChild() != null) {
queue.add(node.getlChild());
}
if (node.rChild != null) {
queue.add(node.getrChild());
}
if (lastNode == node) {
node.setNeighbour(null);
lastNode = queue.peekLast();
} else {
node.setNeighbour(queue.peekFirst());
}
System.out.println(node + " : " + node.getNeighbour());
}
}
For deletion determining the position of element in the array is not O(1).
- tarun.gupta.pec December 25, 2015This can be solved in O(n) time. If we only consider ASCII characters array of 256 numbers is required.
Whenever a character is found its corresponding ASCII value index in array is changed to 1 to remember that this character is already seen. Whenever a new character comes in it is checked with its corresponding ASCII value index in array and if it is already seen then loop breaks.
Remeber this code treats upper and lower case letters differently.
char str[] = "tarun gupta";
int l = strlen(str);
int flag[256]={0};
for( i=0 ; i<l ; i++){
if ( flag[str[i]]!=0 ){
printf("The first repeating character is %c", str[i]);
break;
}
else{
flag[str[i]] = 1;
}
}
The key concept of the question is water is filled over a tower only if there is a tower of greater height on the left AS WELL AS on right.
This can be solved in O(n) or 3*O(n)
For each tower calculate the max height of tower on its left and right. Then min( max_on_left, max_on_right ) - tower(height) is the water filled over that tower. Sum the water on top of each tower. Remember if on either side there is no tower with height greater than the height of current tower in consideration then water cant filled over that tower.
Time Compexity 3O(n), Space Complexity 3n
#include<stdio.h>
#define n 5 // n is the number of towers
int min(int a, int b){
return a<=b ? a : b;
}
void main(){
int th[n]={1,5,3,7,2}; // th: tower height
int mol[n],mor[n]; // mol: max on left, mor: max on right
int max=0;
int i = 0;
for(i=0; i<n; i++){
if( th[i] >= max){
max = th[i];
mol[i] = 0;
}
else{
mol[i] = max;
}
}
max = 0;
for(i=n-1; i>=0; i--){
if( th[i] >= max){
max = th[i];
mor[i] = 0;
}
else{
mor[i] = max;
}
}
int sumwater = 0;
for( i=0; i<n; i++){
if(mol[i]!=0 && mor[i]!=0){
sumwater+= min(mol[i],mor[i]) - th[i];
}
}
printf("Water accumalation is %d", sumwater);
}
Pseudo code
Each element of stack keeps a track of the minimum element below it. To retrieve the minimum element of the stack return the minimum element of top element.
#define max 100;
int Stack[max], minStack[max];
int top = -1;
void push(int elm, int *stack){
Stack[++top]=elm;
if ( top==0 ){
minStack[top]=elm;
}
else{
if(minStack[top-1]<elm){
minStack[top] = minStack[top-1];
}
else{
minStack[top]=elm;
}
}
void pop(){
top--;
}
int min(){
return minStack[top];
}
- tarun.gupta.pec April 07, 2016