Here is my brief O(k) solution


  • 117
    L

    The basic idea is to iteratively update the array from the end to the beginning.

    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> A(rowIndex+1, 0);
            A[0] = 1;
            for(int i=1; i<rowIndex+1; i++)
                for(int j=i; j>=1; j--)
                    A[j] += A[j-1];
            return A;
        }
    };

  • 39
    X

    your ans is really a good solution,just as mine,but my sol is java version

    public static List<Integer> getRow2(int rowIndex) {
    	List<Integer> ret = new ArrayList<Integer>();
    	ret.add(1);
    	for (int i = 1; i <= rowIndex; i++) {
    		for (int j = i - 1; j >= 1; j--) {
    			int tmp = ret.get(j - 1) + ret.get(j);
    			ret.set(j, tmp);
    		}
    		ret.add(1);
    	}
    	return ret;
    }
    

  • 11
    B

    Also a java version...
    idea stolen from the LongsPeak.

    slightly more efficient (without using ArrayList.set(...))

    public List<Integer> getRow(int rowIndex) {
          Integer[] result =  new Integer[rowIndex + 1];
          Arrays.fill(result, 0);
          result[0] = 1;
          for(int i = 1; i < rowIndex + 1; i++)
            for(int j = i; j >= 1; j--)
              result[j] += result[j - 1];
          return Arrays.asList(result);
        }

  • 11
    K

    A little little improvement in C++ version, make the best use of vector's fill constructor:

    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> ints(rowIndex + 1, 1);
            for(int row = 0; row < rowIndex; row++) {
                for(int col = row; col > 0; col--) {
                    ints[col] += ints[col - 1];
                }
            }
            return ints;
        }
    };
    

    The similar improvement can also be applied to Java version:

    public class Solution {
        public List<Integer> getRow(int rowIndex) {
            Integer[] integers = new Integer[rowIndex + 1];
            Arrays.fill(integers, 1);
            for (int row = 0; row < rowIndex; row++) {
                for (int col = row; col > 0; col--) {
                    integers[col] += integers[col - 1];
                }
            }
            return Arrays.asList(integers);
        }
    }

  • 1
    D

    Same idea in Python.

    class Solution:
        # @return a list of integers
        def getRow(self, rowIndex):
            
            array = [1]*(rowIndex+1)
    
            for i in range(1,rowIndex+1):
                for j in range(i-1,0,-1):
                    array[j] += array[j-1]
    
            return array

  • 0
    J

    Arrays.fill(result, 0);? correct?


  • 4
    R

    can you please explain a bit more why this is O(k)?


  • 0
    Q

    int row = 1;


  • 0
    V

    if it would make nicer, we can remove tmp by , ret.set(j, ret.get(j-1) + ret.get(j));


  • 0
    A
    This post is deleted!

  • 0
    A

    this is my answer, use multiply ,i do not understand how the space could be o(k)?
    class Solution {
    public:
    vector<int> getRow(int rowIndex){
    vector<int> vPascal;
    if (rowIndex < 0)
    { return vPascal; }
    int iCnr = 1;
    for (int iIndex = 0; iIndex <= rowIndex; iIndex++)
    {
    if (iIndex)
    {
    iCnr = iCnr * (rowIndex + 1 - iIndex) / (iIndex);
    }
    vPascal.push_back(iCnr);
    }
    return vPascal;
    }
    };


  • 1
    Z

    Same idea, just written in C.

    int *array = malloc((rowIndex + 1) * sizeof(int));
    
    for (int i = 0; i <= rowIndex ; i++) {
        array[i] = 0;
    }
    
    array[0] = 1;
    
    for (int i = 0; i <= rowIndex ; i++) {
        for (int j = i; j > 0; j--) {
            array[j] += array[j-1];
        }
    }
    
    *returnSize = rowIndex + 1;
    return array;
    

  • 0
    V

    right, it is unnecessary to use temporary variable


  • 0
    T

    nice. I use two vector.


  • 0
    D

    //int *array = malloc((rowIndex + 1) * sizeof(int));
    int *array = calloc((rowIndex + 1) ,sizeof(int));


  • 0
    D

    i can not understand the algorithm very well , who can explain it detail . thanks


  • 0
    D

    I can not understand the algorithm very well , who can explain it detail .


  • 0
    H

    2 "ret.add(1)" can be reduced to 1, and jut put it before the inner for-loop


  • 0
    M
    This post is deleted!

  • 0
    M

    @LongsPeak
    Excellent solution


Log in to reply
 

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