C# simple O(k) space complexity solution


  • 0
    S

    Think how we can move from k-1 to k (for example: 1331 -> 14641) in single for loop. The basic idea is that second value of the sum (3 in this example) will become the first value of the sum in the next iteration of the loop. Since we are overwriting the second value, we store it in a variable.

    public IList<int> GetRow(int rowIndex) {
            int[] result = new int[rowIndex + 1];
            result[0] = 1;
            
            for(int i = 1; i <= rowIndex; i++){
                int first = result[0];
                for(int j = 1; j < i; j++){
                    int second = result[j];
                    result[j] = first + second;   
                    first = second;
                }
                
                result[i] = 1;
            }
            return new List<int>(result);
        }
    

Log in to reply
 

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