What is the logical error I am facing in Pascal's Triangle code?

Samik Pandit 0
Viewed 25

Wrong Code:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> finallist = new ArrayList<List<Integer>>();
        if (numRows == 1){
            List<Integer> list1 = new ArrayList<>();
            list1.add(1);
            finallist.add(list1);
            return finallist;
        }
        else if (numRows == 2){
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            list1.add(1);
            list2.add(1);
            list2.add(1);
            finallist.add(list1);
            finallist.add(list2);
            return finallist;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        List<Integer> alist = new ArrayList<>();
        list1.add(1);
        list2.add(1);
        alist.add(1);
        list2.add(1);
        alist.add(1);
        finallist.add(list1);
        finallist.add(list2);
        for (int j = 3;j <= numRows;j++) {
            List<Integer> list3 = new ArrayList<>();
            list3.add(1);
            for (int i = 0; i < alist.size() - 1; i++) {
                list3.add(alist.get(i) + alist.get(i + 1));
            }
            list3.add(1);
            finallist.add(list3);
            alist.clear();
            alist.addAll(list3);
            list3.clear();
        }
        return finallist;
    }
}

Output shown : Input: 5

Output: [[1],[1,1],[],[],[]]

Expected: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Correct Code:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> finallist = new ArrayList<List<Integer>>();
        if (numRows == 1){
            List<Integer> list1 = new ArrayList<>();
            list1.add(1);
            finallist.add(list1);
            return finallist;
        }
        else if (numRows == 2){
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            list1.add(1);
            list2.add(1);
            list2.add(1);
            finallist.add(list1);
            finallist.add(list2);
            return finallist;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        ArrayList<Integer> alist = new ArrayList<>();
        list1.add(1);
        list2.add(1);
        alist.add(1);
        list2.add(1);
        alist.add(1);
        finallist.add(list1);
        finallist.add(list2);
        for (int j = 3;j <= numRows;j++) {
            List<Integer> list3 = new ArrayList<>();
            list3.add(1);
            for (int i = 0; i < alist.size() - 1; i++) {
                list3.add(alist.get(i) + alist.get(i + 1));
            }
            list3.add(1);
            finallist.add(list3);
            alist.clear();
            alist.addAll(list3);
        }
        return finallist;
    }
}

In my wrong code,I was declaring the 'list3' outside the outer loop. Added the 'alist' to my 'finallist' which is the actually my answer. The elements got copied to 'alist' again from 'list3' after clearing the previous 'alist'.As I had to enter elements for the next row in my 'list3', I was clearing the elements of 'list3' in order to enter elements for next row.

In my correct code, the only difference is that I declared 'list3' outside the inner loop but inside the outer loop for which I need not to clear 'list3' for next row iteration.It automatically will be cleared as 'list3' is being called/declared outside the inner loop ,i.e.elements are automatically refreshed.

I think most probably I am making some logical error in the 'object.clear' part in ""Wrong Code"" for which the elements are not inserted in the final one but getting cleared.

Can anyone clear my doubts?

pascals-triangle arraylist nested-lists java list
1 Answers

The problem in the wrong code is, that every list3 instance you add in the outer loop to the alist is getting cleared.

You see, by adding a List x to another List y, you are not copying the values from the list x to the other list y, but you are giving the reference to list x to the list y.

And by clearing list x, after you give list x to list y, you clear the all values.

Thats why after the first two list (which you do not clear), all lists added in the loop to the final list, are references to empty lists, hence:

[[1], [1, 1], [], [], []]

You can see the final list like so:

finnalList[l1, l2, l3, l4, l5]

l1 -> List[[1]]

l2 -> List[[1, 1]]

l3 -> List[[]]

l4 -> List[[]]

l5 -> List[[]]

You are not copying the values inside the list, but giving references to these list (that you clear in the wrong code) to the final list.

ILikeTrains0
Related