# An AC solution without dynamic programming. Short and very easy to understand

• ``````    public boolean canCross(int[] stones) {
SortedSet<Jump> jumps = new TreeSet<>();

for(int i = 1; i < stones.length; i++) {
int stone = stones[i];
Jump next;
while(!jumps.isEmpty() && (next = jumps.first()).dest <= stone) {
jumps.remove(next);
if(next.dest == stone) {
if(i == stones.length - 1) return true;
int speed = next.speed;
jumps.add(new Jump(stone + speed + 1, speed + 1));
if(speed != 1) jumps.add(new Jump(stone + speed - 1, speed - 1));
}
}
}

return false;
}

private static class Jump implements Comparable<Jump> {
final int dest;
final int speed;

public Jump(int dest, int speed) {
this.dest = dest;
this.speed = speed;
}

@Override
public int compareTo(Jump o) {
int ret = Integer.compare(dest, o.dest);
if(ret == 0) ret = Integer.compare(speed, o.speed);
return ret;
}
}
``````

Key notes:

1. A sortable data struct is key to this solution.
2. `TreeSet` can filter out all duplicated moves

• I don't think it's O(NlogN). For example, for input [0, 1, 2, 3, ..., 999] you have 85,331 calls of `add`. Much more than the at most 3,000 your analysis claims. Also, your set grows to size 999. For input [0, 1, 2, 3, ..., 9999] you have 2,788,043 `add` calls and your set grows to size 9999.

• I think you are right.

I should change the title.

Thank you for pointing out my mistake. Much appreciated.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.