Interview preparation -DSA #day1

Photo by Florian Olivo on Unsplash

Getting a job in product based company is a bit tough task. I am preparing for Product based companies and explaining someone helps me to remember the patterns.

I am selecting the questions randomly.

Question : Pascal Triangle 1

link to question : https://leetcode.com/problems/pascals-triangle/

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Each number is calculated by sum of the previous row’s, previous column and present column’s number. To better understand lets see an sample case:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

There are couple of ways to solve this problem. All of the solutions work with all test cases.

SOLUTION 1:

First hard-coding a list to consist all one’s like [[1],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1]]. then as the first and second rows no need any change, starting from 3rd row i.e index 2.

Now for every row, the columns start from 1 to the last second element as the first and last element stays the same.

Instead of seeing it as a triangle, see it as matrix so the indexes will make sense. (computing time and space will be easier)

Time Complexity: O(n*n) [2 for loops used to loop through row and column]

Space Complexity: O(n*n) [2d list is used]

SOLUTION 2:

Here we have initialized first row. then for every row, we store the the [-1] indexed row in temp and an additional [0] at beginning and end. This allows to add 2 numbers and append in the new temp row list.

Time Complexity: O(n*(len + 1))

Space Complexity: O(n*n) [2d list is used]

SOLUTION 3:

This solution is similar to first solution, but here we use an empty list and then try to add elements. The logic is, if its first or last element then append 1, else then adding previous rows, present column and previous column.

Time Complexity: O(n*n)

Space Complexity: O(n*n) [2d list is used]

Thanks for your patience and I am glad you could learn something. I’ll be back with another random question.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store