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


  • 0
    B
        public boolean canCross(int[] stones) {
          SortedSet<Jump> jumps = new TreeSet<>();
          jumps.add(new Jump(1, 1));
    
          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, 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

  • 1

    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.


  • 0
    B

    I think you are right.

    I should change the title.

    Thank you for pointing out my mistake. Much appreciated.


Log in to reply
 

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