james.porcelli@stonybrook.edu
BAN USERno need for extra memory. O(N) time, O(1), space
- james.porcelli@stonybrook.edu September 28, 2014public static int jump(int[] A) {
int jd = A[0];
int i = 0;
int jmps = 1;
int m = 0;
if(A.length == 1){
return 0;
}
if(i + jd >= A.length - 1){
return 1;
}
//O(n)
while(i < A.length - 1){
int n = i;
int j = i + 1;
for(; j <= jd && j < A.length - 1; j++){
if((A[j] + j) > m){
m = A[j] + j;
n = j;
}
if(m >= A.length - 1){
return jmps + 1;
}
}
jd = m;
m = 0;
jmps++;
i = n;
}
return jmps;
}
- james.porcelli@stonybrook.edu September 28, 2014I dont see why people are talking of printing the tree. The question says find the max in a BT, its unusually simple question, you just have to examine every node since its not a search tree.
- james.porcelli@stonybrook.edu September 22, 2014yea i wouldn't agree thats a great solution because ur making a big assumption on the input if it contains 1 number that is 2^32 -1 then thats a lot of space ur requiring
- james.porcelli@stonybrook.edu September 22, 2014the example he gives is not correct. 5 appears 2 e.g. even amount of times
- james.porcelli@stonybrook.edu September 22, 2014in ur example I/O 5 has even frequency
- james.porcelli@stonybrook.edu September 22, 2014I was thinking along the same lines, to use a bitmap and for each integer found if its set, unset it, else, set it. The value set in the end will be the value with even frequency, but i disregarded it because thats a lot of memory
- james.porcelli@stonybrook.edu September 20, 2014
yes greedy works for this problem. Theres no need for extra memory
- james.porcelli@stonybrook.edu September 28, 2014