Share my python solution with O(1) extra space


  • 0
    D

    Since each element is the sum of two "shoulder" element in the last row, we can add up consecutive elements in a row backward to get the new row

    class Solution:
        # @param {integer} rowIndex
        # @return {integer[]}
        def getRow(self, rowIndex):
    		# fill row with 1s
    		row  = [1] * (rowIndex + 1)
    		for i in xrange(2, rowIndex+1):
    			for j in xrange(i-1, 0, -1):
    				# each element is the sum of two “shoulder elements”
    				row[j] += row[j-1]
    
            return row

  • 0
    V

    isnt it O(nlogn) extra space? you created a 2-d array


  • 0
    D

    Row is just a list, not 2D array.

    O(1) is for extra space, that is, the row itself (since we need to return it) is not counted.


Log in to reply
 

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