Java O(k) Space Solution by memorizing the local difference


  • 0
    Z
    public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> res = new ArrayList<>();
            if (rowIndex < 0) return res;
            // O(k) Memory
            int[] prevLevel = new int[rowIndex+1];
            for (int i = 0; i < rowIndex + 1; ++i) {
                int diff = 0;
                for (int index = 0; index <= i; ++index) {
                    if (index == 0 || index == i) {
                        prevLevel[i] = 1;
                    } else {
                        int newVal = prevLevel[index] + prevLevel[index-1] - diff;
                        diff = newVal - prevLevel[index];
                        prevLevel[index] =  newVal;
                    }
                }
            }
            
            // Construct the result
            for (int num : prevLevel) {
                res.add(num);
            }
            return res;
        }
    }
    

Log in to reply
 

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