9. Define a Function that Returns the nth Line of Pascal's Triangle

Define the Problem

This problem is fairly vague and requires a bit of clarification.

Jonathan: I'm sorry; I'm unfamiliar with Pascal's triangle. Can you please explain it to me?

Interviewer: Sure. Pascal's triangle is an arithmetic and geometric figure. Its first few rows look like this:

where each element of each row is either 1 or the sum of the two elements right above it.

Jonathan: Ah, I think I understand. So, would the next row would look like this?

Interviewer: Correct.

Jonathan: Great. Is it okay if I solve this using JavaScript?

Interviewer: Yes.

Think

Jonathan thinks about the problem for a bit. He's already starting to come up with some solutions and writes out some of his thoughts on the board. Here's his pseudocode:

// Create a function that will loop n number of times
// Create array for elements to be pushed into and returned. Start with the 3rd row (index 2).
// Create a temporary array to store temporary values
   // Start looping, starting at index 2
   // We can set the beginning and end of the array as 1
   // Otherwise, add the sum of the previous two
   // Copy the temp array into the main array
// After loop is over, return main array.

Write Code and Syntax

Now that the hard part is done, Jonathan just needs to write out the syntax to fill in the pseudocode. As Jonathan writes the code, he explains the syntax.

// Create a function that will loop n number of times
function pascalsTriangle(n) {
    // Create array for elements to be pushed into and returned. Start with the 3rd row (index 2).
    var mainArr = [1, 1],
    // Create a temporary array to store temporary values
        tempArr = [];
    // Start looping, starting at index 2
    for (var i = 2; i < n; i++) {
        Use another for loop to add elements into the temporary array.
        for (var j = 0; j < mainArr.length + 1; j++) {
            // We can set the beginning and end of the array as 1
            if (j == 0 || j == mainArr.length) {
                tempArr[j] = 1;
            // Otherwise, add the sum of the previous two
            } else {
                tempArr[j] = mainArr[j - 1] + mainArr[j];
            }
            console.log(j, tempArr);
        }
        // Copy the temp array into the main array
        mainArr = tempArr.slice();
    }
    // After loop is over, return main array.
    return mainArr;
}

Jonathan: I started out with a function that can take in a number, n, representing the number of rows in the triangle. From there, I decided to use an array as the data structure to hold the row and a temporary array to hold the elements in the loop.

I then used some conditional statements to set the beginning and end of the array to be 1, followed by an else statement that would otherwise add the sum to the array.

Next, I copied the temporary array by value into the mainArr and then will return the mainArr when the loops are done.

Interviewer: Is there a way that you can show all the rows? I'd like them displayed as each row on a log statement as well.

Jonathan: Sure, let me think about it.

Jonathan takes some time to think and writes out his thought process on the whiteboard.

// Helper function that outputs the rows, each on their own line.
// Function can use string concatenation and for loops to display each line separately.
/* The structure of the data going into the array might have to be structured a bit differently. This time,
   use an array of arrays to store each row's data.*/

// Helper function that outputs the rows, each on their own line.
// Function can use string concatenation and for loops to display each line separately.
function displayRows(arr) {
    var output="";
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr[i].length; j++) {
            output += "  " + arr[i][j] + "  ";
        }
        console.log(output);
        output="";
    }
}

/* The structure of the data going into the array might have to be structured a bit differently. This time,
   use an array of arrays to store each row's data.*/
function pascalsTriangle(n) {
    /* Create array for elements to be pushed into and returned. */
    var mainArr = [[1], [1,1]];
    var tempArr = [];
    for (var i = 2; i < n; i++) {
        for (var j = 0; j < mainArr[i - 1].length + 1; j++) {
            if (j == 0 || j == mainArr[i - 1].length) {
                tempArr[j] = 1;
            } else {
                tempArr[j] = mainArr[i - 1][j - 1] + mainArr[i - 1][j];
            }
        }
        mainArr[i] = tempArr.slice();
    }
    // After loop is over, return main array.
    displayRows(mainArr);
}



pascalsTriangle(5);

Jonathan: Okay, so I had to change the array and for loops in the original function a bit so that I would be storing each row of data inside of the main array. This way, I can use a simple helper function to loop through each of the subarrays and then output them as a string in the console.

Interviewer: Okay.