JAVA DFS 17ms beat 99.28% so far


  • 12
    O

    The idea is simple:

    (1) Using a HashSet to store all the positions of the stones. So when you are trying to jump to a position, you will know whether there is a stone at that position or not.
    (2) Starting from the first valid position (the second stone if it is 1), you try to jump as far as possible. At each position, if you jumped x steps to this position, the next possible positions are position + x - 1, position + x and position + x + 1. If any of them is the last stone's position, then you can return true. If not, use DFS from the longest jump first.
    (3) This path finding process can be terminated much earlier if there are two stones that are too far away.

     public boolean canCross(int[] stones) {
            if (stones == null || stones.length == 0) {return false;}
            int n = stones.length;
            if (n == 1) {return true;}
            if (stones[1] != 1) {return false;}
            if (n == 2) {return true;}
            int last = stones[n - 1];
            HashSet<Integer> hs = new HashSet();
            for (int i = 0; i < n; i++) {
                if (i > 3 && stones[i] > stones[i - 1] * 2) {return false;} // The two stones are too far away. 
                hs.add(stones[i]);
            }
            return canReach(hs, last, 1, 1);
        }
        
        private boolean canReach(HashSet<Integer> hs, int last, int pos, int jump) {
            if (pos + jump - 1 == last || pos + jump == last || pos + jump + 1 == last) {
                return true;
            }
            if (hs.contains(pos + jump + 1)) {
                if (canReach(hs, last, pos + jump + 1, jump + 1)) {return true;}
            }
            if (hs.contains(pos + jump)) {
                if (canReach(hs, last, pos + jump, jump)) {return true;}
            }
            if (jump > 1 && hs.contains(pos + jump - 1)) {
                if (canReach(hs, last, pos + jump - 1, jump - 1)) {return true;}
            }
            return false;
        }
    

  • 1

    Brilliant! Here is my C++ version:

        unordered_set<int> set;
        bool dfs(int k, int pos, int destination)
        {
            if(pos > destination || set.find(pos) == set.end()) return false;
            if(pos == destination) return true;
            for(int i = 1; i >= -1; i--)
                if(k+i > 0 && dfs(k+i, pos+k+i, destination)) return true;
            return false;
        }
        bool canCross(vector<int>& stones) {
            int n = stones.size();
            if(n <= 1) return true;
            set.insert(0);
            for(int i = 1; i < n; i++)
            {
                set.insert(stones[i]);
                if(stones[i] - stones[i-1] > i) return false; //key point !!
            }
            return dfs(1, 1, stones[n-1]);
        }
    

  • 0
    S

    Great solution, fast and easy to understand!


  • 1
    T

    What's the time and space complexity? O(n^3) since we are checking 3 different paths at a given time?


  • 1
    T

    I think your solution just fits the OJ'case, cause when changing the recursive order, it will TLE


  • 1
    O

    @TobeABetterMan said in JAVA DFS 17ms beat 99.28% so far:

    I think your solution just fits the OJ'case, cause when changing the recursive order, it will TLE

    The recursive order is important here. You won't have the same performance if you change the order. For example, consider this case: you have lots of bills in $1, $5, $20, $ 100 and you want to get a total of $601. It is intuitive and reasonable to try to use $100 first for 6 times and then try other bills. You can also use all $1 to get $601 but you will need 601 of them, which takes lots of work. Following the same logic, I tried to make the jump as far as possible in each step, pretty much like trying the $100 first rather than the $1.


  • 0
    T

    Nice Job! It is easy to understand!


  • 2
    N

    If I remove this line

    if (i > 3 && stones[i] > stones[i - 1] * 2) {return false;} // The two stones are too far away. 
    

    with your original code, I will get a TLE.

    Obviously this line is doing a great job filtering unreachable inputs in the early stage. Why do you pick this standard? @odin


  • 0
    J

    The "far away" check is awsome!


  • 1
    S

    Time limit exceeded when your code got input =
    [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999,1998]

    Or the last element of the input array can be anything between the interval of [1043, 1998], the code will exceed time limit.


  • 0
    T

    @nlackx Actually it can be changed to if (i >= 3 && stones[i] - stones[i-1] > stones[i-1])
    The meaning of it is the jump from i-1 to i is at most (stones[i-1] - 1) + 1.


  • 0
    K

    public boolean canCross(int[] stones) {
    if(stones == null || stones.length == 0)
    return false;
    if(stones.length == 1)
    return true;
    if(stones[1] != 1)
    return false;
    HashSet<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < stones.length; i++){
    if(i > 2 && stones[i] - stones[i-1] > stones[i-1])//setting upper bound
    return false;
    set.add(stones[i]);
    }
    return dfs(1,1,stones[stones.length - 1], set);
    }
    //
    public boolean dfs(int i, int jump, int last, HashSet<Integer> set){
    if(i + jump == last || i + jump - 1 == last || i + jump + 1 == last)
    return true;

        if(set.contains(i + jump))
            if(dfs(i + jump, jump, last, set))
                return true;
        
      
        if(jump > 1 && set.contains(i + jump - 1))
            if(dfs(i + jump - 1, jump - 1, last, set))
                return true;
        
        if(set.contains(i + jump + 1))
            if(dfs(i + jump + 1, jump + 1, last, set))
                return true;
        
        return false;
    }
    

    This is my code, I do not know why this code is TLE?


Log in to reply
 

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