adaxjin

class Solution {
    int MAX_EDGE_VAL = 1000;
    public int[] findRedundantConnection(int[][] edges) {
        //  find the first edge occurring in the graph that is already connected
        DSU dsu = new DSU(MAX_EDGE_VAL + 1);
        for (int[] edge: edges){
            if (!dsu.union(edge[0], edge[1])){
                return edge;
            }
        }

adaxjin

class Solution {
    class node{
        int dist;
        int worker;
        int bike;
        public node(int dist, int worker, int bike){
            this.dist = dist;
            this.worker = worker;
            this.bike = bike;
        }

adaxjin

class Solution {
    /*
    sliding window to find the minimum sum in the int array
    window size: cardPoints.length - k
    int[i] mem: sum starting from i to cardPoints.length - k + i 
    */
    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;
        int sum = 0;
        int min = 0;

adaxjin

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {

adaxjin

// @Graph @TopoSort

class Solution {
    private final int N = 26; // idx for lower case letters; i + 'a'
    public String alienOrder(String[] words) {
        // c.c.
        
        boolean[][] adj = new boolean[N][N];
        int[] visited = new int[N];
        // visited: -1: not even existed

adaxjin

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    
    private List<String> helper(int n, int m){
        if (n == 0) return new ArrayList<String>(Arrays.asList(""));
        if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        
        List<String> list = helper(n - 2, m);

adaxjin

class Solution {
    // 0-0, 1-1, 2-2, 5-5, 6-9, 8-8
    public boolean isStrobogrammatic(String num) {
        Map<Character, Character> map = new HashMap<>();
        map.put('0', '0');
        map.put('1', '1');
        // map.put('2', '2');
        // map.put('5', '5');
        map.put('6', '9');
        map.put('8', '8');

adaxjin

// @String @HashMap

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        //Create a hashmap. key is a number (the offset compared to its first char), 
        //value is a list of strings which have the same offset.
        //For each string, convert it to char array 
        //Then subtract its first character for every character
        //eg. "abc" -> "0,1,2,"        "am"->"0,12,"
        

adaxjin

//@Recursion @DFS @Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }

adaxjin

// @Trie @Prefix Tree @DFS

/*
Need: add more or search more
1. More add: save '.' as it is. When query, traverse each. Add O(1), search O(n). Good: save space. Bad: search
2. More search: for each word, have a hashset for all possible '.'. Add O(2^k), search O(1). Good: search. Bad: add, more space
3. Balanced: trie - to reduce space waste with prefix search. Add O(k), search O(n)

*/