C Solution and Optimization


  • 0
    A

    My original solution:

    int** generate(int numRows, int** columnSizes) {
        int **result = malloc(numRows * sizeof(int *));
        *columnSizes = malloc(numRows * sizeof(int));
        
        int n = 0;
        
        (*columnSizes)[n] = 1;
        result[n] = malloc(sizeof(int));
        result[n][0] = 1;
        
        for (++n; n < numRows; ++n) {
            (*columnSizes)[n] = n + 1;
            result[n] = malloc((n + 1) * sizeof(int));
            
            for (int k = 0; k <= n; ++k) {
                if (k == 0) {
                    result[n][k] = 1;
                } else if (k == n) {
                    result[n][k] = 1;
                } else {
                    result[n][k] = result[n - 1][k - 1] + result[n - 1][k];
                }
            }
        }
        
        return result;
    }
    

    This gave me 3 ms runtime.

    Too much mis-predication penalty in the for loop. Optimized to 0 ms:

    int** generate(int numRows, int** columnSizes) {
        int **result = malloc(numRows * sizeof(int *));
        *columnSizes = malloc(numRows * sizeof(int));
        
        int n = 0;
        
        (*columnSizes)[n] = 1;
        result[n] = malloc(sizeof(int));
        result[n][0] = 1;
        
        for (++n; n < numRows; ++n) {
            (*columnSizes)[n] = n + 1;
            result[n] = malloc((n + 1) * sizeof(int));
            
            result[n][0] = 1;
            result[n][n] = 1;
            for (int k = 1; k < n; ++k) {
                result[n][k] = result[n - 1][k - 1] + result[n - 1][k];
            }
        }
        
        return result;
    }
    

Log in to reply
 

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