C++ 9 lines O(n^2) iterative DP solution


  • 4

    This solution is not as fast as some other O(n^2) DFS solutions possibly due to the OJ test cases. But it's simple and clean.
    Special thanks @farahcs and @vesion for correcting the bug in previous code.

    bool canCross(vector<int>& stones) {
            // To record available last steps to reach current position. Position 0 need 0 step to be reached
            unordered_map<int, unordered_set<int>> steps = {{0, {0}}};  
            
            for (int pos : stones) {
                for (auto it = steps[pos].begin(); it != steps[pos].end(); it++) {  // record all future reachable positions
                    if (*it - 1) { steps[pos + *it - 1].insert(*it - 1); }
                    steps[pos + *it].insert(*it);
                    steps[pos + *it + 1].insert(*it + 1);
                }
            }
            
            return steps[stones.back()].size();                                     // check if the last position is reachable
        }
    

  • 0
    Y

    Nice solution! Thx!


  • 0
    Y

    But your solution failed in one test case now.


  • 0

    @Yuanhui
    Thanks for pointing it out. I've tested on my local machine and it actually passed. Probably it's the OJ's problem.

    @1337c0d3r can you help verify/fix it? Thanks!
    BTW the failing case is:
    [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,1035]


  • 0
    Y

    @soamaaazing Well, some DP solutions still work, like this one:

    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            unordered_map<int, unordered_set<int>> m;
            vector<int> dp(stones.size(), 0);
            m[0].insert(0);
            int k = 0;
            for (int i = 1; i < stones.size(); ++i) {
                while (dp[k] + 1 < stones[i] - stones[k]) ++k;
                for (int j = k; j < i; ++j) {
                    int t = stones[i] - stones[j];
                    if (m[j].count(t - 1) || m[j].count(t) || m[j].count(t + 1)) {
                        m[i].insert(t);
                        dp[i] = max(dp[i], t);
                        break;
                    }
                }
            }
            return dp.back() > 0;
        }
    };
    

    I didn't figure out what is wrong with your solution.


  • 0

    @Yuanhui
    Thanks for the alternative DP solution. It's brilliant and faster than mine.
    I've modified your code to make it even faster by dropping ordered_map, and it only takes 9ms to finish.

    bool canCross(vector<int>& stones) {
            // maxHop[i] is the maximum possible hop to reach stone[i]
            int maxHop[stones.size()]; memset(maxHop, 0, sizeof(maxHop));
            
            for (int start = 0, i = 0; i < stones.size(); i++) {
                // start is the largest possible position to reach stone[i]
                while (maxHop[start] + 1 < stones[i] - stones[start]) { start++; }
                
                for (int j = start, hop = stones[i] - stones[j]; j < i && maxHop[i] == 0; hop = stones[i] - stones[++j]) {       
                    // record the maximum possible hop to reach stone[i]
                    if ((j == 0 || maxHop[j] > 0) && maxHop[j] - 1 <= hop && hop <= maxHop[j] + 1) { maxHop[i] = hop; }
                }
            }
            
            return maxHop[stones.size() - 1] > 0;
    }
    

    However, I still believe my original code shouldn't fail the test case...


  • 0

    @Yuanhui
    I've been thinking about your solution for a while and still didn't figure out one thing:

    DP[i] means the maximum possible hop to get to stone[i].
    I believe the meaning of this DP solution indicates that if it's possible to get to the destination, always taking max possible hop every time has to be one of working ways.
    However, isn't there a situation where the destination is reachable but not by always taking max hops?


  • 0
    Y

    That is also my first concern, so I use map to save all possible hops for one stone. DP[i] means max hop from stones[i], not hop to stones[i], which means stones[i] is reachable.


  • 0

    @Yuanhui
    But in your code the map and DP were updated at exactly same place, which means map doesn't really contain all possible hops, but rather it's only max hop to stones[i] (same as DP).
    Is above correct?


  • 0

    @soamaaazing I wish I saw your comment about OJ earlier. This failing test case wasted me a lot of time :-(


  • 0

    @Yuanhui
    New test cases added and proved our suspicion: [0,1,3,6,10,13,15,18]


  • 0

    @zzg_zzm
    Sorry about that.
    I tested my code on local machine and the result was correct, but OJ gave me a different result, which is a failure.
    I've pinned administrators to fix it.


  • 0
    L

    Yeah, you need remove the 'break' in the for loop to let the map record all possible jump capabilities.


  • 0
    P

    I find that if use set instead of unordered_set will pass the test. Although I still don't figure out why.


  • 1
    F

    @soamaaazing said in C++ 9 lines O(n^2) iterative DP solution:

    bool canCross(vector<int>& stones) {
    // To record available last steps to reach current position. Position 0 need 0 step to be reached
    unordered_map<int, unordered_set<int>> steps = {{0, {0}}};

        for (int pos : stones) {
            for (auto it = steps[pos].begin(); it != steps[pos].end(); it++) {  // record all future reachable positions
                steps[pos + *it - 1].insert(*it - 1);
                steps[pos + *it].insert(*it);
                steps[pos + *it + 1].insert(*it + 1);
            }
        }
        
        return steps[stones.back()].size();                                     // check if the last position is reachable
    

    }

    The only issue with your code is that you don't check if (*it-1 and *it >0). Given that frog moves froward you are only supposed to insert if these are positive i.e:

    if(*it-1>0) steps[pos + *it - 1].insert(*it - 1);
    if(*it>0) steps[pos + *it].insert(*it);
    steps[pos + *it + 1].insert(*it + 1);

    But nice Solution!


  • 0
    L

    Could you please let me know the time complexity?

    Thanks!


  • 2

    Concise O(n^2) solution! For the wrong test case, just check if *it-1 is negative.
    Rewrite as below, pass LC.

    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            unordered_map<int, unordered_set<int>> dp;
            dp[0].insert(0);
            for (int pos : stones) {
                for (int step : dp[pos]) {
                    if (step-1 > 0) dp[pos + step-1].insert(step-1);
                    dp[pos + step].insert(step);
                    dp[pos + step+1].insert(step+1);
                }
            }
            return !dp[stones.back()].empty();
        }
    };
    

  • 1
    Z

    not exactly O(n^2)...
    the insert need O(logn)
    so at least O(n^2*logn)


  • 0
    Z

    @littilecrab STL use Red Black Tree to implement unordered_map, the insert operation need O(logn), so the total time is O(n^2*logn). in my op..


  • 0
    Y

    @Zafreedom Actually map is based on RBT, unordered_map is based on hash table.


Log in to reply
 

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