humpydonkey

class AutocompleteSystem {
    private static final int MAX_RESULT = 3;

    private final TrieNode root;
    private final StringBuilder currInput;
    private TrieNode prevNode;

    // Trie + Min heap
    // Time: O(N), N = number of sentences
    public AutocompleteSystem(String[] sentences, int[] times) {

humpydonkey

class Solution {
    private static final int SIZE = 26;
    private static final int[][] DIRECTIONS = new int[][] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    private static final char VISITED_CHAR = '*';
    
    
    // Time: O(mn*3^k)
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        List<String> result = new ArrayList<>();

humpydonkey

class WordDictionary {
    
    static final int ALPHABET_SIZE = 26;
      
    public static class TrieNode {
        char val;
        int count;
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
        
        TrieNode(char val) {

humpydonkey

class Solution {
    // Typical union find problem
    // Time: O(n *26), where n is len(A)
    // Space: O(26)
    public String smallestEquivalentString(String A, String B, String S) {
        UnionFind uf = new UnionFind();
        for (int i = 0; i < A.length(); i++) {
            uf.union(A.charAt(i), B.charAt(i));
        }
        StringBuilder res = new StringBuilder();

humpydonkey

class Solution {
    // A typical union-find problem
    // Time: O(n^2 logn)
    // Space: O(n)
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {

humpydonkey

class Solution {
    // A typical union-find problem
    // Time: O(nK), where K = tree height
    // Space: O(n)
    public int earliestAcq(int[][] logs, int N) {
        Arrays.sort(logs, (l, r) -> l[0] - r[0]);
        UnionFind uf = new UnionFind(N);
        for (int i = 0; i < logs.length; i++) {
            uf.union(logs[i][1], logs[i][2]);
            if (uf.componentCnt == 1) {

humpydonkey

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = []
        len_a = len(a)
        len_b = len(b)
        i = 0
        carry = 0
        while i < len_a or i < len_b:
            sum = carry
            if i < len_a:

humpydonkey

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = []
        len1, len2 = len(num1), len(num2)
        carry = 0
        i = 0
        while i < len1 or i < len2:
            sum = carry
            if i < len1:
                sum += int(num1[len1-1-i])

humpydonkey

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        """
        Idea: a variant of 3-sum where two pointers need to be in the same side
        Time: O(n^2)
        Space: O(1)
        Requirement of a valid triangle: the smaller two numbers must greater than the biggest number in the triplet
        """
        nums.sort()
        n = len(nums)

humpydonkey

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        res = -1
        l, r = 0, len(nums) - 1
        while l < r:
            curr_sum = nums[l] + nums[r]
            if curr_sum >= k:
                r -= 1
            else: