Java O(n^2) Easy to Understand, Optimal Solution


  • 0
    B

    Explanation
    The point to this question is to carefully construct Pascal's triangle row by row. For a non-1 element within our triangle, we note that it's computed as the sum of the above row's two elements.

    Time Complexity
    The time complexity is O(n^2) where n is numRows, since for each row i, there are exactly i number of elements. This translates to 1 + 2 + ... + n-1 + n = n(n-1)/2, which is O(n^2).

    class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> result = new ArrayList<>(numRows);
    
            // Contruct our triangle row by row
            for (int i = 0; i < numRows; i++) {
                List<Integer> row = new ArrayList<>();
    
                // Row i has i+1 elements
                for (int j = 0; j < i + 1; j++) {
                    // Add 1 at row's leftmost, rightmost indices
                    if (j == 0 || i == j) {
                        row.add(1);
                    } 
                    // Compute value based on previous row's 2 nums
                    else {
                        int sum = result.get(i-1).get(j-1) + 
                                  result.get(i-1).get(j);
                        row.add(sum);
                    }
                }
    
                result.add(row);
            }
            return result;
        }
    }
    

Log in to reply
 

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