Triangle | Leetcode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

---

Solution: Allocate two arrays to hold the intermediate results. Initialize an array by copying the values from the last row of the triangle. Loop from the second last row of the triangle to the top. In each iteration, compute the minimum path sum of the next top row, and then swap the two arrays for next reuse. When done, the answer is stored as the first element of the current array.

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 0) return 0;
        if (triangle.size() == 1) return triangle.get(0).get(0);

        // Init two arrays to store computation results.
        List<Integer> lastRow = triangle.get(triangle.size() - 1);
        int maxSize = lastRow.size();
        int[] a = new int[maxSize];
        int[] b = new int[maxSize - 1];
        for (int i = 0; i < maxSize; i++) {
            a[i] = lastRow.get(i);
        }

        // Go from bottom-up and calculate minimum along the way.
        for (int i = triangle.size() - 2; i >= 0; i--) {
            List<Integer> curRow = triangle.get(i);
            for (int j = 0; j < curRow.size(); j++) {
                b[j] = Math.min(a[j], a[j + 1]) + curRow.get(j);
            }
            
            // Swap a and b.
            int[] temp = a;
            a = b;
            b = temp;
        }
        
        return a[0];
    }
}