Straight-forward 9ms 7-line c++ solution with explanation


  • 29

    Search for the last stone in a depth-first way, prune those exceeding the [k-1,k+1] range. Well, I think the code is simple enough and need no more explanation.

    bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
        for (int i = pos + 1; i < stones.size(); i++) {
            int gap = stones[i] - stones[pos];
            if (gap < k - 1) continue;
            if (gap > k + 1) return false;
            if (canCross(stones, i, gap)) return true;
        }
        return pos == stones.size() - 1;
    }
    

    This can pass OJ at 9ms but is inefficient for extreme cases. (update: new test cases are added and the solution above no longer passes OJ, please see the solution below which takes 62ms) We can memorize the returns with minimum effort:

    unordered_map<int, bool> dp;
    
    bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
        int key = pos | k << 11;
    
        if (dp.count(key) > 0)
            return dp[key];
    
        for (int i = pos + 1; i < stones.size(); i++) {
            int gap = stones[i] - stones[pos];
            if (gap < k - 1)
                continue;
            if (gap > k + 1)
                return dp[key] = false;
            if (canCross(stones, i, gap))
                return dp[key] = true;
        }
    
        return dp[key] = (pos == stones.size() - 1);
    }
    

    The number of stones is less than 1100 so pos will always be less than 2^11 (2048).
    Stone positions could be theoretically up to 2^31 but k is practically not possible to be that big for the parameter as the steps must start from 0 and 1 and at the 1100th step the greatest valid k would be 1100. So combining pos and k is safe here.


  • 0

    brilliant! however i cannot follow your idea, could u explain more about

      if (gap < k - 1) continue;
      if (gap > k + 1) return false;
    

    that is, why u can safely prune like this??


  • 0

    @HanMing.py
    Because the stones are given ascendingly.


  • 0
    Z

    Its time complexity is exponential.
    In this case below, it will TLE:

    [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,99999999]


  • 0
    V

    I also came up with the same solution and it passed OJ. However I don't think if this is the most efficient solution. The test cases do not cover a wide range of possibilities. If a test case involves a lot of back tracking then it might not be efficient.

    What do you think is the time complexity of this solution ?


  • 0

    @zehua2 @vigjadel
    Thanks for you comments. I have updated the post.


  • 1
    T

    said in Straight-forward 9ms 7-line c++ solution with explanation:

    int key = pos | k << 11;
    

    Why do you set the key this way?


  • 1
    T

    Wow I see it now. So you put both pos and k into the key for hashtable. It is the first time I see something like this. Very cool!


  • 0

    @tonygogogo I think @mzchen just wanna map 'pos' and 'k' to a unique number, since we can not determine whether the last node is reachable without the parameter 'k'.


  • 0
    D

    @Abu-Q how can you guarantee the key is unique by this way? I cannot get it. Please refer to http://stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way to produce the unique key by two integer


  • 1
    Z

    I think int key = pos | k << 11; will fail when we have a lot of stones in the range of [2^10, 2^11].


  • 0

    @zehua2 @dreamsclogs
    The number of stones is less than 1100 so pos will always be less than 2^11 (2048).
    Stone positions could be theoretically up to 2^31 but k is practically not possible to be that big for the parameter as the steps must start from 0 and 1 and at the 1100th step the greatest valid k would be 1100. So combining pos and k is safe here.
    (I have also added this comment to my post.)


  • 0

    @mzchen Actually, the greatest valid k at the 1100th step is 1100.


  • 0
    Z

    @mzchen I thought your pos is the position number of stone. I just noticed you are storing the index of stones, so you are right.


  • 0

    @StefanPochmann
    Ah, you are damn right! I got confused when I was writing the comment. Post updated.


  • 0
    Q

    @mzchen Execuse me, I ran your "unordered_map memorization" solution and it took 62 ms. Did I do it wrong?


  • 0

    @quesder it's not wrong. the non-memorizing version takes 9ms.


  • 0
    D

    What about [0,2]? Should we add if (pos ==0 && k!=gap) return false; after we got the gap?


  • 0

    @dukeforever No. Why?


  • 0
    W

    I am still quite confused about your complexity analysis.

    In your post, your "key" value is in the range of O(1100 << 11 + 1100), which means there are at most around O(n^2) statuses. However, you got another O(n) loop to find out next position. It means that your DP's complexity is actually O(n^3), though it might be difficult to construct a case for it.

    I believe a better way is to enumerate current position and last position, calculate the distance between them, denoted as k, then use binary search to find out next potential position with distance either k-1, k, or k+1. This solution has O(n^2) statuses but only O(log n) status transitions. Thus, O(n^2 log n) complexity can be achieved.


Log in to reply
 

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