## james.porcelli@stonybrook.edu

BAN USERno need for extra memory. O(N) time, O(1), space

- james.porcelli@stonybrook.edu September 28, 2014```
public 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**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

yes greedy works for this problem. Theres no need for extra memory

- james.porcelli@stonybrook.edu September 28, 2014