Java O(k) solution with explanation


  • 11
    Y

    When generating each row, we can use the previous row directly, so this way we only use O(k) space with k being the number of row. For each new row, we append a 1, letting j iterate from i - 1 backward to 1, and set the jth element as res.set(j, res.get(j-1) + res.get(j)). For example, when k = 4, the process goes like this:

    k == 0
    [1] 
    k == 1
    [11] 
    k == 2
    [111]  add 1
    [121]  calculate jth spot
    k == 3
    [1211]  add 1
    [1331]   calculate jth spot
    k == 4
    [13311]  add 1
    [14641]  calculate jth spot
    

    Java

       public List<Integer> getRow(int rowIndex) {
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i <= rowIndex; i++) {
                res.add(1);
                for(int j = i-1; j > 0; j--) {
                    res.set(j, res.get(j-1) + res.get(j));
                }
            }
            return res;
        }

  • 0
    H

    why this is O(k), I am a little bit confused.


Log in to reply
 

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