leetCodeArray.java

// Problem 118. Pascal's Triangle
// Link: https://leetcode.com/problems/pascals-triangle/
// Solution: An element = one above + one before above
// Time: O(n^2), Space: O(n^2)
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (numRows == 0) { return result; }

    result.add(new ArrayList<>(Arrays.asList(1)));

    for (int row = 1; row < numRows; row++) {
        List<Integer> rowList = new ArrayList<Integer>();
        List<Integer> prevList = result.get(row - 1);

        rowList.add(1);

        for (int col = 1; col < row; col++) {
            rowList.add(prevList.get(col) + prevList.get(col - 1));
        }

        rowList.add(1);

        result.add(rowList);
    }

    return result;
}



// Problem 119. Pascal's Triangle II
// Link: https://leetcode.com/problems/pascals-triangle-ii/
// Solution: reversely traverse the list and set an element = itself + one before itself
// Time: O(n^2), Space: O(n)
public List<Integer> getRow(int rowIndex) {
    List<Integer> rowList = new ArrayList<Integer>();
    rowList.add(1);

    for (int i = 1; i <= rowIndex; i++) {
        for (int j = i - 1; j > 0; j--) {
            rowList.set(j, rowList.get(j - 1) + rowList.get(j));
        }

        rowList.add(1);
    }

    return rowList;
}



// Problem 121. Best Time to Buy and Sell Stock
// Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
// Solution: One pass, find the min price (valley) and max profit (peak)
// Time: O(n), Space: O(1)
public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int max = 0;
    for (int i = 0; i < prices.length; i++) {
        int price = prices[i];
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > max) {
            max = price - minPrice;
        }
    }

    return max;
}



// Problem 1. Two Sum
// Link: https://leetcode.com/problems/two-sum/
// Solution: One pass, find the min price (valley) and max profit (peak)
// Time: O(n), Space: O(1)



// 152. Maximum Product Subarray
// Link: https://leetcode.com/problems/maximum-product-subarray/
// Time: O(n)
func maxProduct(_ nums: [Int]) -> Int {
    if nums.count == 0 { return 0 }
    var currMax = nums[0]
    var currMin = nums[0]
    var globalMax = nums[0]

    for i in 1..<nums.count {
        let num = nums[i]
        if num > 0 {
            currMax = max(num, num * currMax)
            currMin = min(num, num * currMin)
        } else {
            let temp = currMax
            currMax = max(num, num * currMin)
            currMin = min(num, num * temp)
        }

        if currMax > globalMax { 
            globalMax = currMax
        }
    }

    return globalMax
}