Chris Chen chrisynchen

## gist:72faf4c3f8bfb4e11339a8bf8976b1ec
<!DOCTYPE html>
 <html style="background-color:#F6F7FC;">
 <head>
     <meta name="viewport" content="width=device-width, initial-scale=1.0">
     <style>
 /* width */
 ::-webkit-scrollbar {
   width: 10px;
 }


## MinEmptySpaceInChessboard
public class MinEmptySpaceInChessboard {

    /**
     * From Google:
     * Given n * n chessboard and pos array means position (i, j) has chess.
     * Calculate min distance from each chess to the empty space.
     * ex: n = 3, pos = {{0, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}, {2, 0}}
     * ans: [1, 2, 2, 1, 1, 1]
     *
     * follow up: if n = ∞ , pos has just few chess. How to improve?

## gist:6859096634cba1ec894fdf2000efd9ef
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        int max = 0;
        for(int e: nums) {
            sum += e;
            max = Math.max(max, e);
        }

        if(sum % k > 0 || max > (sum / k)) return false;

## gist:68591760c95ca595560ba2b0641f59c8
//dijkstra TLE
public int minimumObstacles(int[][] grid) {
        //dijkstra

        int[][] ref = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};

        int[][] minDistance = new int[grid.length][grid[0].length];

        for(int[] e: minDistance) {
            Arrays.fill(e, Integer.MAX_VALUE);

## gist:f9831e3169f4fb80ddcfdf986e90ad17
//Total time complexity O(n), space complexity is O(k)
public class findMoreThanKthLargest {
    public static void main(String[] args) {
        int[][] example = new int[][]{{1426828011, 9},
                {1426828028, 350},
                {1426828037, 25},
                {1426828056, 231},
                {1426828058, 109},
                {1426828066, 111}};

## gist:8b6816cee07c8e6d4a9cff33e8f37b9b
public int largestCombination(int[] candidates) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < candidates.length; i++) {
            min = Math.min(min, candidates[i]);
            max = Math.max(max, candidates[i]);
        }

        while((min & min - 1) > 0) {
            min &= min - 1;

## gist:72d9c1ebcb54818da2a465cf5247e50d
class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] ref = new int[m][n];

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '(') {
                    ref[i][j] = 1;

## shortest_path_visiting_all_nodes
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<>();

## gist:8c224d93b7f5d48cb51d0cdfa349f01f
// (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

## gist:c40f3e6aeb9dedde60f6aa54f010932d
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++) {
	<!DOCTYPE html>
	<html style="background-color:#F6F7FC;">
	<head>
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<style>
	/* width */
	::-webkit-scrollbar {
	width: 10px;
	}
	public class MinEmptySpaceInChessboard {

	/**
	* From Google:
	* Given n * n chessboard and pos array means position (i, j) has chess.
	* Calculate min distance from each chess to the empty space.
	* ex: n = 3, pos = {{0, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}, {2, 0}}
	* ans: [1, 2, 2, 1, 1, 1]
	*
	* follow up: if n = ∞ , pos has just few chess. How to improve?
	class Solution {
	public boolean canPartitionKSubsets(int[] nums, int k) {
	int sum = 0;
	int max = 0;
	for(int e: nums) {
	sum += e;
	max = Math.max(max, e);
	}

	if(sum % k > 0 \|\| max > (sum / k)) return false;
	//dijkstra TLE
	public int minimumObstacles(int[][] grid) {
	//dijkstra

	int[][] ref = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};

	int[][] minDistance = new int[grid.length][grid[0].length];

	for(int[] e: minDistance) {
	Arrays.fill(e, Integer.MAX_VALUE);
	//Total time complexity O(n), space complexity is O(k)
	public class findMoreThanKthLargest {
	public static void main(String[] args) {
	int[][] example = new int[][]{{1426828011, 9},
	{1426828028, 350},
	{1426828037, 25},
	{1426828056, 231},
	{1426828058, 109},
	{1426828066, 111}};
	public int largestCombination(int[] candidates) {
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	for(int i = 0; i < candidates.length; i++) {
	min = Math.min(min, candidates[i]);
	max = Math.max(max, candidates[i]);
	}

	while((min & min - 1) > 0) {
	min &= min - 1;
	class Solution {
	public boolean hasValidPath(char[][] grid) {
	int m = grid.length;
	int n = grid[0].length;
	int[][] ref = new int[m][n];

	for(int i = 0; i < m; i++) {
	for(int j = 0; j < n; j++) {
	if(grid[i][j] == '(') {
	ref[i][j] = 1;
	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<>();
	// (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
	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++) {