My Java 1ms solution. Can anyone tell me the runtime?


  • 0
    R

    I think the runtime may be O(N^2) as well as the space complexity. Anyone could tell me about that?

            public List<List<Integer>> generate(int numRows) {
        		if (numRows < 1)
        			return new ArrayList<>();
        		
        		List<List<Integer>> res = new ArrayList<>();
        		
        		// Row 1
        		List<Integer> row1 = new ArrayList<>();
        		row1.add(1);
        		res.add(row1);
        		
        		if (numRows == 1)
        			return res;
        		
        		// Row2
        		List<Integer> row2 = new ArrayList<>();
        		row2.add(1);
        		row2.add(1);
        		res.add(row2);
        		
        		if (numRows == 2) {
        			return res;
        		}
        		
        		int now = 2;
        		
        		while(now < numRows) {
        			int i = 0;
        			int j = 1;
        			List<Integer> row = new ArrayList<>();
        			row.add(1);
        			List<Integer> lastRow = res.get(now - 1);
        			while(j < lastRow.size()) {
        				row.add(lastRow.get(i) + lastRow.get(j));
        				i++;
        				j++;
        			}
        			row.add(1);
        			res.add(row);
        			now++;
        		}
        		return res;
        	}

Log in to reply
 

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