chrisynchen’s gists

chrisynchen / gist:72faf4c3f8bfb4e11339a8bf8976b1ec

Created December 1, 2023 12:40

	<!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;
	}

chrisynchen / MinEmptySpaceInChessboard

Last active August 11, 2022 10:14

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?

chrisynchen / gist:6859096634cba1ec894fdf2000efd9ef

Last active June 12, 2022 12:05

canPartitionKSubsets

	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;

chrisynchen / gist:68591760c95ca595560ba2b0641f59c8

Created May 29, 2022 16:02

2290. Minimum Obstacle Removal to Reach Corner

	//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);

chrisynchen / gist:f9831e3169f4fb80ddcfdf986e90ad17

Created May 20, 2022 13:05

findMoreThanKthLargest

	//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}};

chrisynchen / gist:8b6816cee07c8e6d4a9cff33e8f37b9b

Last active May 15, 2022 03:38

6065. Largest Combination With Bitwise AND Greater Than Zero

	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;

chrisynchen / gist:72d9c1ebcb54818da2a465cf5247e50d

Created May 8, 2022 05:04

2267. Check if There Is a Valid Parentheses String Path

	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;

chrisynchen / shortest_path_visiting_all_nodes

Created February 27, 2022 03:56

847. 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<>();

chrisynchen / gist:8c224d93b7f5d48cb51d0cdfa349f01f

Created February 23, 2022 04:17

1044. Longest Duplicate Substring

	// (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 / gist:c40f3e6aeb9dedde60f6aa54f010932d

Last active February 14, 2022 02:33

2104. Sum of Subarray Ranges

	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++) {

Chris Chen chrisynchen