chrisynchen

public int minPathSum(int[][] grid) {
        
        final int[][] dp = new int[grid.length][grid[0].length];
        
        dp[0][0] = grid[0][0];
        
        for(int i =0; i<grid.length;i++){
            for(int j =0; j<grid[0].length;j++){
                if (i == 0 && j == 0) continue;

chrisynchen

Given the root of a binary tree, split the binary tree into two subtrees by removing one edge such that the product of the sums of the subtrees is maximized.

Return the maximum product of the sums of the two subtrees. Since the answer may be too large, return it modulo 109 + 7.

Note that you need to maximize the answer before taking the mod and not after taking it.

 
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 110

chrisynchen

743. Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, 
a list of travel times as directed edges times[i] = (ui, vi, wi), 
where ui is the source node, vi is the target node, 
and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. 
If it is impossible for all the n nodes to receive the signal, return -1.

chrisynchen

// result: 0.10666666666666667
public class Result {

    static double result = 0;

    public static void main(String[] args) {
        User[] raw = {new User(0.1, 75), new User(0.16, 74.9),
                new User(0.11, 74.8), new User(0.12, 74.4),
                new User(0.09, 74.4), new User(0.07, 74.3),
                new User(0.09, 74.2), new User(0.09, 74.2),

chrisynchen

class Solution {
    public int[] finalPrices(int[] prices) {
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < prices.length; i++) {
            while(!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                int prevIndex = stack.pop();
                prices[prevIndex] -= prices[i];
            }
            stack.push(i);

chrisynchen

class Solution {
    public int[] finalPrices(int[] prices) {
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < prices.length; i++) {
            while(!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                stack.pop();
            }
            if(!stack.isEmpty()) {
                prices[i] -= prices[stack.peek()];

chrisynchen

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < nums2.length; i++) {
            map.put(nums2[i], i);
        }
        
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < nums2.length; i++) {

chrisynchen

class Solution {
    public long subArrayRanges(int[] nums) {
        //Monotonic Stack O(n)
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] leftMin = new int[n];
        int[] rightMin = new int[n];
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        for(int i = 0; i < n; i++) {

chrisynchen

// (X) 63 / 67 test cases passed.
class Solution {
    long BASE = 26;
    long MOD = 1 << 31 - 1;
    public String longestDupSubstring(String s) {
        //rolling hash + binary search
        //ex: banana, is any length contains duplicate string?
        //(Y)length1: b, a, n
        //(Y)length2: ba, an, na
        //(Y)length3: ban,ana,nan

chrisynchen

class Solution {
    public int shortestPathLength(int[][] graph) {        
        if(graph.length == 1) return 0;
        
        int n = graph.length;
        //for example n = 0,1,2. The bitmask finish criteria = 111(7)
        //so we can easily count (1 << 3) - 1 = 7 or use pow.
        int finish = (int) (1 << n) - 1;
        
        Queue<int[]> queue = new LinkedList<>();