Space cost from O(n^2) to O(2n) to O(n) to O(1) in C, all accepted as best


  • 2
    //AC - 8ms - O(n^2);
    int minimumTotal(int** triangle, int rSize, int *cSize)
    {
        int len = sizeof(int)*cSize[rSize-1];
        int *mins0 = (int*)malloc(len);
        int *mins1 = (int*)malloc(len);
        mins0[0] = triangle[0][0];
        for(int r = 1; r < rSize; r++)
        {
            for(int c = 0; c < cSize[r]; c++)
            {
                if(c == 0)
                {
                    mins1[c] = mins0[c]+triangle[r][c];
                    continue;
                }
                if(c == cSize[r]-1)
                {
                    mins1[c] = mins0[c-1]+triangle[r][c];
                    continue;
                }
                int t = triangle[r][c] + mins0[c];
                if(mins0[c] > mins0[c-1])
                    t = triangle[r][c] + mins0[c-1];
                mins1[c] = t;
            }
            int *t = mins0;
            mins0 = mins1;
            mins1 = t;
        }
        int t = mins0[0];
        for(int i = 0; i < cSize[rSize-1]; i++)
            if(t > mins0[i])
                t = mins0[i];
        return t;
    }
    

    //AC - 8ms - O(2n);
    int minimumTotal(int** triangle, int rSize, int *cSize)
    {
        int len = sizeof(int)*cSize[rSize-1];
        int *mins0 = (int*)malloc(len);
        int *mins1 = (int*)malloc(len);
        mins0[0] = triangle[0][0];
        for(int r = 1; r < rSize; r++)
        {
            for(int c = 0; c < cSize[r]; c++)
            {
                if(c == cSize[r]-1)
                    mins0[c] = mins0[c-1];
                int t = triangle[r][c] + mins0[c];
                if(c > 0 && mins0[c] > mins0[c-1])
                    t = triangle[r][c] + mins0[c-1];
                mins1[c] = t;
            }
            int *t = mins0;
            mins0 = mins1;
            mins1 = t;
        }
        int t = mins0[0];
        for(int i = 0; i < cSize[rSize-1]; i++)
            if(t > mins0[i])
                t = mins0[i];
        return t;
    }
    

    //AC - 8ms - O(n);
    int minimumTotal(int** triangle, int rSize, int *cSize)
    {
        int len = sizeof(int)*cSize[rSize-1];
        int *mins = (int*)malloc(sizeof(int)*len);
        mins[0] = triangle[0][0];
        for(int r = 1; r < rSize; r++)
        {
            for(int c = cSize[r]-1; c > -1; c--)
            {
                if(c == 0) mins[c] += triangle[r][c];
                else
                {
                    if(c == cSize[r]-1) mins[c] = triangle[r][c]+mins[c-1];
                    else mins[c] = triangle[r][c]+(mins[c]>mins[c-1]? mins[c-1]:mins[c]);
                }
            }
        }
        int t = mins[0];
        for(int i = 0; i < cSize[rSize-1]; i++)
            if(t > mins[i])
                t = mins[i];
        return t;
    }
    

    //AC - 8ms - O(1);
    int minimumTotal(int** triangle, int rSize, int *cSize)
    {
        for(int r = rSize-1; r > -1; r--)
            for(int c = 0; c < cSize[r]-1; c++)
                triangle[r-1][c] += triangle[r][c]>triangle[r][c+1]? triangle[r][c+1]:triangle[r][c];
        return triangle[0][0];
    }

  • 0
    Z

    You forgot to free all space malloced.
    And technically, there is no notation like O(2n). O(n) is enough, although there is difference between O(n) algorithms.


  • 0

    Space to be freed is not required, and of course if you'd like to, you can do it personally. As for the O(2n) here is just used to get others' attention to the space reduction process, the format is invalid as we all know.


  • 0
    S

    I think the last solution can not do since it will modify the original data. What do you think?


Log in to reply
 

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