Nine notes

Note: This is an extension of House Robber.

Given a binary tree, find the maximum path sum.

Description:

Follow up for problem “Populating Next Right Pointers in Each Node”.

Given a binary tree

Design a data structure that supports all following operations in average O(1) time.

Design a data structure that supports all following operations in average O(1) time.

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

O(n) time O(1) space one pass solution

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, profit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                profit = Math.max(profit, prices[i] - min);
            }
        }
        return profit;
    }
}