LeetCode Summary

Template:

Union-Find

---

721. Accounts Merge

Use three maps: <email, name>, <email, parent email> for “find”, <parent email, child emails in sorted order> for “union”.
First for each account, put <email, username> and set the parent email as itself.
Then for each account, find the parent email of the first email, then set the parent of the rest emails to be this email
Then for each account, find the parent email of the first email, then put the parent email as the key, and all emails (including parent) as the values in the tree set
For each key in the union map, transform the tree set to list, and add the username to the first position, and add to the result list

Run time: $O(n)$, space: $O(n)$

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, String> owner = new HashMap<>(); // email, name
    Map<String, String> parents = new HashMap<>(); // email, parent
    Map<String, TreeSet<String>> unions = new HashMap<>();
    for(List<String> acc: accounts){
        for(int i = 1; i < acc.size(); i++){ // initialize 
            owner.put(acc.get(i), acc.get(0));
            parents.put(acc.get(i), acc.get(i)); // set parent to be itself
        }
    }
    
    for(List<String> acc: accounts){
        String p = find(acc.get(1), parents); // find parent
        for(int i = 2; i < acc.size(); i++){
            parents.put(find(acc.get(i), parents), p);
        }
    }
    
    for(List<String> acc : accounts) {
        String p = find(acc.get(1), parents);
        if (!unions.containsKey(p)) unions.put(p, new TreeSet<>());
        for (int i = 1; i < acc.size(); i++)
            unions.get(p).add(acc.get(i)); // add child
    }
    
    List<List<String>> res = new ArrayList<>();
    for (String p : unions.keySet()) {
        List<String> emails = new ArrayList(unions.get(p)); // get all children
        emails.add(0, owner.get(p)); // add name
        res.add(emails);
    }
    return res;
}

private String find(String s, Map<String, String> p) {
    if(p.get(s) == s) return s;
    return find(p.get(s), p);
}

BFS

public List<List<String>> accountsMerge2(List<List<String>> accounts) {
    Map<String, Set<String>> graph = new HashMap<>();
    Map<String, String> emailToName = new HashMap<>();

    // step 1: build graph that connects all emails have relationships
    for (List<String> account : accounts) {
        String name = account.get(0);
        for (int i = 1; i < account.size(); i++) {
            graph.putIfAbsent(account.get(i), new HashSet<>());
            emailToName.put(account.get(i), name);
            if (i != 1) {
                graph.get(account.get(i)).add(account.get(i - 1));
                graph.get(account.get(i - 1)).add(account.get(i));
            }
        }
    }

    // step 2: BFS traversal to traverse all nodes in every single component and generate each result list individually
    List<List<String>> result = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    for (String email : graph.keySet()) {
        if (!visited.contains(email)) {
            visited.add(email);
            List<String> newList = bfs(graph, visited, email);
            Collections.sort(newList);
            newList.add(0, emailToName.get(newList.get(0)));
            result.add(newList);
        }
    }
    return result;
}

public List<String> bfs(Map<String, Set<String>> graph, Set<String> visited, String startPoint) {
    List<String> newList = new ArrayList<>();
    Queue<String> queue = new LinkedList<>();
    queue.offer(startPoint);

    while(!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String curEmail = queue.poll();
            newList.add(curEmail);
            Set<String> neighbors = graph.get(curEmail);
            for (String neighbor : neighbors) {
                // WARING: DO NOT FORGET to check whether current email has been visited before
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
    return newList;
}

DFS

public List<List<String>> accountsMerge3(List<List<String>> accounts) {
    Map<String, Set<String>> graph = new HashMap<>();
    Map<String, String> emailToName = new HashMap<>();

    // step 1: build graph that connects all emails have relationships
    for (List<String> account : accounts) {
        String name = account.get(0);
        for (int i = 1; i < account.size(); i++) {
            graph.putIfAbsent(account.get(i), new HashSet<>());
            emailToName.put(account.get(i), name);
            if (i != 1) {
                graph.get(account.get(i)).add(account.get(i - 1));
                graph.get(account.get(i - 1)).add(account.get(i));
            }
        }
    }

    // step 2: DFS traversal to traverse all nodes in every single component and generate each result list individually
    List<List<String>> result = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    for (String email : graph.keySet()) {
        if (!visited.contains(email)) {
            visited.add(email);
            List<String> newList = new ArrayList<>();
            dfs(newList, graph, visited, email);
            Collections.sort(newList);
            newList.add(0, emailToName.get(newList.get(0)));
            result.add(newList);
        }
    }
    return result;
}

public void dfs(List<String> result, Map<String, Set<String>> graph, Set<String> visited, String curPoint) {
    result.add(curPoint);
    Set<String> neighbors = graph.get(curPoint);
    for (String neighbor : neighbors) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            dfs(result, graph, visited, neighbor);
        }
    }
}

RestrictedPaths (G)

Relevant post: link
A graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted vertices given in K. If it creates a path, we have to discard the edge.

1. First build the graph ( like 2d array) of n nodes using edge list

2. Then pick a pair from restricted nodes and recursively check does current node pass through any other node which is restricted, if so, simply remove that edge(s).
   Complexity = there can be at most n^2 edges = M size O(m) , You need to pick a pair from k list O(k), and check all possible connections from source to destination of picked pair O(m)
   $O(nkm^2)$

2.1 build hash to set of given k list O(k)
2.2 Rater bulding graph, while building it check the restrictions recursively using 2d matrix,
Complexity = you need to traverse whole matrix to check restrictions O(n^2)
For each pair from edge list O(m) , keeping hash to set of nodes from k list O(1)
O(mn^2)

3. Efficient
   Use union find algo, assuming path compression is used.
   3.1 union edges from m list one by one if they are not connected, before connecting them see O(m)

a) the parent (s) of pair source does not lies in k list O(logn)
B) child of pair of destinations node not lies in k list O(logn)
If either of its true, then discard

Complexity = O(logn + logn) * O(m)
$O(mk\log n)$

Other option still using disjoint set is for each edge, before adding it, check the sets for each vertex in the edge (say sets x and y) and for each edge in the K list check also the sets of its vertices (say sets w and z), in case (x == z && y == w) || (x == w && y == z) discard the edge.

Complexity is O(mk logn)

public class RestrictedPaths {

    public List<UndirectedGraph.Edge> create(List<UndirectedGraph.Edge> edges, List<UndirectedGraph.Edge> restricted, int n) {
        DisjointSet ds = new DisjointSet(n);
        List<UndirectedGraph.Edge> result = new ArrayList<>();

        for (UndirectedGraph.Edge edge: edges) {

            int x = ds.find(edge.getSrc());
            int y = ds.find(edge.getDest());

            boolean validEdge = true;
            for (UndirectedGraph.Edge r: restricted) {
                int z = ds.find(r.getSrc());
                int w = ds.find(r.getDest());

                if ((x == z && y == w) || (x == w && y == z)) {
                    validEdge = false;
                    break;
                }
            }
            if (validEdge) {
                result.add(edge);
                ds.union(x, y);
            }
        }
        return result;

    }
}

Peers and Managers (G)

A company has a bunch of employees; each employee has a single direct manager. There is a stream of actions:
set_manager(A, B) -> Set B’s direct manager to A
set_peer(A, B) -> set A and B’s direct manager to the same
query_manager(A,B) -> returns true if A is on the management chain of B, false otherwise.

Relevant posts: 2015, 2018
Union Find, HashMap checking cycle, or DFS

public class QueryMangerImpl implements QueryManger{
    Map<Integer, Integer> employmentMap;
    public QueryMangerImpl () {}

    @Override
    public void setManger(int manager, int employee) throws CyclicRelationFoundException {
        if (queryManager(employee, manager)) {
            throw new CyclicRelationFoundException(String.format("There is management relation from %s to %s",
                    manager, employee));
        }
        employmentMap.put(employee, manager);
    }

    @Override
    public void setPeer(int managerFrom, int employee) throws EmployeeNotFoundException, CyclicRelationFoundException {
        if (!employmentMap.containsKey(managerFrom)) {
            throw new EmployeeNotFoundException(String.format("Employee %s is not found"));
        }
        int newManager = employmentMap.get(managerFrom);
        if (queryManager(employee, newManager)) {
            throw new CyclicRelationFoundException(String.format("There is management relation from %s to %s", newManager, employee));
        }
        employmentMap.put(employee, newManager);
    }

    @Override
    public boolean queryManager(int manager, int employee) {
        if (manager == employee) {
            return false;
        }
        while (employmentMap.containsKey(employee)) {
            employee = employmentMap.get(employee);
            if (employee == manager) {
                return true;
            }
        }
        return false;
    }
}

public interface QueryManger {
    public void setManger(int manager, int employee) throws CyclicRelationFoundException;
    public void setPeer(int managerFrom, int target) throws CyclicRelationFoundException, EmployeeNotFoundException;
    public boolean queryManager(int manager, int employee);
}

public class CyclicRelationFoundException extends Exception {
    public CyclicRelationFoundException(String message) {
        super(message);
    }
}

public class EmployeeNotFoundException extends Exception {
    public EmployeeNotFoundException(String message) {
        super(message);
    }
}

Union set/find?

//assume there are N employees with id 0 to N-1
class peer_manager{
	int[] manager;
	int[] ids;
	int[] sz;   
	public peer_manager(int N){
		manager = new int[N]; 
		Arrays.fill(manager, -1); 
		
		ids = new int[N];
		for(int i = 0; i < N; i++) ids[i] = i;
		
		sz = new int[N]; 
		Arrays.fill(sz, 1); 
	}
   
    //indicate p and q have the same direct manager
    void set_peer(int p, int q){
        int pr = root(p);
        int qr = root(q);
        int mgr = max(manager[pr], manager[qr]);
        
        if(sz[pr] > sz[qr]){
            ids[qr] = pr;
            sz[pr] += sz[qr];
            manager[pr] = mgr;
        } else {
            ids[pr] = qr;
            sz[qr] += sz[pr];
            manager[qr] = mgr;
        }
    }
   
    //indicate p is the direct manager of q
    void set_manager(int p, int q){
        int qr = root(q);
        manager[qr] = p;
    }
   
    //check if p is in the management chain of q
    bool query_manager(int p, int q){
        while(true){
            int qr = root(q);
            
            if(manager[qr] == -1) return false;
            
            if(manager[qr] == p) return true;
            
            //follow managerment chain
            q = manager[qr];
        }
        return false;
    }

    private int root(int i){
        while(i != ids[i]) i = ids[i];
        return i;
    }
}

1101. The Earliest Moment When Everyone Become Friends

First sort the logs by chronological (increasing) order.
Create a UnionFind class and initialize an array of length N, the number of people, set each parent to be itself.
For each log, call union method in the UnionFind class, first find the parents of each person.
If they are not the same, update the date. Also set the parent of person x to be person y.
In the find method, recursively find the top parent. That is, if x does not equal to the parent of x, then call find(parent[x]) to find the top parent and assign to parent[x].
The check method will check the top parent for each person is the same or not.

Run time: $O(m\log^* n)$, space: $O(n)$, where $m$ is number of logs, $n$ is number of people

private class Myc implements Comparator<int[]>{
    @Override
    public int compare(int[] a1, int[] a2){
        return a1[0]-a2[0];
    }
}
public int earliestAcq(int[][] logs, int N) {
    Myc myc = new Myc();
    Arrays.sort(logs,myc);
    Unionfind unionf = new Unionfind(N);
    for(int[] log : logs){
        unionf.Union(log[1],log[2],log[0]);
    }
    if(unionf.check()) return unionf.ans;
    return -1;
}

private class Unionfind{
    int[] parent;
    int ans = -1;
    public Unionfind(int N){
        parent= new int[N];
        for(int i =0; i< N; i++){
            parent[i] = i;
        }
    }
    public int Find(int x){
        if(x != parent[x]){
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    public void Union(int x ,int y,int data){
        int px = Find(x);
        int py = Find(y);
        //System.out.println(px+" "+ py);
        if(px!=py) ans = data;
        parent[px] = py;
    }
    public boolean check(){
        int t = Find(0);          
        for(int a = 0; a<parent.length; a++){
            if(Find(a)!=t)return false;
        }
        return true;
    }
}

Trees and Nodes

---

173. Binary Search Tree Iterator (M)

Use a stack and push the root and left nodes to it
When we want the next smallest number, if the top node has a right node, use the same way to push the right node to the stack, and return the current value

public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode tmpNode = stack.pop();
        pushAll(tmpNode.right);
        return tmpNode.val;
    }
    
    private void pushAll(TreeNode node) {
        while (node != null){
            stack.push(node);
            node = node.left;
        }
    }
}

Use in-order traversal to transform tree to list and update the pointer

class BSTIterator {
    List<Integer> list;
    int i = 0;
    public BSTIterator(TreeNode root) {
        list = new ArrayList<>();
        helper(list, root);
    }
    
    private void helper(List<Integer> list, TreeNode root){
        if(root == null) return;
        helper(list, root.left);
        list.add(root.val);
        helper(list, root.right);
    }
    
    /** @return the next smallest number */
    public int next() {
        return list.get(i++);
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(i >= list.size()) return false;
        return true;
    }
}

655. Print Binary Tree (M)

public List<List<String>> printTree(TreeNode root) {
    List<List<String>> res = new ArrayList<>();
    if (root == null) return res;
    
    int rows = getHeight(root);
    int cols = (int) Math.pow(2, rows) - 1;
    for (int i = 0; i < rows; i++) {
        List<String> row = new ArrayList<>();
        for (int j = 0; j < cols; j++) {
            row.add("");
        }
        res.add(row);
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    Queue<int[]> indexQ = new LinkedList<>();
    queue.offer(root);
    indexQ.offer(new int[] { 0, cols - 1 });
    int row = -1;
    while (!queue.isEmpty()) {
        row++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            int[] indices = indexQ.poll();
            
            if (cur == null) continue;
            
            int left = indices[0];
            int right = indices[1];
            int mid = left + (right - left) / 2;
            res.get(row).set(mid, String.valueOf(cur.val));
            
            queue.offer(cur.left);
            queue.offer(cur.right);
            indexQ.offer(new int[] { left, mid - 1 });
            indexQ.offer(new int[] { mid + 1, right });
        }
    }
    return res;
}

public int getHeight(TreeNode root) {
    if(root == null)  return 0;
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}

Recursive

public List<List<String>> printTree(TreeNode root) {
    List<List<String>> result = new ArrayList<>();
    int row = getHeight(root);
    int col = (int) Math.pow(2, row) - 1;
    List<String> ans = new ArrayList<>();
    for(int i = 0; i < col; i++)  ans.add("");
    for(int i = 0; i < row; i++)  result.add(new ArrayList<>(ans));
    populateResult(root, result, 0, row, 0, col - 1);
    return result;
}

public void populateResult(TreeNode root, List<List<String>> result, int curRow, int totalRow, int i, int j) {
    if(root == null || curRow == totalRow)  return;
    result.get(curRow).set((i + j) / 2, String.valueOf(root.val));
    populateResult(root.left, result, curRow + 1, totalRow, i, ((i + j) / 2) - 1);
    populateResult(root.right, result, curRow + 1, totalRow, ((i + j) / 2) + 1, j);
}

public int getHeight(TreeNode root) {
    if(root == null)  return 0;
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}

114. Flatten Binary Tree to Linked List (M)

Iterative: Use a pointer for the current node
If left child exists, use another pointer to find the rightest leaf node
Assign the right child of current node to be the right child of the leaf node
Then move the left node to be the right child of the current node
Set left child to be null
Move on to the next right child

Run time: $O(n)$, space: $O(1)$

public void flatten(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left != null) {
            TreeNode last = cur.left;
            while (last.right != null) last = last.right; // find the rightest leaf
            last.right = cur.right; // right child of the rightest leaf
            cur.right = cur.left; // right child of the root
            cur.left = null;
        }
        cur = cur.right;
    }
}

Recursive: post-order traversal, use a pointer node to keep track of the node to be attached to the next node, then update this pointer

private TreeNode prev = null;
public void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}

1261. Find Elements in a Contaminated Binary Tree

Use DFS to explore every node, and assign value to left child and right child, then put value into a HashSet.

class FindElements {
    Set<Integer> set = new HashSet<>();
    public FindElements(TreeNode root) {
        dfs(root, 0);
    }
    
    private void dfs(TreeNode n, int v) {
        if (n == null) return;
        set.add(v);
        n.val = v;
        dfs(n.left, 2 * v + 1);
        dfs(n.right, 2 * v + 2);
    }
    
    public boolean find(int target) {
        return set.contains(target);
    }
}

116. Populating Next Right Pointers in Each Node

From observation, the next node’s left child is the current node’s right child’s next node, so we need a pointer to the root node. In the while loop, if current node and the left child are not null, set the left child’s next node to be the right child. If the next node of the current node is not null, then set as discussed before.

public Node connect(Node root) {
    if(root == null) return null;
    Node cur = root;
    while(cur != null && cur.left != null){
        cur.left.next = cur.right;
        if(cur.next != null) cur.right.next = cur.next.left;
        cur = cur.next;
    }
    connect(root.left);
    return root;
}

95. Unique Binary Search Trees II (M)

Find out that the number of unique BST with same number of nodes does not change, so we can use DP to find the unique BST with 1 to n node.

public List<TreeNode> generateTrees(int n) {
    ArrayList<TreeNode>[] dp = new ArrayList[n + 1];
    dp[0] = new ArrayList<TreeNode>();
    if (n == 0) {
        return dp[0];
    }
    dp[0].add(null);
    for (int len = 1; len <= n; len++) { //长度为 1 到 n
        dp[len] = new ArrayList<TreeNode>();
        for (int root = 1; root <= len; root++) { //将不同的数字作为根节点，只需要考虑到 len
            int left = root - 1;  //左子树的长度
            int right = len - root; //右子树的长度
            for (TreeNode leftTree : dp[left]) {
                for (TreeNode rightTree : dp[right]) {
                    TreeNode treeRoot = new TreeNode(root);
                    treeRoot.left = leftTree;
                    treeRoot.right = clone(rightTree, root); //克隆右子树并且加上偏差
                    dp[len].add(treeRoot);
                }
            }
        }
    }
    return dp[n];
}

private TreeNode clone(TreeNode n, int offset) {
    if (n == null) return null;
    TreeNode node = new TreeNode(n.val + offset);
    node.left = clone(n.left, offset);
    node.right = clone(n.right, offset);
    return node;
}

Sum of all leaf nodes of binary tree (G)

Relevant link: GFG
The idea is to traverse the tree in any fashion and check if the node is the leaf node or not. If the node is the leaf node, add node data to sum variable.

Run time: $O(n)$, space: $O(n)$

static int leafSum(Node root){ 
    if (root == null) return 0; 
   
    if (root.left == null && root.right == null) return root.val; 
   
    return leafSum(root.left) + leafSum(root.right); 
} 

951. Flip Equivalent Binary Trees (G)

Recursion way
If any of the two nodes is null, check if they are the same
If none of them is null. check if the values are the same
Return if fleft=left and right=right, or left=right and right=left

Run time: $O(m+n)$, space: $O(m+n)$

public boolean flipEquiv(TreeNode r1, TreeNode r2) {
    if (r1 == null || r2 == null) return r1 == r2;
    if(r1.val != r2.val) return false;
    return (flipEquiv(r1.left, r2.left) && flipEquiv(r1.right, r2.right)) || 
           (flipEquiv(r1.left, r2.right) && flipEquiv(r1.right, r2.left));
}

Iterative (BFS): Helper function to check if two nodes are same
Store nodes in a queue, each time poll two nodes
If they are both null, continue; if they are not the same, return false
Check if left1=left2 and right1=right2, put left1, left2, right1, right2 into the queue
Check if left1=right2 and right1=left2, put left1, right2, right1, left2 into the queue
Otherwise return false

public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    Queue<TreeNode> queue = new LinkedList<>();

    queue.offer(root1);
    queue.offer(root2);
    while (!queue.isEmpty()) {
        TreeNode curr1 = queue.poll();
        TreeNode curr2 = queue.poll();

        if (curr1 == null && curr2 == null) continue;
        if (!isEquals(curr1, curr2)) return false;

        if (isEquals(curr1.left, curr2.left) && isEquals(curr1.right, curr2.right)) {
            queue.offer(curr1.left);
            queue.offer(curr2.left);
            queue.offer(curr1.right);
            queue.offer(curr2.right);
        } else if (isEquals(curr1.left, curr2.right) && isEquals(curr1.right, curr2.left)) {
            queue.offer(curr1.left);
            queue.offer(curr2.right);
            queue.offer(curr1.right);
            queue.offer(curr2.left);
        } else {
            return false;
        }
    }
    return true;
}

private boolean isEquals(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null) return root1 == root2;
    else if (root1.val == root2.val) return true;
    return false;
}

2. Add Two Numbers

Create a pointer node and a node for result
While either of the nodes is not null or the temp sum is greater than 0
Collect the values, if greater than 10, subtract 10 and increment the carry-in
Set the next Node value, and move the pointer
Set the sum to be carry-in, and set the carry-in to be zero

Run time: $O(m+n)$, space: $O(m+n)$

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode res = new ListNode(-1);
    ListNode cur = res;
    int sum = 0;
    int carry = 0;
    while(l1 != null || l2 != null || sum > 0) {
        if(l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        
        if(l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        
        if(sum >= 10) {
            sum %= 10;
            carry += 1;
        }
        
        cur.next = new ListNode(sum);
        cur = cur.next;
        sum = carry;
        carry = 0;
    }
    return res.next;
}

Recursion way

   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	if (l1 == null && l2 == null) return null;
	if (l1 == null || l2 == null) {
		return l1 == null ? l2 : l1;
	}
	int val1 = l1.val;
	int val2 = l2.val;

	ListNode ln = null;

	if (val1 + val2 < 10) {
		ln = new ListNode(val1 + val2);
		ln.next = addTwoNumbers(l1.next, l2.next);
	} else {
		ln = new ListNode(val1 + val2 - 10);
		ListNode overflow = new ListNode(1);
		overflow.next = null;
		ListNode temp = addTwoNumbers(overflow, l1.next);
		ln.next = addTwoNumbers(temp, l2.next);
	}
	return ln;
}

133. Clone Graph

Use HashMap to put <node.val, Node>, use a helper method to go through all the neighbors
If the Node has been visited(in the map), then directly return it
Otherwise, create a new Node and walk through its neighbors

Run time: $O(n)$, space: $O(n)$

public Node cloneGraph(Node node) {
    Map<Integer, Node> map = new HashMap<>();
    return helper(map, node);
}

public Node helper(Map<Integer, Node> map, Node n){
    if(n == null) return null;
    if(map.containsKey(n.val)) return map.get(n.val);
    Node tempNode = new Node(n.val, new ArrayList<Node>());
    map.put(n.val, tempNode);
    for(Node neighbor: n.neighbors) tempNode.neighbors.add(helper(map, neighbor));
    return tempNode;
}

21. Merge Two Sorted Lists

Recursion: look organized!

public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
}

Straightforward way: use a while loop and copy the values one by one

Run time: $O(n)$, space: $O(n)$

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l2 == null) return l1;
    if(l1 == null) return l2;
    ListNode head = new ListNode(-1);
    ListNode ptr = head;
    while(l1 != null && l2 != null){
        if(l1.val < l2.val){
            head.next = new ListNode(l1.val);
            l1 = l1.next;
        }
        else{
            head.next = new ListNode(l2.val);
            l2 = l2.next;
        }
        head = head.next;
    }
    if(l1 != null) head.next = l1;
    if(l2 != null) head.next = l2;
    return ptr.next;
}

23. Merge k Sorted Lists

Put all nodes in a priority queue in increasing order.
Put out all nodes in the list into PQ.
Create a head node with value 0, and a pointer node pointing to head.
Loop through this PQ, and set the next node of the pointer to the node that was just polled out.
Update the polled node to the next one, and put it back to the PQ if it is not null.
Return the next node of the head node.

Run time: $O(n\log k)$, space: $O(n\log k)$, where $k$ is the max length of nodes

public ListNode mergeKLists(List<ListNode> lists) {
    Queue<ListNode> heap = new PriorityQueue(new Comparator<ListNode>(){
        @Override public int compare(ListNode l1, ListNode l2) { 
            return l1.val - l2.val; 
        }
    });
    ListNode head = new ListNode(0), tail = head;
    for (ListNode node : lists) if (node != null) heap.offer(node);
    while (!heap.isEmpty()) {
        tail.next = heap.poll();
        tail = tail.next;
        if (tail.next != null) heap.offer(tail.next);
    }
    return head.next;
}

146. LRU Cache (M)

Use double linked list (Node) and HashMap
Node class: key and value, prev and next nodes
Map: <Integer, Node> --> key, node

Run time: $O(1)$ for each method, space: $O(n)$

class LRUCache {
    final Node head = new Node(0,0);
    final Node tail = new Node(0,0);
    final Map<Integer, Node> map;
    final int capacity;
    
    public LRUCache(int capacity){
        this.capacity = capacity;
        map = new HashMap(capacity);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
      int res = -1;
      if(map.containsKey(key)){
        Node n = map.get(key);
        remove(n);
        insertToHead(n);
        res = n.value;
      }
      return res;   
    }
    
    public void put(int key, int value) {
      if(map.containsKey(key)){
        Node n = map.get(key);
        remove(n);
        n.value = value;
        insertToHead(n);
      } else {
        
        if(map.size() == capacity){
           map.remove(tail.prev.key); 
           remove(tail.prev);
        } 
        
        Node n = new Node(key, value);
        insertToHead(n);
        map.put(key, n);
      }  
    }
    
    class Node{
        int key, value;
        Node prev, next;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
      
    private void remove(Node n){ // skip this node
      n.prev.next = n.next;
      n.next.prev = n.prev;
    }
    
    private void insertToHead(Node n){
      Node headNext = head.next;
      head.next = n;
      headNext.prev = n;
      n.prev = head;
      n.next = headNext;
    }
}

Alternative way

class LRUCache {
    class DListNode {
        int key;
        int val;
        DListNode prev;
        DListNode next;

        public DListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    Map<Integer, DListNode> map;
    DListNode oldestNode;
    DListNode latestNode;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
    }

    public int get(int key) {
        DListNode node = map.get(key);
        if (node == null) return -1;
        else if (node.next == null) return node.val;
        else {
            if (node.prev == null) {
                oldestNode = node.next;
                oldestNode.prev = null;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            node.next = null;
            node.prev = latestNode;
            latestNode.next = node;
            latestNode = node;
            return node.val;
        }
    }

    public void put(int key, int value) {
        int val = get(key);
        if (val == -1) {
            if (map.size() == capacity) {
                map.remove(oldestNode.key);
                if (oldestNode.next != null)
                    oldestNode.next.prev = null;
                oldestNode = oldestNode.next;
            }
            DListNode node = new DListNode(key, value);
            if (map.size() == 0) {
                oldestNode = node;
                latestNode = node;
            } else {
                latestNode.next = node;
                node.prev = latestNode;
                latestNode = node;
            }
            map.put(key, node);
        } else map.get(key).val = value;
    }
}

Straight forward way: use LinkedHashMap and override the removeEldestEntry method
"LinkedHashMap is just like HashMap with an additional feature of maintaining an order of elements inserted into it. HashMap provided the advantage of quick insertion, search and deletion but it never maintained the track and order of insertion which the LinkedHashMap provides where the elements can be accessed in their insertion order. "
“The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.”

class LRUCache {
    private Map<Integer, Integer> cache;
    private int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // create cache with initial capacity of 16 items
        // load factor of 75% and using access order (LRU style) retrieval
        this.cache = new LinkedHashMap<Integer, Integer>(16, 0.75f, true){
            //anonymous inner class to override removeEldestEntry behaivor. 
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return  cache.size() > capacity;
            }
        };
    }
    
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

138. Copy List with Random Pointer (9/19 Bloomberg, FAILED)

Use a node start from head
Use a map to store <current node, new node with same val, next.val, random.val>
Reset the node to be head
Go through each node and get the new node from the map

public Node copyRandomList(Node head) {
    if (head == null) return null;
    
    Map<Node,Node> map = new HashMap<Node,Node>();
    
    Node ans = head;
    while(ans != null){
        map.put(ans, new Node(ans.val,ans.next,ans.random));
        ans = ans.next;
    }
    
    ans = head;
    while(ans != null){
        map.get(ans).next = map.get(ans.next);
        map.get(ans).random = map.get(ans.random);
        ans = ans.next;
    }
    return map.get(head);
}

public RandomListNode copyRandomList(RandomListNode head) {
  RandomListNode iter = head, next;

  // First round: make copy of each node,
  // and link them together side-by-side in a single list.
  while (iter != null) {
    next = iter.next;

    RandomListNode copy = new RandomListNode(iter.label);
    iter.next = copy;
    copy.next = next;

    iter = next;
  }

  // Second round: assign random pointers for the copy nodes.
  iter = head;
  while (iter != null) {
    if (iter.random != null) {
      iter.next.random = iter.random.next;
    }
    iter = iter.next.next;
  }

  // Third round: restore the original list, and extract the copy list.
  iter = head;
  RandomListNode pseudoHead = new RandomListNode(0);
  RandomListNode copy, copyIter = pseudoHead;

  while (iter != null) {
    next = iter.next.next;

    // extract the copy
    copy = iter.next;
    copyIter.next = copy;
    copyIter = copy;

    // restore the original list
    iter.next = next;

    iter = next;
  }
  return pseudoHead.next;
}

Dynamic Programming (DP)

---

1278. Palindrome Partitioning III

This question essentially is a knapsack problem.
dp[i][j] means that the mininal number of change if we partition the string at j for ith time.

Map<String, Integer> map = new HashMap<>();
public int palindromePartition(String s, int k) {
    if (s.length() == k) return 0;
    int len = s.length();
    int[][] dp = new int[k][len + 1];
    for (int i = 0; i < len; ++i){
        dp[0][i + 1] = helper(s.substring(0, i + 1));
    }
    for (int i = 1; i < k; i++){
        for (int j = i; j <= len; j++){
            int cur = Integer.MAX_VALUE;
            for (int p = j; p >= i; p--){
                cur = Math.min(cur, dp[i - 1][p - 1] + helper(s.substring(p - 1,j )));
            }
            dp[i][j] = cur;
        }
    }
    return dp[k - 1][len];
}
private int helper(String str){
    if (str == null || str.length() == 0) return 0;
    if (map.containsKey(str)) return map.get(str);
    int res = 0;
    for (int i = 0; i < str.length(); ++i){
        if (str.charAt(i) != str.charAt(str.length() - i - 1)) res++;
    }
    res /= 2;
    map.put(str, res);
    return res;
}

1277. Count Square Submatrices with All Ones

dp[i][j] represents the length of the square which lower right corner is located at (i, j).
If the value of this cell is also 1, then the length of the square is the minimum of: the one above, its left, and diagonal up-left value +1. Because if one side is short or missing, it will not form a square.

Run time: $O(mn)$, space: $O(mn)$

public int countSquares(int[][] matrix) {
    int total = 0;
    int rows = matrix.length, cols = matrix[0].length;
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++){
            if(matrix[i][j] == 0) continue;
            if(i == 0 || j == 0){
                total += matrix[i][j];
                continue;
            }
            int min = Math.min(matrix[i-1][j], Math.min(matrix[i][j-1], matrix[i-1][j-1]));
            matrix[i][j] += min;
            total += matrix[i][j];
        }
    }
    return total;
}

494. Target Sum

public int findTargetSumWays(int[] nums, int S) {
    int sum = 0;
    for(int n: nums) sum += n;
    if (S < -sum || S > sum) return 0;

    int[][] dp = new int[nums.length + 1][ 2*sum + 1];
    dp[0][0+sum] = 1; // 0 + sum means 0, 0 means -sum,  check below graph
    for(int i = 1; i <= nums.length; i++){
        for(int j = 0; j < 2 * sum + 1; j++){
            if(j + nums[i-1] < 2*sum + 1) dp[i][j] += dp[i-1][j+nums[i-1]];
            if(j - nums[i-1] >= 0) dp[i][j] += dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.length][sum + S];
}

1269. Number of Ways to Stay in the Same Place After Some Steps

Recursion takes forever to solve this problem, so use 1-D array of the same length as the given array length, and fill in 1 to the first two cells.
For each number of steps, initialize a new array, and use a for loop to iterate from 0 to n-1 or current remaining steps. Find the result of staying, moving left, and moving right, update the count, and assign to the temp array. At last, assign the temp array to the original array, since this would be the last state of the array. In the end, return the value in the first cell in arr.

Run time: $O(steps)$, space: $O(n)$

static int mod = (int)Math.pow(10, 9) + 7;
public int numWays(int steps, int n) {
    int[] arr = new int[n];
    if(n <= 1) return n;
    arr[0] = 1;
    arr[1] = 1;
    
    for(int j = 1; j < steps; j++){
        int[] temp = new int[n]; // configuration of the array from the previous state.
        for(int i = 0; i <= Math.min(n - 1, steps - j); i++){
            long ans = arr[i]; // stay
            if(i > 0) ans = (ans + arr[i - 1]) % mod; // right
            if(i < n - 1) ans = (ans + arr[i + 1]) % mod; // left
            temp[i] = (int) ans;
        }
        arr = temp;
    }
    return arr[0];
}

63. Unique Paths II (M)

Keep track of num ways to reach this position in row i

Run time: $O(n^2)$, space: $O(n)$

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int width = obstacleGrid[0].length;
    int[] dp = new int[width];
    dp[0] = 1;
    for (int[] row : obstacleGrid) {
        for (int j = 0; j < width; j++) {
            if (row[j] == 1) dp[j] = 0;
            else if (j > 0) dp[j] += dp[j - 1];
        }
    }
    return dp[width - 1];
}

55. Jump Game (M)

Start from last index, then a loop back to the start
If the sum of current index and current step is not less than the last step, update the last step to be the current index
At last check if the last index is smaller than or equal to 0

Run time: $O(n)$, space: $O(1)$

public boolean canJump(int nums[]) {
    int last = nums.length-1;
    for(int i = last-1; i >= 0; i--){
        if(i + nums[i] >= last) last = i;
    }
    return last <= 0;
}

Work forward (Greedy?): Update the maximum steps each time, check if the current index is greater than the max step

public boolean canJump(int[] nums) {
    int max = 0;
    for(int i = 0; i < nums.length; i++){
        if(i > max) return false;
        max = Math.max(max, nums[i]+i);
    }
    return true;
}

53. Maximum Subarray (M)

Keep track of the max and the max sum ended at current index, update the entry if the previous element is positive, otherwise just take the current element

Run time: $O(n)$, space: $O(n)$

public int maxSubArray(int[] A) {
    int n = A.length;
    int[] dp = new int[n]; //dp[i]: the maximum subarray ending with A[i]
    dp[0] = A[0];
    int max = dp[0];
    
    for(int i = 1; i < n; i++){
        dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
        max = Math.max(max, dp[i]);
    }
    return max;
}

Another way: update maxSoFar and maxEndingHere

Run time: $O(n)$, space: $O(1)$

public static int maxSubArray(int[] A) {
    int maxSoFar = A[0], maxEndingHere = A[0];
    for (int i = 1; i < A.length; i++){
        maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);	
    }
    return maxSoFar;
}

Dijkstra’s Algorithm with Path Printing (G)

Relevant link: GFG, link

import java.util.Scanner; //Scanner Function to take in the Input Values 
  
public class Dijkstra { 
    static Scanner scan; // scan is a Scanner Object 
  
    public static void main(String[] args) { 
        int[] preD = new int[5]; 
        int min = 999, nextNode = 0; // min holds the minimum value, nextNode holds the value for the next node. 
        scan = new Scanner(System.in); 
        int[] distance = new int[5]; // the distance matrix 
        int[][] matrix = new int[5][5]; // the actual matrix 
        int[] visited = new int[5]; // the visited array 
  
        System.out.println("Enter the cost matrix"); 
  
        for (int i = 0; i < distance.length; i++) { 
            visited[i] = 0; //initialize visited array to zeros 
            preD[i] = 0; 
  
            for (int j = 0; j < distance.length; j++) { 
                matrix[i][j] = scan.nextInt(); //fill the matrix 
                if (matrix[i][j]==0) 
                    matrix[i][j] = 999; // make the zeros as 999 
            } 
        } 
  
        distance = matrix[0]; //initialize the distance array 
        visited[0] = 1; //set the source node as visited 
        distance[0] = 0; //set the distance from source to source to zero which is the starting point 
  
        for (int counter = 0; counter < 5; counter++) { 
            min = 999; 
            for (int i = 0; i < 5; i++) { 
                if (min > distance[i] && visited[i]!=1) { 
                    min = distance[i]; 
                    nextNode = i; 
                } 
            } 
  
            visited[nextNode] = 1; 
            for (int i = 0; i < 5; i++) { 
                if (visited[i]!=1) { 
                    if (min+matrix[nextNode][i] < distance[i]) { 
                        distance[i] = min+matrix[nextNode][i]; 
                        preD[i] = nextNode; 
                    } 
                } 
            } 
        } 
  
        for(int i = 0; i < 5; i++) System.out.print("|" + distance[i]); 
  
        System.out.println("|"); 
  
        int j; 
        for (int i = 0; i < 5; i++) { 
            if (i!=0) { 
                System.out.print("Path = " + i); 
                j = i; 
                while(j!= 0) { 
                    j = preD[j]; 
                    System.out.print(" <- " + j); 
                } 
            } 
            System.out.println(); 
        } 
    } 
} 

Check for possible path in 2D matrix (G)

1 = road, 0 = wall
First, change the value of the first top left element value to 2. Then get the next (current) value in the first row and compare to the previous value. Set this current value equal to the previous value only if it is reachable (not equal to 0). Similarly, do the same for column values, by comparing and setting the current with the previous column’s value if it is reachable.
Then start from the first-row & first column and take the values of previous row & the previous column. Find the max between them, and set the current index to that max. If the current index value is 0 then there’s no change.

Run time: $O(mn)$, space: $O(1)$

boolean isPath(int[][] arr, int[] start, int[] end) { 
    arr[start[0]][start[1]] = 2; 

    for (int i = 1; i < arr.length; i++) 
        if (arr[0][i] != 0) arr[0][i] = arr[0][i - 1]; 
    for (int j = 1; j < arr[0].length; j++) 
        if (arr[j][0] != 0) arr[j][0] = arr[j - 1][0]; 
  

    for (int i = 1; i < arr.length; i++) 
        for (int j = 1; j < arr[0].length; j++) 
            if (arr[i][j] != 0) arr[i][j] = Math.max(arr[i][j - 1], arr[i - 1][j]); 
  
    return (arr[end[0]][end[1]] == 1); 
} 

Rhyme Schemes (G)

Relevant posts: link1, link2
Relevant links: Bell number, Bell triangle, Binomial coefficient

This way: dp[current length][current last char][biggest char seen]

public int getPatternCount(int n) {
    int[][][] dp = new int[n + 1][26][26];
    dp[1][0][0] = 1; // 'A'
    for (int len = 1; len != n; len++) {
      for (int j = 0; j != 26; j++) {
        for (int i = 0; i <= j; i++) {
          for (int k = 0; k <= j; k++)
            dp[len + 1][k][j] += dp[len][i][j];
          if (j + 1 != 26)
            dp[len + 1][j + 1][j + 1] += dp[len][i][j];
        }
      }
    }
    int res = 0;
    for (int i = 0; i != 26; i++)
      for (int j = 0; j != 26; j++)
        res += dp[n][i][j];
    return res;
  }

Backtracking: not very efficient if only return number of ways of permutations
This solution return exact paths (original version is C++, not sure if I translated right)

List<String> findRhyme(int n){
        if(n == 0) return new ArrayList<>()
        List<String> res = new ArrayList<>();
        String path = "";
        int[] visited = new int[26];
        backtracking(path, n, res, visited);
        return res;
    }
   
    void backtracking(String path, int n, List<String> res, int[] visited){
        if(path.size() == n){
            res.add(path);
            return;
        }
        for(int i = 0; i < visited.length; i++){
            if(visited[i] != 0){
                path.add('A' + i);
                backtracking(path, n, res, visited);
                path.remove();
            }else{
                path.add('A' + i);
                visited[i] = 1;
                backtracking(path, n, res, visited);
                visited[i] = 0;
                path.remove();
                break;
            }
        }
        return;
    }

91. Decode Ways (G) (M)

Keep track of # decoding ways for substring ended at index i-1
Fill in dp[0] = 1 and if first char is not 0, then dp[1] = 1, otherwise fill in 0

Run time: $O(n)$, space: $O(n)$

public int numDecodings(String s) {
    if(s == null || s.length() == 0) return 0;

    int n = s.length();
    int[] dp = new int[n+1];
    dp[0] = 1;
    dp[1] = s.charAt(0) != '0' ? 1 : 0;
    for(int i = 2; i <= n; i++) {
        int first = Integer.valueOf(s.substring(i-1, i));
        int second = Integer.valueOf(s.substring(i-2, i));
        if(first >= 1 && first <= 9) {
           dp[i] += dp[i-1];  
        }
        if(second >= 10 && second <= 26) {
            dp[i] += dp[i-2];
        }
    }
    return dp[n];
}

1246. Palindrome Removal

Intuition: A[i] can be removed alone or it makes a pair.

Top down DP

int[][] dp;
public int minimumMoves(int[] A) {
    int n = A.length;
    dp = new int[n][n];
    return dfs(0, n - 1, A);
}
int dfs(int i, int j, int[] A) {
    if (i > j) return 0;
    if (dp[i][j] > 0) return dp[i][j];
    int res = dfs(i, j - 1, A) + 1;
    if (j > 0 && A[j] == A[j - 1])
        res = Math.min(res, dfs(i, j - 2, A) + 1);
    for (int k = i; k < j - 1; ++k)
        if (A[k] == A[j])
            res = Math.min(res, dfs(i, k - 1, A) + dfs(k + 1, j - 1, A));
    dp[i][j] = res;
    return res;
}

Bottom up DP

public int minimumMoves(int[] A) {
    int N = A.length;
    //  declare dp array and initialize it with 0s
    int[][] dp = new int[N + 1][N + 1];
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++)
            dp[i][j] = 0;
    // loop for subarray length we are considering
    for (int len = 1; len <= N; len++) {
        // loop with two variables i and j, denoting starting and ending of subarray
        for (int i = 0, j = len - 1; j < N; i++, j++) {
            // If subarray length is 1, then 1 step will be needed
            if (len == 1)
                dp[i][j] = 1;
            else {
                // delete A[i] individually and assign result for subproblem (i+1,j)
                dp[i][j] = 1 + dp[i + 1][j];
                // if current and next element are same, choose min from current and subproblem (i+2,j)
                if (A[i] == A[i + 1])
                    dp[i][j] = Math.min(1 + dp[i + 2][j], dp[i][j]);
                // loop over all right elements and suppose Kth element is same as A[i] then
                // choose minimum from current and two subarray after ignoring ith and A[K]
                for (int K = i + 2; K <= j; K++)
                    if (A[i] == A[K])
                        dp[i][j] = Math.min(dp[i + 1][K - 1] + dp[K + 1][j], dp[i][j]);
            }
        }
    }
    return dp[0][N - 1];
}

1105. Filling Bookcase Shelves

Use an array to store the min levels to put i books
For each book, first assume it is put at a new level, then loop back and see if the previous level and fit this book (both width and height), then update the levels

Run time: $O(n^2)$, space: $O(n)$

public int minHeightShelves(int[][] books, int shelf_width) {
    int[] dp = new int[books.length + 1]; // store the min levels to put i books
    dp[0] = 0;
    
    for (int i = 1; i <= books.length; i++) {
        int width = books[i-1][0], height = books[i-1][1];
        dp[i] = dp[i-1] + height; // another level
        for (int j = i - 1; j > 0 && width + books[j-1][0] <= shelf_width; j--) {
            height = Math.max(height, books[j-1][1]); // get max height on this level
            width += books[j-1][0]; // put this book
            dp[i] = Math.min(dp[i], dp[j-1] + height); // update min
        }
    }
    return dp[books.length];
}

72. Edit Distance (G)

Use a 2-D array to keep track of number of changes from char i in word1 to char j in word2

Run time: $O(mn)$, space: $O(mn)$ (m, n are the length of words)

public int minDistance(String word1, String word2) {
    if (word1.equals(word2)) return 0; // exactly same
    if (word1.length() == 0 || word2.length() == 0) // one of them is empty
        return Math.abs(word1.length() - word2.length());
    // num changes from char i in word1 to char j in word2
    int[][] dp = new int[word1.length() + 1][word2.length() + 1];
    for (int i = 0; i <= word1.length(); i++) dp[i][0] = i;
    for (int i = 0; i <= word2.length(); i++) dp[0][i] = i;

    for (int i = 1; i <= word1.length(); i++) {
        for (int j = 1; j <= word2.length(); j++) {
            // same char, just copy the count from previous character
            if (word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
            // need to do an operation, copy the minimum num changes from previous step
            else dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
        }
    }
    return dp[word1.length()][word2.length()];
}

1027. Longest Arithmetic Sequence

Use an array of HashMap to store <difference, current length>

Run time: $O(n^2)$, space: $O(n^2)$

public int longestArithSeqLength(int[] A) {
    int res = 2, n = A.length;
    HashMap<Integer, Integer>[] dp = new HashMap[n];
    for (int j = 0; j < A.length; j++) {
        dp[j] = new HashMap<>();
        for (int i = 0; i < j; i++) {
            int diff = A[j] - A[i];
            dp[j].put(diff, dp[i].getOrDefault(diff, 1) + 1);
            res = Math.max(res, dp[j].get(diff));
        }
    }
    return res;
}

739. Daily Temperatures

For each temperature, walk back to fill in the number of days

Run time: $O(n)$, space: $O(n)$

public int[] dailyTemperatures(int[] T) {
    int[] arr = new int[T.length];
    int top = -1;
    int[] ret = new int[T.length];
    for(int i = 0; i < T.length; i++) {
        while(top > -1 && T[i] > T[arr[top]]) {
            int idx = arr[top--];
            ret[idx] = i - idx;
        }
        arr[++top] = i;
    }
    return ret;
}

Descending stack

public int[] dailyTemperatures(int[] T) {
    Stack<Integer> stack = new Stack<>();
    int[] ret = new int[T.length];
    for(int i = 0; i < T.length; i++) {
        while(!stack.isEmpty() && T[i] > T[stack.peek()]) {
            int idx = stack.pop();
            ret[idx] = i - idx;
        }
        stack.push(i);
    }
    return ret;
}

322. Coin Change

Initialize an array of length “amount+1”, fill it from index 1 (one dollar) to the end
First fill in the max value, then loop through every possible coin
If the current amount is greater than the coin, update the number of coins by finding the value [i-this coin]+1

Run time: $O(n\times amount)$, space: $O(amount)$

public int coinChange(int[] coins, int amount) {
  int[] dp = new int[amount + 1];
  for (int i=1; i < dp.length; i++) {
    dp[i] = dp.length;
    for (int j=0; j < coins.length; j++) {
      if (i >= coins[j]) dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
    }
  }
  return dp[amount] == dp.length ? -1 : dp[amount];
}

Similar way

public static int coinChange(int[] coins, int amount) {
    if (coins == null || coins.length == 0 || amount <= 0) return 0;
    int[] minNumber = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        minNumber[i] = Integer.MAX_VALUE;
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i && minNumber[i - coins[j]] != Integer.MAX_VALUE)
                minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);
        }
    }
    if (minNumber[amount] == Integer.MAX_VALUE) return -1;
    else return minNumber[amount];
}

121. Best Time to Buy and Sell Stock (M)

Update the lowest buy price, and update the maximum earn (current price - buy price)

Run time: $O(n)$, space: $O(1)$

public int maxProfit(int[] prices) {
    if(prices == null || prices.length < 2) return 0;
    int buy = prices[0], earn = 0;
    for(int i = 1; i < prices.length; i++){
        buy = Math.min(buy, prices[i]);
        earn = Math.max(earn, prices[i]-buy);
    }
    return earn;
}

304. Range Sum Query 2D - Immutable

Use a matrix to calculate the sum of rectangle that the current entry is the lower right corner
In the method, use the max entry subtracts the lower left and upper right entries, and add the upper left entry.

Run time: $O(n^2)$, space: $O(n^2)$

private int[][] dp;
public NumMatrix(int[][] matrix) {
    if(matrix == null||matrix.length == 0||matrix[0].length == 0) return;   
    int m = matrix.length, n = matrix[0].length;

    dp = new int[m+1][n+1];
    for(int i = 1; i <= m; i++){ // store the sum of neighbors
        for(int j = 1; j <= n; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1];
        }
    }
}

public int sumRegion(int row1, int col1, int row2, int col2) {
    int iMin = Math.min(row1, row2);
    int iMax = Math.max(row1, row2);
    int jMin = Math.min(col1, col2);
    int jMax = Math.max(col1, col2);

    return dp[iMax + 1][jMax + 1] - dp[iMax + 1][jMin] - dp[iMin][jMax + 1] + dp[iMin][jMin];    
}

123. Best Time to Buy and Sell Stock III

Use four variables: first buy price (min), profit after first sell (max), profit after second buy (max), and profit after second sell (max).

Run time: $O(n)$, space: $O(1)$

public int maxProfit(int[] prices) {
    int n = prices.length;
    if(prices.length < 2) return 0;
    
    int firstBuy = prices[0];
    int firstSell = 0;
    int secondBuy = Integer.MIN_VALUE;
    int secondSell = 0;
    for(int p: prices){
        firstBuy = Math.min(firstBuy, p); // buy at lowest price
        firstSell = Math.max(firstSell, p-firstBuy); // max profit
        secondBuy = Math.max(secondBuy, firstSell-p); // profit after buying second stock
        secondSell = Math.max(secondSell, p+secondBuy); // final profit
    }
    return secondSell;
}

1218. Longest Arithmetic Subsequence of Given Difference

Use a map to store the length of the sequence that contains this number; if the previous element exist, then put this element with new length into the map.

Run time: $O(n)$, space: $O(n)$

public int longestSubsequence(int[] arr, int difference) {
	HashMap<Integer, Integer> dp = new HashMap<>();
	int longest = 0;
	for(int i=0; i<arr.length; i++) {
		dp.put(arr[i], dp.getOrDefault(arr[i] - difference, 0) + 1);
		longest = Math.max(longest, dp.get(arr[i]));
	}
	return longest;
}

403. Frog Jump

Faster way

public boolean canCross(int[] stones) {
    if(stones.length == 2){
        if(stones[1]-stones[0] == 1) return true;
        return false;
    }
    Map<Integer,Boolean> map = new HashMap<>();
    for(int i=0;i<stones.length-1;i++){
        map.put(stones[i],true);
    }
    
    for(int i=stones.length-2;i>=1;--i){
        if(bottomUp(map,stones[i],stones[stones.length-1]-stones[i])){
            return true;   
        }
    }
    
    return false;
}

private boolean bottomUp(Map<Integer,Boolean> map,int stone,int k){
    if(stone == 0) return k == 1;
    if(k <= 0 || stone < 0 || !map.containsKey(stone)) return false;
    return bottomUp(map,stone - (k-1),k-1) || bottomUp(map,stone-k,k) || bottomUp(map,stone-(k+1),k+1);
}

Use a map to store the stone location and a set of possible steps
Put the initial location (0) and possible step (1) into the map
Loop through every stone, get the step, calculate the location
Then get the set of location, put three possible steps into the set

Run time: $O(n^2)$, space: $O(n^2)$

   public boolean canCross(int[] stones) {
// the most progressive arrange is [0, 1, 3, 6, 10, 15, 21, ...]
// the right-most point is at most 0 + (1 + len - 1) * (len - 1) / 2
if(stones == null || stones.length == 0 || stones[1] != 1 ||
               stones[stones.length - 1] > (stones.length * (stones.length - 1)) / 2) return false;
       
       HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>(stones.length);
       map.put(0, new HashSet<Integer>());
       map.get(0).add(1);
       for (int i = 1; i < stones.length; i++) {
       		map.put(stones[i], new HashSet<Integer>() );
       }
       
       for (int i = 0; i < stones.length - 1; i++) {
       		int stone = stones[i];
       		for (int step : map.get(stone)) {
       			int reach = step + stone;
       			if (reach == stones[stones.length - 1]) return true;
       			HashSet<Integer> set = map.get(reach);
       			if (set != null) {
       		    		set.add(step);
       		    		if (step - 1 > 0) set.add(step - 1);
       		    		set.add(step + 1);
       			}
       		}
       }
       return false;
   } 

42. Trapping Rain Water

Use two arrays to keep track of the index with higher bars
The minimum of left and right bars minus the current height is the water for this location
Run time: $O(n)$, space: $O(n)$

public int trap(int[] height) {
	int ans = 0, n = height.length, leftSoFar = 0, rightSoFar = n-1;
	int[] left = new int[n], right = new int[n];
	
	for(int i = 0; i < n; i++){
		if(height[leftSoFar] < height[i]) leftSoFar = i;
		if(height[rightSoFar] < height[n-1-i]) rightSoFar = n-1-i;
		left[i] = leftSoFar;
		right[n-1-i] = rightSoFar;
	}
	
	for(int i = 0; i < n; i++){
		ans += Math.min(height[left[i]], height[right[i]])-height[i];
	}
	return ans;
}

Search

---

Trie

1268. Search Suggestions System

Use trie tree to store the characters and sort them, then add corresponding words to the list by moving a pointer in the trie tree

class Trie {
    Trie[] sub = new Trie[26];
    LinkedList<String> suggestion = new LinkedList<>();
}

public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Trie root = new Trie();
    for (String p : products) { // build Trie.
        Trie t = root;
        for (char c : p.toCharArray()) { // insert current product into Trie.
            if (t.sub[c - 'a'] == null) t.sub[c - 'a'] = new Trie();
            t = t.sub[c - 'a'];
            t.suggestion.offer(p); // put products with same prefix into suggestion list.
            Collections.sort(t.suggestion); // sort products.
            if (t.suggestion.size() > 3) // maintain 3 lexicographically minimum strings.
                t.suggestion.pollLast();
        }
    }
    List<List<String>> ans = new ArrayList<>();
    for (char c : searchWord.toCharArray()) { // search product.
        if (root != null) // if current Trie is NOT null.
            root = root.sub[c - 'a'];
        ans.add(root == null ? Arrays.asList() : root.suggestion); // add it if there exist products with current prefix.
    }
    return ans;
}

public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products);
    List<List<String>> ans = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    
    for(char c: searchWord.toCharArray()){
        sb.append(c);
        List<String> temp = new ArrayList<>();
        for(String s: products){
            if(s.startsWith(sb.toString())){
                if(temp.size() >= 3) break;
                else temp.add(s);
            } 
        }
        Collections.sort(temp);
        ans.add(temp);
    }
    return ans;
}

211. Add and Search Word - Data structure design

Create a class called TrieNode, and in each class there’s a array of 26 TrieNodes
When adding a word, look through each character and move a pointer from the root node to the corresponding child node. Create a new node if there’s no node in the entry
Given a word, walk through each letter and keep track of the length and the node pointer
If it is a dot, loop through all children nodes if it is not null
Otherwise, call the helper function recursively

class WordDictionary {

    public class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public boolean isWord;
    }
    
    private TrieNode root = new TrieNode();

    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c-'a'] == null) {
                node.children[c-'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return match(word.toCharArray(), 0, root);
    }
    
    private boolean match(char[] chs, int k, TrieNode node) {
        if (k == chs.length) return node.isWord;
        if (chs[k] == '.') {
            for (int i = 0; i < node.children.length; i++) {
                if (node.children[i] != null && match(chs, k + 1, node.children[i])) {
                    return true;
                }
            }
        } else {
            return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
        }
        return false;
    }
}

208. Implement Trie (Prefix Tree) (M)

Build TrieNode to hold a list of TrieNode for searching

class Trie {
    
    class TrieNode {
        public char val;
        public boolean isWord; 
        public TrieNode[] children = new TrieNode[26];
        public TrieNode() {}
        TrieNode(char c){
            TrieNode node = new TrieNode();
            node.val = c;
        }
    } 

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
        root.val = ' ';
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode ws = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(ws.children[c - 'a'] == null){
                ws.children[c - 'a'] = new TrieNode(c);
            }
            ws = ws.children[c - 'a'];
        }
        ws.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode ws = root; 
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(ws.children[c - 'a'] == null) return false;
            ws = ws.children[c - 'a'];
        }
        return ws.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode ws = root; 
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(ws.children[c - 'a'] == null) return false;
            ws = ws.children[c - 'a'];
        }
        return true;
    }
}

Breadth-First Search (BFS)

1091. Shortest Path in Binary Matrix

Be careful that the size of queue is dynamic so each time we need to use an int to memorize the current size and run for loop to poll the element. Also use a boolean matrix to keep track of the visited cells.

Run time: $O(n^2)$, space: $O(n^2)$

public int shortestPathBinaryMatrix(int[][] grid) {
    if(grid == null || grid.length == 0 || grid[0].length == 0) return -1;

    int steps = 0, m = grid.length, n = grid[0].length;
    if(grid[0][0] == 1 || grid[m-1][n-1] == 1) return -1;
            
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{0,0});
    
    boolean[][] visited = new boolean[m][n];
    visited[0][0] = true;

    int[] dX = new int[]{0,0,1,-1,1,-1,-1,1};
    int[] dY = new int[]{1,-1,0,0,-1,1,-1,1};
    
    while(!q.isEmpty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            int[] cur = q.poll();
            if(cur[0] == m-1 && cur[1] == n-1) return steps+1;
            for(int j = 0; j < 8; j++){
                int tempX = cur[0] + dX[j], tempY = cur[1] + dY[j];
                if(tempX < 0 || tempY < 0 || tempX >= m || 
                   tempY >= n || grid[tempX][tempY] == 1 || 
                   visited[tempX][tempY]) continue;
                q.add(new int[]{tempX, tempY});
                visited[tempX][tempY] = true;
            }
        }
        steps++;
    }
    return -1;
}

1263. Minimum Moves to Move a Box to Their Target Location

BFS+backtracking
First find the positions of player, box, and target
Use a HashSet to keep track of the visited positions
Use a Queue to record the possible movements
For each possible movement, use a helper function to test if the player could reach the position to push the box. If valid, offer this position to the queue, and add it to the set
Use a count to keep track of the movements
Poll the position from the queue, if the box is at the end position, return the number of steps
Otherwise, mark the box position as wall, similarly explore 4 possible movements.
If the movement is valid (in the bound, not visited, can reached by player), add it to the queue and mark as visited
After trying 4 movements, reset the position as road
Update the number of movements after we polled the element from queue

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

  public int minPushBox(char[][] grid) {
      int rowLen = grid.length, colLen = rowLen == 0 ? 0 : grid[0].length;
      int[] start = new int[2];  // start position of the box
int[] end = new int[2];  // target position where the box should be moved to
int[] player = new int[2];  // start position of the person

// initialize three important positions
      for (int row = 0; row < rowLen; row++) {
          for (int col = 0; col < colLen; col++) {
              if (grid[row][col] == 'B') {
                  start[0] = row;
                  start[1] = col;
              } else if (grid[row][col] == 'T') {
                  end[0] = row;
                  end[1] = col;
              } else if (grid[row][col] == 'S') {
                  player[0] = row;
                  player[1] = col;
              }
          }
      }
      // record both the position of the box and the position to push the box
      Queue<int[][]> queue = new LinkedList<>();  
      // same as queue for deduplication
      Set<String> set = new HashSet<>(); 
      for (int i = 0; i < 4; i++) { // 4 possible positions to push the box
          int[] push = new int[]{start[0] + dir[i], start[1] + dir[i+1]};  
          // skip if the person is not able to reach the push position
          if (!canReach(grid, player, push)) continue;
          queue.offer(new int[][]{start, push});  
          String visited = (start[0] * colLen + start[1]) + "," + (push[0] * colLen + push[1]);
          set.add(visited); 
      }
      
      int move = 0;
      while (!queue.isEmpty()) {
          int size = queue.size();  // search each level
          while (size-- > 0) {
              int[][] curr = queue.poll();
              int[] box = curr[0], push = curr[1];
              if (Arrays.equals(box, end)) return move;
          
              grid[box[0]][box[1]] = '#';  // set the box to be impassible 
              for (int i = 0; i < 4; i++) {
                  // the position where the box is moved  to
                  int nextRow = box[0] + dir[i], nextCol = box[1] + dir[i + 1];  
                  // the position where the person should stand in order to move the box
                  int[] nextPush = new int[]{box[0] - dir[i], box[1] - dir[i + 1]};  
                  String visited = (nextRow * colLen + nextCol) + "," + (nextPush[0] * colLen + nextPush[1]);
                  
			// skip if this position is not valid
			if (nextRow < 0 || nextRow >= rowLen || nextCol < 0 || 
                      nextCol >= colLen || grid[nextRow][nextCol] == '#' || 
                      set.contains(visited) || !canReach(grid, push, nextPush)) continue; 

                  queue.offer(new int[][]{new int[]{nextRow, nextCol}, nextPush});
                  set.add(visited);
              }
              grid[box[0]][box[1]] = '.';  // reset  
          }
          move++;  // update move
      }
      // unable to reach the target position or even the beginning position to push the box
      return -1;  
  }
  
  /** check if a person can reach the destination position from the source position */
  private boolean canReach(char[][] grid, int[] source, int[] destination) {
      int rowLen = grid.length, colLen = rowLen == 0 ? 0 : grid[0].length;
      Queue<int[]> queue = new LinkedList<>();
      Set<Integer> set = new HashSet<>();
      queue.offer(source);
      set.add(source[0] * colLen + source[1]);
      while (!queue.isEmpty()) {
          int[] curr = queue.poll();
          if (Arrays.equals(curr, destination)) return true;
          for (int i = 0; i < 4; i++) {
              // the next position where the person is going
              int nextRow = curr[0] + dir[i], nextCol = curr[1] + dir[i+1];  
              int nextIndex = nextRow * colLen + nextCol;
             
	    // skip if this position is not valid
              if (nextRow < 0 || nextRow >= rowLen || nextCol < 0 || nextCol >= colLen ||
                  grid[nextRow][nextCol] == '#' || set.contains(nextIndex)) continue;   
              
              queue.offer(new int[]{nextRow, nextCol});
              set.add(nextIndex);
          }
      }
      return false;
  }

126. Word Ladder II

Use BFS to find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node’s next level neighbors to HashMap;
Use DFS to output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    List<List<String>> res = new ArrayList<>();
    if (!dict.contains(endWord)) {
        return res;
    }
    Map<String, List<String>> map = getChildren(beginWord, endWord, dict);
    List<String> path = new ArrayList<>();
    path.add(beginWord);
    findLadders(beginWord, endWord, map, res, path);
    return res;
    
}

public void findLadders(String beginWord, String endWord, Map<String, List<String>> map, List<List<String>> res, List<String> path) {
    if (beginWord.equals(endWord)) {
        res.add(new ArrayList<>(path));
    }
    if (!map.containsKey(beginWord)) {
        return;
    }
    for (String next : map.get(beginWord)) {
        path.add(next);
        findLadders(next, endWord, map, res, path);
        path.remove(path.size() - 1);
    }
}

public Map<String, List<String>> getChildren(String beginWord, String endWord, Set<String> dict) {
    Map<String, List<String>> map = new HashMap<>();
    Set<String> start = new HashSet<>();
    start.add(beginWord);
    Set<String> end = new HashSet<>();
    Set<String> visited = new HashSet<>();
    end.add(endWord);
    boolean found = false;
    boolean isBackward = false;
    while (!start.isEmpty() && !found) {
        if (start.size() > end.size()) {
            Set<String> tem = start;
            start = end;
            end = tem;
            isBackward = !isBackward;
        }
        Set<String> set = new HashSet<>();
        for (String cur : start) {
            visited.add(cur);
            for (String next : getNext(cur, dict)) {
                if (visited.contains(next) || start.contains(next)) {
                    continue;
                }
                if (end.contains(next)) {
                    found = true;
                }
                set.add(next);
                String parent = isBackward ? next : cur;
                String child = isBackward ? cur : next;
                if (!map.containsKey(parent)) {
                    map.put(parent, new ArrayList<>());
                }
                map.get(parent).add(child);
                
            }
        }
        start = set;
    }
    return map;
    
}
private List<String> getNext(String cur, Set<String> dict) {
    List<String> res = new ArrayList<>();
    char[] chars = cur.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        char old = chars[i];
        for (char c = 'a'; c <= 'z'; c++) {
            if (c == old) {
                continue;
            }
            chars[i] = c;
            String next = new String(chars);
            if (dict.contains(next)) {
                res.add(next);
            }
        }
        chars[i] = old;
    }
    return res;
}

752. Open the Lock (G)

GFG link: Bidirectional Search: 2-end BFS
Suppose if branching factor of tree is b and distance of goal vertex from source is d, then the normal BFS/DFS searching complexity would be $O(b^d)$. On the other hand, if we execute two search operation then the complexity would be $O(b^{d/2})$ for each search and total complexity would be $O(b^{d/2}+b^{d/2})$ which is far less than $O(b^d)$.

Run time: $O(b^{d/2})$, space: $O(b^{d/2})$

public int openLock(String[] deadends, String target) {
    Set<String> begin = new HashSet<>();
    Set<String> end = new HashSet<>();
    Set<String> deads = new HashSet<>(Arrays.asList(deadends));
    begin.add("0000");
    end.add(target);
    int level = 0;
    Set<String> temp;
    while(!begin.isEmpty() && !end.isEmpty()) {
        if (begin.size() > end.size()) {
            temp = begin;
            begin = end;
            end = temp;
        }
        temp = new HashSet<>();
        for(String s : begin) {
            if(end.contains(s)) return level; // found
            if(deads.contains(s)) continue; // dead end or appear before
            deads.add(s);
            StringBuilder sb = new StringBuilder(s);
            for(int i = 0; i < 4; i ++) { // all possible moves
                char c = sb.charAt(i);
                String s1 = sb.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + sb.substring(i + 1);
                String s2 = sb.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + sb.substring(i + 1);
                if(!deads.contains(s1)) temp.add(s1);
                if(!deads.contains(s2)) temp.add(s2);
            }
        }
        level++;
        begin = temp;
    }
    return -1;
}

127. Word Ladder

2-end like DFS

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> beginSet = new HashSet<>();
    Set<String> endSet = new HashSet<>();
    beginSet.add(beginWord);
    endSet.add(endWord);
    Set<String> dict = new HashSet<>(wordList);
    if(!dict.contains(endWord)) return 0;
    return search(beginSet, endSet, dict, true, 1);
}

private int search(Set<String> beginSet, Set<String> endSet, Set<String> dict, boolean isForward, int cnt){
    if(beginSet.isEmpty() || endSet.isEmpty()) return 0;
    cnt++;
    dict.removeAll(beginSet);
    Set<String> nextSet = new HashSet<>();
    for(String str : beginSet){
        char[] chs = str.toCharArray();
        for(int i = 0; i < chs.length; i++){
            char c = chs[i];
            for(char j = 'a'; j <= 'z'; j++){
                chs[i] = j;
                String tmp = new String(chs);
                if(!dict.contains(tmp)) continue;
                if(endSet.contains(tmp)) return cnt;
                nextSet.add(tmp);
            }
            chs[i] = c;
        }
    }
    return nextSet.size() > endSet.size() ? search(endSet, nextSet, dict, false, cnt) : search(nextSet, endSet, dict, true, cnt);
}

2-end BFS without helper method

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if (!wordList.contains(endWord)) {
        return 0;
    }
    Set<String> dict = new HashSet<>(wordList);
    Set<String> beginSet = new HashSet<>();
    Set<String> endSet = new HashSet<>();
    beginSet.add(beginWord);
    endSet.add(endWord);

    int step = 1;
    Set<String> visited = new HashSet<>();
    while (!beginSet.isEmpty() && !endSet.isEmpty()) {
        if (beginSet.size() > endSet.size()) {
            Set<String> set = beginSet;
            beginSet = endSet;
            endSet = set;
        }
        Set<String> temp = new HashSet<>();
        for (String word : beginSet) {
            char[] chs = word.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    char old = chs[i];
                    chs[i] = c;
                    String target = String.valueOf(chs);
                    if (endSet.contains(target)) {
                        return step + 1;
                    }
                    if (!visited.contains(target) && dict.contains(target)) {
                        temp.add(target);
                        visited.add(target);
                    }
                    chs[i] = old;
                }
            }
        }
        beginSet = temp;
        step++;
    }
    return 0;
}

Use a queue to add the begin word, then add any transformations that are in the dictionary

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if (!wordList.contains(endWord)) return 0;
    HashSet<String> set = new HashSet<String>(wordList);
    Queue<String> q = new LinkedList<String>();
    int length = 0;
    set.add(endWord);
    q.add(beginWord);
    
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String w = q.poll();
            if (w.equals(endWord)) return length + 1;
            wordMatch(w, set, q);
        }
        length++;
    }
    return 0;
}

public void wordMatch(String w, Set<String> set, Queue<String> q) {
    for (int i = 0; i < w.length(); i++) {
        char[] word = w.toCharArray();
        for (int j = 0; j < 26; j++) {
            char c = (char) ('a' + j);
            if (word[i] == c) continue;
            word[i] = c;
            String s = String.valueOf(word);
            if (set.contains(s)) {
                set.remove(s);
                q.offer(s);
            }
        }
    }
}

743. Network Delay Time

Dijkstra: use list to store N+1 node lists, every time get the list of source node, add sink and cost
Create priority queue and override comparator as “(a,b) -> (a[1]-b[1])” get min cost
Pretty similar idea as below

Run time: $O(n)$, space: $O(n)$

public int networkDelayTime(int[][] times, int N, int K) {
    List<List<int[]>> graph = new ArrayList<>(N + 1);
    for(int i = 0; i <= N; i++) graph.add(new ArrayList<>());
    for(int[] time : times) graph.get(time[0]).add(new int[]{time[1], time[2]});
    PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
        public int compare(int[] a, int[] b) {
            return a[1] - b[1];
        }
    });
    pq.offer(new int[]{K, 0});
    Set<Integer> visited = new HashSet<>();
    int dist = 0;
    while(!pq.isEmpty()) {
        int[] curr = pq.poll();
        if(!visited.add(curr[0])) continue;
        dist = curr[1];
        for(int[] neighbor : graph.get(curr[0])) {
            if(!visited.contains(neighbor[0])) pq.offer(new int[]{neighbor[0], neighbor[1] + curr[1]});
        }
    }
    return visited.size() == N ? dist : -1;
}

BFS: use Map<source, Map<sink, cost>> to store all info
Create priority queue and override comparator as “(a,b) -> (a[0]-b[0])”
PQ stores int[]{total cost, next node}
A boolean array to record whether the node is visited or not
Skip visited node, and mark unvisited node, update total cost
Decrement N (num of nodes), if it’s zero, return the cost
Add new array to PQ

Run time: $O(n)$, space: $O(n)$

public int networkDelayTime(int[][] times, int N, int K) {
    Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    for(int[] time: times){
        map.putIfAbsent(time[0], new HashMap<>());
        map.get(time[0]).put(time[1], time[2]);
    }
    
    Queue<int[]> pq = new PriorityQueue<>((a,b) -> (a[0]-b[0]));
    pq.add(new int[]{0,K});
    boolean[] visited = new boolean[N+1];
    int res = 0;
    
    while(!pq.isEmpty()){
        int[] cur = pq.remove();
        int curNode = cur[1];
        int curDist = cur[0];
        if(visited[curNode]) continue;
        visited[curNode] = true;
        res = curDist;
        N--;
        if(N == 0) return res; 
        if(map.containsKey(curNode)){
            for(int nextNode: map.get(curNode).keySet()){
                pq.add(new int[]{curDist+map.get(curNode).get(nextNode), nextNode});
            }
        }
    }
    return -1;
}

317. Shortest Distance from All Buildings (G)

Create two 2D arrays to keep track of the smallest distance and the number of building that this location can reach
Helper method:

Run time: $O()$, space: $O()$

public int shortestDistance(int[][] grid) {
    int[][] distance = new int[grid.length][grid[0].length];
    int[][] reach = new int[grid.length][grid[0].length];
    int numBuilding = 0;
    
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                helper(grid, distance, reach, i, j);
                numBuilding++;
            }
        }
    }
 
    int result = Integer.MAX_VALUE;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 0 && reach[i][j] == numBuilding) {
                result = Math.min(result, distance[i][j]);
            }
        }
    }
 
    return result == Integer.MAX_VALUE ? -1 : result;
}

private void helper(int[][] grid, int[][] distance, int[][] reach, int i, int j) {
 
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
 
    //two queue, one for direction, one for distance tracking
    LinkedList<int[]> q = new LinkedList<>();
    LinkedList<Integer> qDist = new LinkedList<>();
 
    q.offer(new int[]{i, j});
    qDist.offer(1);
 
    while (!q.isEmpty()) {
        int[] head = q.poll();
        int dis = qDist.poll();
 
        for (int k = 0; k < 4; k++) {
            int x = head[0] + dx[k];
            int y = head[1] + dy[k];
 
            if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 0) { // valid move
                grid[x][y] = -1;
 
                q.offer(new int[]{x, y});
                qDist.offer(dis + 1); // distance from current new location to building
 
                distance[x][y] += dis;
                reach[x][y]++; // reachable
            }
        }
    }
 
    for (int m = 0; m < grid.length; m++) {
        for (int n = 0; n < grid[0].length; n++) {
            if (grid[m][n] == -1) {
                grid[m][n] = 0;
            }
        }
    }
}

Depth-First Search (DFS)

695. Max Area of Island

A helper method to explore the neighbors. If the cell is 1, set it to 0, and return the sum of helper methods taking its neighbors’ positions, plus 1

Run time: $O(mn)$, space: $O(1)$

public int maxAreaOfIsland(int[][] grid) {
    int max = 0, m = grid.length, n = grid[0].length;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 1) max = Math.max(max, findArea(grid, i, j));
        }
    }
    return max;
}

private int findArea(int[][] grid, int i, int j){
    int m = grid.length, n = grid[0].length;
    if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) return 0;
    grid[i][j] = 0;
    return findArea(grid, i+1, j) + findArea(grid, i-1, j) + 
        findArea(grid, i, j+1) + findArea(grid, i, j-1) + 1;
}

79. Word Search (M)

Backtracking: if this current character is valid, mark it as visited, then explore its neighbors, and then reset

Run time: $O(mn)$, space: $O(1)$

public boolean exist(char[][] board, String word) {
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++){
            if(exist(board, i, j, word, 0))
                return true;
        }
    return false;
}

private boolean exist(char[][] board, int i, int j, String word, int ind){
    if(ind == word.length()) return true;
    if(i >= board.length || i < 0 || j < 0 || j >= board[0].length || 
       board[i][j] != word.charAt(ind)) return false;
    
    board[i][j] = '*'; // mark as visited
    boolean result = exist(board, i-1, j, word, ind+1) ||
                     exist(board, i, j-1, word, ind+1) ||
                     exist(board, i, j+1, word, ind+1) ||
                     exist(board, i+1, j, word, ind+1);
    board[i][j] = word.charAt(ind); // put it back
    return result;
}

200. Number of Islands (M)

Use a helper function to explore the island
As long as the position is valid and is 1, mark it as 0, since it would be counted as one island

Run time: $O(mn)$, space: $O(1)$

public int numIslands(char[][] grid) {
    int ans = 0;
    for(int i = 0; i < grid.length; i++){
        for(int j = 0; j < grid[0].length; j++){
            ans += helper(grid, i, j);
        }
    }
    return ans;
}

private int helper(char[][] grid, int i, int j){
    if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0')
        return 0;
    grid[i][j] = '0';
    // explore all neighbors and mark them as visited
    helper(grid, i+1, j);
    helper(grid, i-1, j);
    helper(grid, i, j+1);
    helper(grid, i, j-1);
    return 1;
}

663. Walls and Gates (LintCode)

搜索0的位置，每找到一个0，以其周围四个相邻点为起点，开始 DFS 遍历，并带入深度值1，如果遇到的值大于当前深度值，将位置值赋为当前深度值，并对当前点的四个相邻点开始DFS遍历，注意此时深度值需要加1，这样遍历完成后，所有的位置就被正确地更新了

public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0) dfs(rooms, i, j, 0);
            }
        }
    }
    private void dfs(int[][] rooms, int i, int j, int val) {
        if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < val) return;
        rooms[i][j] = val;
        dfs(rooms, i + 1, j, val + 1);
        dfs(rooms, i - 1, j, val + 1);
        dfs(rooms, i, j + 1, val + 1);
        dfs(rooms, i, j - 1, val + 1);
    }

BFS 的解法，需要借助 queue，首先把门的位置都排入 queue 中，然后开始循环，对于门位置的四个相邻点，判断其是否在矩阵范围内，并且位置值是否大于上一位置的值加1，如果满足这些条件，将当前位置赋为上一位置加1，并将次位置排入 queue 中，这样等 queue 中的元素遍历完了，所有位置的值就被正确地更新了

public void wallsAndGates(int[][] rooms) {
    Queue<int[]> q = new LinkedList<>();
    int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    for (int i = 0; i < rooms.length; i++) {
        for (int j = 0; j < rooms[0].length; j++) {
            if (rooms[i][j] == 0) q.push(new int[]{i, j});   
        }
    }
    while (!q.empty()) {
        int i = q.front().first, j = q.front().second; q.pop();
        for (int k = 0; k < dirs.length; k++) {
            int x = i + dirs[k][0], y = j + dirs[k][1];
            if (x < 0 || x >= rooms.length || y < 0 || y >= rooms[0].length || rooms[x][y] < rooms[i][j] + 1) continue;
            rooms[x][y] = rooms[i][j] + 1;
            q.push(new int[]{x, y});
        }
    }
}

934. Shortest Bridge (M)

DFS + BFS: first mark all islands from 1 to 2, if we found the second unexplored island, add the position to the queue
In the queue, poll the position and try to explore the neighbors. If the movement is valid, check if it is 2 (found already), or check if it is 1 (on the same island), or check if it is 0 (valid change), then mark is as 1 and add to the queue.

Run time: $O(n^2)$, space: $O(1)$

public int shortestBridge(int[][] A) {
    int level = 0;
    Queue<int[]> queue = new LinkedList<>();
    boolean found = false;
    
    for(int i = 0; i < A.length; i++){
        for(int j = 0; j < A[0].length; j++){
            if(A[i][j] == 1 && !found){
                dfs(A, i, j, A.length, A[0].length);
                found = true;
            }
            if(found && A[i][j] == 1) {
                queue.add(new int[] {i, j});
            }
        }
    }
    
    int[][] d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    while(!queue.isEmpty()) {
        int size = queue.size();
        for(int s = 0; s < size; s++) {
            int[] pos = queue.remove();
            for(int i = 0; i < 4; i++) {
                int x = pos[0] + d[i][0];
                int y = pos[1] + d[i][1];
                if(x < 0 || x >= A.length || y < 0 || y >= A[0].length) continue;
                if(A[x][y] == 2) return level;
                else if(A[x][y] == 1) continue;
                else if(A[x][y] == 0) {
                    A[x][y] = 1;
                    queue.add(new int[]{x, y});
                }
            }
        }
        level++;
    }
    return -1;
    
}

public void dfs(int[][] A, int i, int j, int m, int n) {
    A[i][j] = 2;
    if(i - 1 >= 0 && A[i-1][j] == 1) dfs(A, i - 1, j, m, n);
    if(i + 1 < m && A[i+1][j] == 1) dfs(A, i + 1, j, m, n);
    if(j - 1 >= 0 && A[i][j - 1] == 1) dfs(A, i, j - 1, m, n);
    if(j + 1 < n && A[i][j + 1] == 1) dfs(A, i, j + 1, m, n);
}

1245. Tree Diameter

Traverse all the nodes of the tree. The diameter of the tree is maximum of the longest path through each node.
Longest path through a node is sum of top 2 depths of children’s tree.

Run time: $O(n)$, space: $O(n)$, where $n$ is edges.length

int diameter = 0;

public int treeDiameter(int[][] edges) {
    int n = edges.length + 1;
    LinkedList<Integer>[] adjacencyList = new LinkedList[n];
    for (int i = 0; i < n; ++i) adjacencyList[i] = new LinkedList<>();
    for (int[] edge : edges) {
        adjacencyList[edge[0]].add(edge[1]);
        adjacencyList[edge[1]].add(edge[0]);
    }
    diameter = 0;
    depth(0, -1, adjacencyList);
    return diameter;
}

private int depth(int root, int parent, LinkedList<Integer>[] adjacencyList) {
    int maxDepth1st = 0, maxDepth2nd = 0;
    for (int child : adjacencyList[root]) {
        if (child != parent) { // Only one way from root node to child node, don't allow child node go to root node again!
            int childDepth = depth(child, root, adjacencyList);
            if (childDepth > maxDepth1st) {
                maxDepth2nd = maxDepth1st;
                maxDepth1st = childDepth;
            } else if (childDepth > maxDepth2nd) {
                maxDepth2nd = childDepth;
            }
        }
    }
    int longestPathThroughRoot = maxDepth1st + maxDepth2nd; // Sum of the top 2 highest depths is the longest path through this root
    diameter = Math.max(diameter, longestPathThroughRoot);
    return maxDepth1st + 1;
}

1239. Maximum Length of a Concatenated String with Unique Character

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters. Return the maximum possible length of s.

private int max = 0;
public int maxLength(List<String> arr) {
    dfs(arr, 0, "");
    return max;
}

public void dfs(List<String> arr, int index, String concatenatStr) {
    if (isUnique(concatenatStr)) max = Math.max(max, concatenatStr.length());
    if (index == arr.size() || !isUnique(concatenatStr))  return;
    for (int i = index; i < arr.size(); i++) {
        dfs(arr, i + 1, concatenatStr + arr.get(i));
    }
}
public boolean isUnique(String s) {
    int[] alpha = new int[26];
    for (int i = 0; i < s.length(); i++) alpha[s.charAt(i) - 'a']++;
    for (int i = 0; i < alpha.length; i++) if (alpha[i] > 1) return false;
    return true;
}

My way

public int maxLength(List<String> arr) {
    int len = 0;
    for(int i = 0; i < arr.size(); i++){
        String str = arr.get(i);
        Set<Character> set = new HashSet<>();
        int x = 0;
        while(x < str.length()){
            char c = str.toCharArray()[x];
            if(!set.add(c)) break;
            x++;
        }
        if(x == str.length()){
            len = Math.max(len, helper(set, arr, i));
        }
    }
    return len;
}

int helper(Set<Character> set, List<String> arr, int index){
    if(index >= arr.size()) return set.size();
    int maxLen = set.size();
    for(int i = index+1; i < arr.size(); i++){
        String str = arr.get(i);
        Set<Character> newSet = new HashSet<>(set);
        int x = 0;
        // System.out.println(arr.get(index)+" "+str +" "+ newSet.size());
        while(x < str.length()){
            char c = str.toCharArray()[x];
            if(!newSet.add(c)) break;
            x++;
        }
        // System.out.println(set.size()+str.length());
        if(x == str.length()){
            maxLen = Math.max(maxLen, helper(newSet, arr, i));
        }
    }
    return maxLen;
}

1219. Path with Maximum Gold

Use a helper function to find the max points; if the cell is invalid, return the current sum.
First update the sum of points, then mark the cell visited, and call helper function to explore the neighbor cells and update the temp max. At last mark the cell unvisited and return the temp max.

Run time: $O(mn)$, space: $O(1)$

private static final int[] d = {0, 1, 0, -1, 0};
public int getMaximumGold(int[][] grid) {
    int ans = 0;
    for (int i = 0; i < grid.length; ++i) {
        for (int j = 0; j < grid[0].length; ++j) {
            ans = Math.max(ans, dfs(grid, i, j, 0));
        }
    }
    return ans;
}
private int dfs(int[][] g, int i, int j, int sum) {
    if (i < 0 || i >= g.length || j < 0 || j >= g[0].length || g[i][j] == 0 || g[i][j] > 100) 
        return sum;
    sum += g[i][j];
    g[i][j] += 1000; // mark visited.
    int mx = 0;
    for (int k = 0; k < 4; ++k) { // traverse 4 neighbors to get max value.
        mx = Math.max(mx, dfs(g, i + d[k], j + d[k + 1], sum));
    }
    g[i][j] -= 1000; // change back.
    return mx;
}

694. Number of Distinct Islands

Use set1 to store the string version of set2 storing island shape
Explore up, down, left, right location and if it’s 1, then add the location difference to the set2

Run time: $O(n^3)$, space: $O(n^2)$

public int numDistinctIslands(int[][] grid) {
    if (grid == null || grid.length < 1 || grid[0].length < 1) return 0;
    int m = grid.length, n = grid[0].length;
    Set<String> res = new HashSet<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            Set<String> set = new HashSet<>();
            if (grid[i][j] == 1) {
                dfs(grid, i, j, i, j, set);
                res.add(set.toString());
            }
        }
    }
    return res.size();
}

public void dfs(int[][] grid, int i, int j, int baseX, int baseY, Set<String> set) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) return;
    set.add((i - baseX) + "_" + (j - baseY));
    grid[i][j] = 0;
    dfs(grid, i + 1, j, baseX, baseY, set);
    dfs(grid, i - 1, j, baseX, baseY, set);
    dfs(grid, i, j - 1, baseX, baseY, set);
    dfs(grid, i, j + 1, baseX, baseY, set);
}

329. Longest Increasing Path in a Matrix

Use cache of same size as the matrix, walk through each entry
Use helper function to check if this movement is valid and the next entry is larger than the current one, then update max; check 4 directions, then update max and return it
Run time: $O(n^4)$, space: $O(n^2)$

public int longestIncreasingPath(int[][] matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) return 0;
    
    int max = 0;
    int[][] cache = new int[matrix.length][matrix[0].length];
    for(int i = 0; i < matrix.length; i++) {
        for(int j =0; j < matrix[0].length; j++) {
            max = Math.max(dfs(matrix, i, j, cache), max);
        }
    }
    return max;
}

private int dfs(int[][] matrix, int i, int j, int[][] cache) {
    if (cache[i][j] > 0) return cache[i][j];
    
    int count1 = 0,count2=0,count3=0,count4=0;
    if (j - 1 >= 0 && matrix[i][ j - 1] > matrix[i][j])
    		count1 = dfs(matrix, i, j - 1, cache);
    if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j])
   		 count2 = dfs(matrix, i - 1, j, cache);
    if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j])
    		count3 = dfs(matrix, i, j + 1, cache);
    if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j])
    		count4 = dfs(matrix, i + 1, j, cache);
    
    int longestIncreasingPath = Math.max(Math.max(count1, count2), Math.max(count3, count4));
    cache[i][j] = 1 + longestIncreasingPath;
    
    return cache[i][j];
}

248. Strobogrammatic Number III

Loop through num of low digits to num of high digits
Check a couple of edge cases(length, starting 0, smaller/larger)
Run time: $O(n)$, space: $O(1)$

   public int strobogrammaticInRange(String low, String high) {
       int res = 0;
       find(low, high, "", i, res);
       find(low, high, "0", i, res);
       find(low, high, "1", i, res);
       find(low, high, "8", i, res);
       return res;
   }
   
   void find(String low, String high, String w, int res){
   	if(w.length() >= low.length() && w.length() <= high.length()){
	if(w.length() >= high.length() && w.compareTo(high) > 0) return;
	if((w.length() <= 1 || w.charAt(0) != '0') && (w.length() != low.length() || w.compareTo(low) >= 0) res++;
}

if(w.length+2 > high.size()) return;
       find(low, high, "0" + w + "0", res);
       find(low, high, "1" + w + "1", res);
       find(low, high, "6" + w + "9", res);
       find(low, high, "8" + w + "8", res);
       find(low, high, "9" + w + "6", res);
   }

98. Validate Binary Search Tree

Recursion
Run time $O(n)$, space $O(h)$

Integer prev = null;
    
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        
        if(!isValidBST(root.left)) return false;
        
        if(prev != null && prev >= root.val) return false;
        else prev = root.val;
        
        if(!isValidBST(root.right)) return false;
        
        return true;
    }

min max comparison
Run time $O(n)$, space $O(h)$

public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return valid(root, null, null);
    }
    public boolean valid(TreeNode n, Integer min, Integer max){
        if(n == null) return true;

        if ((min != null && n.val <= min) || (max != null && n.val >= max))
            return false;
        
        return valid(n.left, min, n.val) && valid(n.right, n.val,max);
    }

200. Number of Islands (M)

DFS: $O(n^2)$, space complexity: $O(1)$

public int numIslands(char[][] grid) {
        int ans = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                ans += helper(i, j, grid);
            }
        }
        return ans;
    }
    
    int helper(int i, int j, char[][] grid){
        if(i<0 || j<0 || i>=grid.length || j>=grid[0].length||
          grid[i][j] == '0') return 0;
        
        grid[i][j] = '0';
        helper(i+1,j,grid);
        helper(i-1,j,grid);
        helper(i,j+1,grid);
        helper(i,j-1,grid);
        return 1;
    }

Backtracking (DFS)

37. Sudoku Solver

Every time see an empty cell, try value from 1 to 9 if it is valid
Call helper function and if it is true return true, otherwise reset this cell
After trying all possible values but none of them works, return false

We could replace ‘.’ one by one with a digit that is compatible, if we can’t find a compatible digit for a cube, we backtrace to a cube and fill it with another compatible digit. if we have replace all ‘.’ with a compatible digit, we get a solution
Heuristic method: The key point is which ‘.’ should we replace first? we should first replace intuitively a ‘.’ which has the fewest compatible digit. why? let‘s say，we chosed a digit for the first ‘.’ and finally we find it is a wrong digit, we have to traceback to this first ‘.’, it would be painfully inefficient, so, we should first replace a ‘.’ which we are most likely choose a right digit for it. The fewer compatible digits the ‘.’ has, the more likely we can choose a right digits for it.
The code can be improved, Welcome to share your own tricks and implementation

    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0) return;
        solve(board);
    }
    
    public boolean solve(char[][] board){
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '.'){
                    for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
                        if(isValid(board, i, j, c)){
                            board[i][j] = c; //Put c for this cell
                            
                            if(solve(board)) return true; //If it's the solution return true
                            else board[i][j] = '.'; //Otherwise go back
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c){
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c) return false; //check row
            if(board[row][i] != '.' && board[row][i] == c) return false; //check column
            if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' && 
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
        }
        return true;
    }

465. Optimal Account Balancing (G)

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Use a map to store <person, balance>, where positive balance means extra money, negative implies somebody owes this person.
First record all transactions into the map, then add all nonzero values into a list
Create a Long array to store nonzero balances
Helper method: if current entry is zero, continue till the end, return count

Relevant post: link

    public int minTransfers(int[][] transactions) {
        Map<Integer, Long> map = new HashMap<>();
        for(int[] t : transactions){
            long val1 = map.getOrDefault(t[0], 0L);//balance
            long val2 = map.getOrDefault(t[1], 0L);
            map.put(t[0], val1-t[2]);
            map.put(t[1], val2+t[2]);
        }
        
        List<Long> list = new ArrayList<>();
        for(long val : map.values()){
            if(val!=0) list.add(val);
        }
        Long[] debts = new Long[list.size()];
        debts = list.toArray(debts);
        return helper(debts, 0, 0);
    }
    
    int helper(Long[] debts, int pos, int count ){
        while(pos < debts.length && debts[pos] == 0) pos++;
        if(pos>=debts.length) return count;
        int res = Integer.MAX_VALUE;
        for(int i=pos+1; i<debts.length; i++){
            if((debts[pos] ^ debts[i]) < 0){ // debts[pos] and debts[i] has different signs
                debts[i] += debts[pos];
                res = Math.min(res, helper(debts, pos+1, count+1));
                debts[i] -= debts[pos];//backtracking
            }
        }
        return res;
    }
}

Speed up:
有一点greedy + backtracking的感觉，首先用sort找出-5, 5这种pair, 然后从debts list中移除。

public int minTransfers(int[][] transactions) {
    Map<Integer, Long> map = new HashMap<>();
    for(int[] t : transactions){
        long val1 = map.getOrDefault(t[0], 0L);//balance
        long val2 = map.getOrDefault(t[1], 0L);
        map.put(t[0], val1-t[2]);
        map.put(t[1], val2+t[2]);
    }
    
    List<Long> list = new ArrayList<>();
    for(long val : map.values()){
        if(val!=0) list.add(val);
    }
    int matchCount = removeMatch(list);
    return matchCount + minTransStartFrom(list, 0);
}

private int removeMatch(List<Long> list) {
    Collections.sort(list);
    int left = 0;
    int right = list.size() - 1;
    int matchCount = 0;
    while (left < right) {
        if (list.get(left) + list.get(right) == 0) {
            list.remove(left);
            list.remove(right - 1);
            right -= 2;
            matchCount++;
        } else if (list.get(left) + list.get(right) < 0) {
            left++;
        } else {
            right--;
        }
    }
    return matchCount;
}

 private int minTransStartFrom(List<Long> list, int start) {
    int result = Integer.MAX_VALUE;
    int n = list.size();
    while (start < n && list.get(start) == 0) {
        start++;
    }
    if (start == n) {
        return 0;
    }
    for (int i = start + 1; i < n; i++) {
        if (list.get(i) * list.get(start) < 0) {
            list.set(i, list.get(i) + list.get(start));
            result = Math.min(result, 1 + minTransStartFrom(list, start + 1));
            list.set(i, list.get(i) - list.get(start));
        }
    }
    return result;
}

9999. Construct a word using dice (G)

Onsite interview problem
Given a word of length n and n six-sided dice with a character in each side. Find out if this word can be constructed by the set of given dice.

Run time: $O(|word|)$, space: $O(26)$ assuming alphabet

boolean canConstruct(String word, char[][] M) {
    if(word == null || word.isEmpty() || word.length() > M.length)
        return false;

    Map<Character, List<Integer>> map = new HashMap<>();

    for(int i = 0; i < M.length; i++) {
        char[] A = M[i];
        addToMap(A, i, map);
    }

    int i = 0;
    while(i < word.length()) {
        char c = word.charAt(i++);
        boolean hasFound = findCharFromMap(c, map);
        if( !hasFound) return false;
    }
    return (i == word.length());
}

boolean findCharFromMap(char c, Map<Character, List<Integer>> map) {
    List<Integer> list = map.get(c);
    if(list == null) return false;
    else {
        list.remove(list.size()-1);
        if(list.size() == 0) map.remove(c);
        return true;
    }
}

void addToMap(char[] A, int i, Map<Character, List<Integer>> map) {
    for(char c: A ) {
        List<Integer> list = map.get(c);

        if(list == null) {
            list = new ArrayList<>();
            list.add(i);
        } else {
            if(!list.contains(i)) list.add(i);
        }
        map.put(c, list);
    }
}

1240. Tiling a Rectangle with the Fewest Squares

// 基本思路是从底往上填充整个方块，每次优先填充最底下的没填充的方块，并选择不同的可能的size的正方形把他填充了。我们在dfs的时候维护一个height数组（天际线）。这个天际线是状态的标识。我们最终要求的结果就是天际线是n个m的那个状态的最小方块数。当然纯暴力的话时间复杂度会很高，但是可以通过以下三点来剪枝，或者优化。
// 1、 当前这个天际线的cnt（也就是方块数）已经超过了当前的全局最优解的值，那么直接return
// 2、 当前的这个天际线已经遍历过了，而且之前的cnt比当前的cnt要小，那么直接return
// 3、 当我们找到左下角的空方块后，选取下一个填充方块的的时候优先从较大的方块开始选取，这样可以使得程序快速收敛。（这一点不是剪枝，但是是很重要的优化）

The basic idea is to fill the entire block bottom up. In every step, find the lowest left unfilled square first, and select a square with different possible sizes to fill it. We maintain a height array (skyline) with length n while dfs. This skyline is the identity of the state. The final result we ask for is the minimum number of squares for the state [m, m, m, m, m, m, m] (The length of this array is n). Of course, backtrack without optimization will have a huge time complexity, but it can be pruned or optimized by the following three methods.

When the current cnt (that is, the number of squares) of this skyline has exceeded the value of the current global optimal solution, then return directly.
When the current skyline has been traversed, and the previous cnt is smaller than the current cnt, then return directly.
When we find the empty square in the lowest left corner, we pick larger size for the next square first. This can make the program converge quickly. (It is a very important optimization)

Map<Long, Integer> set = new HashMap<>();
int res = Integer.MAX_VALUE;
public int tilingRectangle(int n, int m) {
    if (n == m) return 1;
    if (n > m) {
        int temp = n;
        n = m;
        m = temp;
    }
    dfs(n, m, new int[n + 1], 0);
    return res;
}

private void dfs(int n, int m, int[] h, int cnt) {
    if (cnt >= res) return;
    boolean isFull = true;
    int pos = -1, minH = Integer.MAX_VALUE;
    for (int i = 1; i <= n; i++) {
        if (h[i] < m) isFull = false;
        if (h[i] < minH) {
            pos = i;
            minH = h[i];
        }
    }
    if (isFull) {
        res = Math.min(cnt, res);
        return;
    }
    
    long key = 0, base = m + 1;
    for (int i = 1; i <= n; i++) {
        key += h[i] * base;
        base *= m + 1;
    }
    if (set.containsKey(key) && set.get(key) <= cnt) return;
    set.put(key, cnt);
    
    int end = pos;
    while (end + 1 <= n && h[end + 1] == h[pos] && (end + 1 - pos + 1 + minH) <= m) end++;
    for (int j = end; j >= pos; j--) {
        int curH = j - pos + 1;
        if (curH + minH > m) break;
        
        int[] next  = Arrays.copyOf(h, n + 1);
        for (int k = pos; k <= j; k++) {
            next[k] += curH;
        }
        dfs(n, m, next, cnt + 1);
    }
}

489. Robot Room Cleaner

int[] dx = {-1,0,1,0};
int[] dy = {0,1,0,-1};
public void cleanRoom(Robot robot){
	dfs(robot, new HashSet<>(), 0, 0, 0); // 0: up, 90: right, 180: down, 270: left
}

public void dfs(Robot robot, Set<String> visited, int x, int y, int curDir){
	String key = x + "@" + y; // current location
	if(visited.contains(key)) return;
	visited.add(key); // not visited, add to hashset
	robot.clean();
	
	for(int i = 0; i < 4; i++){ // go up, right, down, left --> clockwise
		if(robot.move()){
			dfs(robot, visited, x+dx[curDir], y+dy[curDir], curDir);
			backtrack(robot); // back to original position before call dfs!
		}
		
		robot.turnRight();
		curDIr += 1;
		curDir %= 4;
	}
}

public void backtrack(Robot robot){
	robot.turnLeft();
	robot.turnLeft();
	robot.move();
	robot.turnRight();
	robot.turnRight();
}

301. Remove Invalid Parentheses

Still need time to understand this solution
Limit max removal rmL and rmR for backtracking boundary. Otherwise it will exhaust all possible valid substrings, not shortest ones.
Scan from left to right, avoiding invalid strs (on the fly) by checking num of open parens.
If it’s ‘(’, either use it, or remove it.
If it’s ‘(’, either use it, or remove it.
Otherwise just append it.

public List<String> removeInvalidParentheses(String s) {
    int rmL = 0, rmR = 0;
    for (char c: s.toCharArray()) {
        if (c == '(') rmL++;
        else if (c == ')') {
            if (rmL != 0) rmL--;
            else rmR++;
        }
    }
    List<String> res = new ArrayList<>();
    dfs(s, 0, res, "", rmL, rmR, 0, '&');
    return res;
}

public void dfs(String s, int i, List<String> res, String temp, int rmL, int rmR, int open, char lastSkipped) {
    if (rmL < 0 || rmR < 0 || open < 0) return;
    if (i == s.length()) {
        if (rmL == 0 && rmR == 0 && open == 0) res.add(temp);
        return;
    }

    char c = s.charAt(i);

    if (c == '(') {
        if (rmL > 0) dfs(s, i + 1, res, temp, rmL - 1, rmR, open, '('); // not use (
        if (lastSkipped != '(') 
            dfs(s, i + 1, res, temp + c, rmL, rmR, open + 1, '&'); // use (
    } else if (c == ')') {
        if (rmR > 0) dfs(s, i + 1, res, temp, rmL, rmR - 1, open, ')');	// not use  )
        if (open > 0 && (lastSkipped != ')'))
            dfs(s, i + 1, res, temp + c, rmL, rmR, open - 1, '&');  	    // use )
    } else dfs(s, i + 1, res, temp + c, rmL, rmR, open, '&');
}

399. Evaluate Division (G)

Graph+DFS+backtracking
Use directed graph and store value on the edge: $[“a”, “c”] = a -> b -> c = 2.0 * 3.0 = 6.0$

Create a Graph class, with addNode (void), addConnection (return boolean)
Create a Node class, with addConnections
Initialize a Graph object before the real method

• add <src, tgt, val> and <tgt, src, 1/val> to graph
• DFS: check mutiple edge cases, val *= sNode.connections.get(s), visited.add(s)
• return 0 or the final product

class Solution {
    class Graph{
        Map<String, Node> nodes = new HashMap<>();
        void addNode(String key){
            if(nodes.containsKey(key)) return;
            nodes.put(key, new Node(key));
        }
        
        boolean addConnection(String src, String tgt, double val){
            addNode(src);
            nodes.get(src).addConnection(tgt, val);
            return true;
        }
    }
    
    class Node{
        String key;
        Map<String, Double> connections = new HashMap<>();
        public Node(String key){
            this.key = key;
        }
        
        void addConnection(String tgt, double val){
            if(connections.containsKey(tgt)) return;
            connections.put(tgt, val);
        }
    }
        
    Graph graph = new Graph();
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        for(int i=0; i<equations.size(); i++){
            List<String> equation = equations.get(i);
            String src = equation.get(0);
            String tgt = equation.get(1);
            double val = values[i];
            graph.addConnection(src, tgt, val);
            graph.addConnection(tgt, src, 1/val);
        }
        
        double[] ans = new double[queries.size()];
        for(int i=0; i<queries.size(); i++){
            List<String> query = queries.get(i);
            String src = query.get(0);
            String tgt = query.get(1);
            if(graph.nodes.containsKey(src) && 
               graph.nodes.containsKey(tgt)){
                ans[i] = dfs(src, tgt, 1, new HashSet<String>());
            }
            
            if(ans[i] == 0) ans[i] = -1;
            // ans[i] = (res[i] == 0)?-1:ans[i];
        }
        return ans;
    }
        
    private double dfs(String src, String tgt, double val, Set<String> visited){
        if(val == 0) return 0;
        if(src.equals(tgt)) return val;
        Node sNode = graph.nodes.get(src);
        if(sNode == null) return 0;
        for(String s: sNode.connections.keySet()){
            if(visited.contains(s)) continue;
            if(s.equals(tgt)) return val*sNode.connections.get(s);
            val *= sNode.connections.get(s);
            visited.add(s);
            double res = dfs(s, tgt, val, visited);
            if(res != 0) return res;
            visited.remove(s);
            val = val / sNode.connections.get(s);
        }
        return 0;
    }
}

Traversal

102. Binary Tree Level Order Traversal (M)

(DFS?) Similar to LC103, and we do not need to care about the insertion position

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    helper(ans, root, 0);
    return ans;
}

private void helper(List<List<Integer>> ans, TreeNode root, int level){
    if(root == null) return;
    if(ans.size() <= level) ans.add(new ArrayList<>());
    ans.get(level).add(root.val);
    helper(ans, root.left, level+1);
    helper(ans, root.right, level+1);
}

103. Binary Tree Zigzag Level Order Traversal (M)

Use a helper function that takes the level of the node and determines the node should be added to first or last position of the corresponding list

Run time: $O(n)$, space: $O(n)$

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    helper(ans, root, 0);
    return ans;
}

public void helper(List<List<Integer>> ans, TreeNode root, int level){
    if(root == null) return;
    if(ans.size() <= level) ans.add(new ArrayList<>());
    
    if(level % 2 == 0) {
        ans.get(level).add(root.val);
    } else{
        ans.get(level).add(0, root.val);
    }
    helper(ans, root.left, level+1);
    helper(ans, root.right, level+1);
}

106. Construct Binary Tree from Inorder and Postorder Traversal (M)

Add the node backwards in the postorder list into stack, and keep track of the left node in the inorder list

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(inorder.length == 0) return null;
    int j = postorder.length-1;
    Stack<TreeNode> stack = new Stack();
    TreeNode root = new TreeNode(postorder[j--]); // root node
    stack.push(root);
    TreeNode node = null;
    for(int i = inorder.length-1; j >= 0; j--){
        TreeNode cur = new TreeNode(postorder[j]); // right subtree
        while(stack.size() > 0 && stack.peek().val == inorder[i]){
            node = stack.pop();
            i--;
        }
        if(node != null){
            node.left = cur;
            node = null;
        } else{
            stack.peek().right = cur;
        }
        
        stack.push(cur);
    }
    return root;
}

572. Subtree of Another Tree

Use a helper method to check each child node and see if they are the same.

Run time: $O(m+n)$, space: $O(1)$

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    if (isSame(s, t)) return true;
    return isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSame(TreeNode s, TreeNode t) {
    if (s == null && t == null) return true;
    if (s == null || t == null) return false;
    
    if (s.val != t.val) return false;
    
    return isSame(s.left, t.left) && isSame(s.right, t.right);
}

428 . Serialize and Deserialize N-ary Tree

Same idea as a binary tree!

// Encodes a tree to a single string.
    public String serialize(Node root) {
        if (root == null) return "";
         
        Queue<Node> que = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        sb.append(Integer.toString(root.val)).append(",#,");
        que.add(root);
         
        while (!que.isEmpty()) {
            Node node = que.poll();
            for (Node n : node.children) {
                sb.append(Integer.toString(n.val)).append(",");
                que.add(n);
            }
            sb.append("#,");
        }
         
        return sb.toString();
    }
 
    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        if (data.length() == 0) return null;
        String[] s = data.split(",");
 
        Queue<Node> que = new LinkedList<>();
        Node root = new Node(Integer.parseInt(s[0]), new ArrayList<Node>());
        que.add(root);
        int i = 1;
         
        while (!que.isEmpty()) {
            Node node = que.poll();
            i++;
            while (!s[i].equals("#")) {
                Node c = new Node(Integer.parseInt(s[i]), new ArrayList<>());
                node.children.add(c);
                que.add(c);
                i++;
            }
        }
         
        return root;
    }

297. Serialize and Deserialize Binary Tree (M)

Serialize: return current value, and recursively call children
Deserialize: Store in a queue, works life BFS

Run time: $O(n)$, space: $O(n)$

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    if(root == null) return "null";
    return root.val+","+serialize(root.left)+","+serialize(root.right);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
    return helper(queue);
}

TreeNode helper(Queue<String> q){
    String s = q.poll();
    if(s.equals("null")) return null;
    TreeNode root = new TreeNode(Integer.valueOf(s));
    root.left = helper(q);
    root.right = helper(q);
    return root;
}

199. Binary Tree Right Side View

Use helper function, check if the level equals to the size of the list
This way makes sure that only the rightest node will be added to the list
Call right child, then left child

Run time: $O(n)$, space: $O(n)$

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    helper(root, ans, 0);
    return ans;
}

void helper(TreeNode root, List<Integer> ans, int level){
    if(root == null) return;
    if(level == ans.size()) ans.add(root.val);
    helper(root.right, ans, level+1);
    helper(root.left, ans, level+1);
}

Binary Search

1201. Ugly Number III

Calculate how many numbers from 1 to num are divisible by either a, b or c by using the formula:
$(num / a) + (num / b) + (num / c) – (num / lcm(a, b)) – (num / lcm(b, c)) – (num / lcm(a, c)) + (num / lcm(a, b, c))$

Run time: $O(n \log n)$, space: $O(1)$

private long gcd(long a, long b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}

private long lcm(long a, long b) {
    return (a * b) / gcd(a, b);
}

private int count(long a, long b, long c, long num) {
    return (int) ((num / a) + (num / b) + (num / c)
            - (num / lcm(a, b))
            - (num / lcm(b, c))
            - (num / lcm(a, c))
            + (num / lcm(a, lcm(b, c)))); // lcm(a,b,c) = lcm(a,lcm(b,c))
}

public int nthUglyNumber(int n, int a, int b, int c) {
    int low = 1, high = Integer.MAX_VALUE, mid;

    while (low < high) {
        mid = low + (high - low) / 2;

        if (count((a), b, c, mid) < n) low = mid + 1;
        else high = mid;
    }
    return high;
}

Chocolate Sweetness (G)

Relevant post: link

Run time: $O(n \log (sum - min))$, space: $O(1)$

public int splitArray(int[] nums, int m) {
    int low = 0, high = Integer.MAX_VALUE;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canSplit(nums, m, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return high;
    
}

// for a certian min sum requirement, check whether this can split into m groups
private boolean canSplit(int[] nums, int m, int minSum) {
    int count = 0;
    long sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum >= minSum) {
            sum = 0;
            count++;
        }
    }
    return count >= m;
}

Find Median in Large Integer File of Integers (Airbnb)

Relevant link: GitHub repo

// if length is even, return the larger element in array
    public static void main(String []args){
        int[] arr = new int[]{7,6,6,6,6,5,4,4,3,3,2,2,2,22,1};
       System.out.println(findMedian(arr));
    }
    
    public static int findMedian(int[] arr) {
	return helper(arr, Integer.MIN_VALUE, Integer.MAX_VALUE);
   }
   
   private static int helper(int[] arr, int loBound, int hiBound) {
       if (loBound >= hiBound) return loBound;
      
       int mid = (loBound + hiBound) / 2;
       int count = 0;
       int smallerCount = 0;
       for (int a : arr) {
           if(a < mid) smallerCount++;
           if (a <= mid) count++;
       }

       if (smallerCount <= arr.length/2 && count >= arr.length/2) return mid;
       else if (count < arr.length/2) return helper(arr, mid+1, hiBound);
       return helper(arr, loBound, mid);
   }

1011. Capacity To Ship Packages Within D Days (G)

One iteration to find total sum (hi) and maximum package(lo)
While lo is less than hi, find mid and see if the mid capacity could finish. If it is, assign mid to hi, otherwise assign mid+1 to lo.
Helper function basically check if the current capacity would work or not. Use a sum to keep track of the current capacity at day “cnt”.

Run time: $O(\log m)$, space: $O(1)$, where $m$ is total weight-max weight

public int shipWithinDays(int[] weights, int D) {
    int sum = 0;
    int max = 0;
    for (int i = 0; i < weights.length; i++) {
        sum += weights[i];
        max = Math.max(max, weights[i]);
    }
    int lo = max, hi = sum;

    while (lo < hi) {
        int m = lo + (hi - lo) / 2;
        if (satisfy(weights, m, D)) {
            hi = m;
        } else {
            lo = m + 1;
        }
    }
    return lo;
}
public boolean satisfy(int[] weights, int cap, int D) {
    int cnt = 1;
    int sum = 0;
    for (int i = 0; i < weights.length; i++) {
        sum += weights[i];
        if (sum > cap) {
            sum = weights[i];
            cnt++;
        }
    }
    return cnt <= D;
}

Brute force: Check from capacity 1, if not work then increment by 1

public int shipWithinDays(int[] weights, int D) {
    int cap = 1;
    boolean shipAll = false;
    while(!shipAll){
        int day = 0, i = 0, curCap = 0;
        while(day < D && i < weights.length){
            int cur = weights[i];
            if(curCap+cur <= cap) curCap += cur;
            else if (cur <= cap){
                curCap = cur;
                day++;
            }
            else{
                cap++;
                continue;
            }
            // System.out.println(cap+" day:"+day+" "+curCap);
            i++;
        }
        if(day >= D) cap++;
        else if(i == weights.length){
            if(day <= D) shipAll = true;
            else cap++;
        }
    }
    return cap;
}

Airbnb OA - Halloween Candy

private static int getMinDandies(int[] nums, int hours) {
	int r = 0;
	for(int n : nums)
		r = Math.max(r, n);
	int l = 1;
	while(l < r) {
		int m = l + (r - l)/2;
		if(canFinish(nums, hours, m)) {
			r = m;
		}else {
			l = m+1;
		}
	}
	return l;
}

static boolean canFinish(int[] nums, int hours, int m){
	int res = 0;
	for(int n : nums) {
		res += n/m;
		if(n%m > 0) res++;
	}
	return res <= hours;
}

153. Find Minimum in Rotated Sorted Array (M)

Trick: check left < right-1 in the while loop
if a[mid] > a[right], go right; if a[mid] < a[right], go left.

Run time: $O(\log n)$, space: $O(1)$

public int findMin(int[] nums) {
    if (nums == null || nums.length == 0) return Integer.MIN_VALUE;
    int left = 0, right = nums.length-1;
    while (left < right-1) {  // while (left < right-1) is a useful technique
        int mid = left + (right-left)/2;
        if (nums[mid] > nums[right]) left = mid;
        else right = mid;
    }
    if (nums[left] > nums[right]) return nums[right];
    return nums[left];
}

278. First Bad Version

Binary search on the number of version from 1 to n, return hi index

Run time: $O(\log n)$, space: $O(1)$

public int firstBadVersion(int n) {
    return helper(1, n);
}
private int helper(int lo, int hi){
    while(lo < hi){
        int md = lo+(hi-lo)/2;
        if(isBadVersion(md)) hi = md;
        else lo = md + 1;
    }
    return hi;
}

34. Find First and Last Position of Element in Sorted Array (FB FT, failed in 2019)

Use binary search with a helper function
It first compares the end points and immediately returns [lo, hi] if that whole part of nums is full of target, and immediately returns [-1, -1] if target is outside the range. The interesting case is when target can be in the range but doesn’t fill it completely.

Run time: $O(\log n)$, space: $O(1)$

public int[] searchRange(int[] nums, int target) {
	if(nums == null || nums.length == 0) return new int[]{-1,-1};
	return helper(nums, target, 0, nums.length-1);
}

private int[] helper(int[] nums, int target, int lo, int hi) {
	if(nums[lo] == target && nums[hi] == target) return new int[]{-1,-1};
	if(nums[lo] <= target && nums[hi] >= target){
		int mid = lo + (lo+hi)/2;
		int[] left = helper(nums, target, lo, mid);
		int[] right = helper(nums, target, mid+1, hi);
		if(left[0] == -1) return right;
		if(right[0] == -1) return left;
		return new int[]{left[0], right[1]};
	}
	return new int[]{-1,-1};
}

315. Count of Smaller Numbers After Self (G)

Binary Indexed Tree
Run time: $O()$, space: $O(n)$

private class BIT {
    int[] bit;
    public BIT(int size) {
        bit = new int[size + 1];
    }
    public void increase(int i, int diff) {
        while (i < bit.length) {
            ++bit[i];
            i += (i & -i);
        }
    }
    public int query(int i) {
        int count = 0;
        while (i > 0) {
            count += bit[i];
            i -= (i & -i);
        }
        return count;
    }
}
public List<Integer> countSmaller(int[] nums) {
    List<Integer> list = new LinkedList<>();
    if (nums == null || nums.length == 0) return list;
    int n = nums.length;
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    for (int i : nums) {
        max = Math.max(max, i);
        min = Math.min(min, i);
    }
    BIT bit = new BIT(max - min + 1);
    for (int i = n - 1; i >= 0; --i) {
        list.add(0, bit.query(nums[i] - min));
        bit.increase(nums[i] - min + 1, 1);
    }
    return list;
}

One efficient way: binary search only
Build a ordered list and perform binary search on it, return the left index
Run time: $O(n^2)$ (worst case), space: $O(n)$

public List<Integer> countSmaller(int[] nums) {
    List<Integer> list = new ArrayList<>();
    LinkedList<Integer> res = new LinkedList<>();
    for (int i = nums.length-1; i >= 0; i--){
        res.addFirst(search(0, list.size()-1, list, nums[i]));
        insert(list, nums[i]);
    }
    return res;
}

private int search(int l, int r, List<Integer> list, int target){
    if(l > r) return l;
    int m = (l+r)/2;
    if(list.get(m) < target) return search(m+1, r, list, target);
    else return search(l, m-1, list, target);
}

private void insert(List<Integer> list, int num){
    int id = 0;
    while(id < list.size() && list.get(id) < num) id++;
    list.add(id, num);
}

Slowest & brute force way: directly count
Run time: $O(n^2)$, space: $O(n)$

4. Median of Two Sorted Arrays

Find the average of two medians, no need to consider whether the sum of length is odd or not
If out of range, then return the other one
if size is one, return the smaller one
Update the median by updating index+k/2-1
Run time: $O(\log(m+n))$, space: $O(1)$

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int l = (m + n + 1) / 2;
    int r = (m + n + 2) / 2;
    return (getkth(nums1, 0, nums2, 0, l) + getkth(nums1, 0, nums2, 0, r)) / 2.0;
}

public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
    if (aStart > A.length - 1) return B[bStart + k - 1];            
    if (bStart > B.length - 1) return A[aStart + k - 1];                
    if (k == 1) return Math.min(A[aStart], B[bStart]); // size one for each array

    int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE; // new median
    if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
    if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];        

    if (aMid < bMid) 
        return getkth(A, aStart + k/2, B, bStart,       k - k/2); // Check: aRight + bLeft 
    else 
        return getkth(A, aStart,       B, bStart + k/2, k - k/2); // Check: bRight + aLeft
}

Topological Sort

210. Course Schedule II (M)

Use an array to count the number of courses that need this class as a prerequisite
Use an array of list to store the exact courses that need this class as a prerequisite
Then use a queue to get the current course that does not need any prerequisite, update the other courses and push to the queue

Run time: $O(n)$, space: $O(n)$

public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] result = new int[numCourses];
    int[] numPreq = new int[numCourses];
    ArrayList<Integer>[] graph = new ArrayList[numCourses];
    Queue<Integer> queue = new LinkedList<>();
    int ptr = 0;
    for(int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
    for(int[] pre: prerequisites){
        graph[pre[1]].add(pre[0]);
        numPreq[pre[0]]++;
    }
    for(int i = 0; i < numCourses; i++){
        if(numPreq[i] == 0) queue.add(i);
    }
    while(!queue.isEmpty()){
        int cur = queue.poll();
        result[ptr++] = cur;
        for(int rest: graph[cur]){
            numPreq[rest]--;
            if(numPreq[rest] == 0) queue.add(rest);
        }
    }
    if(ptr != numCourses) return new int[0];
    return result;
}

269. Alien Dictionary

1. Get all characters used in the dictionary, which will be nodes. But this dictionary will also be used in the traverse.

2. Extract edges from the input. Just find the same prefix and use the first different character.
3. Perform Topological sort.

Run time: $O(n)$, space: $O(n)$

public String alienOrder(String[] words) {
	Map<Character, Set<Character>> graph = new HashMap<>();
	int[] degree = new int[26];
	
	buildGraph(word, graph, degree);
	
	String order = topologicalSort(graph, degree);
        	return order.length() == graph.size() ? order : "";
}

public void buildGraph(String[] word, Map<Character, Set<Character>> graph, int[] degree){
	for (String word : words) { // put every showed alphabet into the graph
         	for (char c : word.toCharArray()) graph.put(c, new HashSet<>());
        }
	
	for (int i = 1; i < words.length; i++) {
            	String first = words[i - 1]; // previous word
            	String second = words[i]; // current word
            	int length = Math.min(first.length(), second.length());
            
            	for (int j = 0; j < length; j++) {
                		 char parent = first.charAt(j);
                		 char child = second.charAt(j);
                		if (parent != child) {
                    		if (!graph.get(parent).contains(child)) { // add child to the parent set
                        			graph.get(parent).add(child);
                        			inDegree[child - 'a']++;
                    		}
                    		break;
               		 }
            	}
        }
}

private String topologicalSort(Map<Character, Set<Character>> graph, int[] inDegree) {
        Queue<Character> queue = new LinkedList<>();
        for (char c : graph.keySet()) {
            	if (inDegree[c - 'a'] == 0) queue.offer(c);
        }
        
        	StringBuilder sb = new StringBuilder();
        	while (!queue.isEmpty()) {
            	char c = queue.poll();
            	sb.append(c);
            	for (char neighbor : graph.get(c)) {
                		inDegree[neighbor - 'a']--;
                		if (inDegree[neighbor - 'a'] == 0) {
                    		queue.offer(neighbor);
                		}
            	}
        	}
        	return sb.toString();
}

Recursion

---

206. Reverse Linked List (M)

Recursive

public ListNode reverseList(ListNode head) {
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null) return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
}

Iterative

public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

236. Lowest Common Ancestor of a Binary Tree

If the root is null, or it equals either p or q, we should return it, since that satisfies LCA
Get the left LCA and right LCA, if either of them is null, which means the two nodes are on one side of the (sub)tree. Otherwise, we should just return the root.

Run time: $O(n)$, space: $O(1)$

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    if(left == null) return right;
    if(right == null) return left;
    return root;
}

112. Path Sum (M)

If node is null, return false
If current node is leaf (no left/right child), check if the value equals to the remaining sum
Return the left path or the right path that may contain the sum

Run time: $O(n)$, space: $O(1)$

public boolean hasPathSum(TreeNode root, int sum) {
    if(root == null) return false;

    if(root.left == null && root.right == null) return sum == root.val;

    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

104. Maximum Depth of Binary Tree

Call the function recursively

public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}

235. Lowest Common Ancestor of a Binary Search Tree

Recursive way

Run time: $O(n)$, space: $O(1)$

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) return null;
    if(root == p || root == q) return root;
    if((root.val > p.val && root.val < q.val) ||
       (root.val > q.val && root.val < p.val)) return root;
    if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    return lowestCommonAncestor(root.right, p, q);
}

Iterative way

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while(root != null) {
        if(root.val > p.val && root.val > q.val)
            root = root.left;
        else if ( root.val < p.val && root.val < q.val)
            root = root.right;
        else
            return root;
    }   
    return root;
}

101. Symmetric Tree (M)

Recursive way

Run time: $O(n)$, space: $O(1)$

public boolean isSymmetric(TreeNode root) { // recursive
    if(root == null) return true;
    return isMirror(root.left,root.right);
}
public boolean isMirror(TreeNode p, TreeNode q) {
    if(p==null && q==null) return true;
    if(p==null || q==null) return false;
    return (p.val == q.val) && isMirror(p.left,q.right) && isMirror(p.right,q.left);
}

Iterative way

Run time: $O(n)$, space: $O(n)$

public boolean isSymmetric(TreeNode root) { // iterative
    if (root == null) return true;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root.left);
    stack.push(root.right);
    while (!stack.empty()) {
        TreeNode n1 = stack.pop(), n2 = stack.pop();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null || n1.val != n2.val) return false;
        stack.push(n1.left);
        stack.push(n2.right);
        stack.push(n1.right);
        stack.push(n2.left);
    }
    return true;
}

124. Binary Tree Maximum Path Sum

Helper method finds the left max and right max, then update the total max, and return the sum of root value with either left or right sum
Notice: The reference variable int[] is in MA, the address is copied (and passed as value), and the initial variable will be changed.

Run time: $O(n)$, space: $O(1)$

public int maxPathSum(TreeNode root) {
    int[] max = new int[1];
    max[0] = Integer.MIN_VALUE;
    maxPathSum(max, root);
    return max[0];
}
private int maxPathSum(int[] max, TreeNode root){
    if(root == null) return 0;
    int leftMax =  Math.max(0, maxPathSum(max, root.left));
    int rightMax = Math.max(0, maxPathSum(max, root.right));
    max[0] = Math.max(max[0],  root.val+leftMax+rightMax);
    return root.val+Math.max(leftMax,rightMax);
}

394. Decode String

Recursion: if meet a number, update count c = 10*c +c-‘0’
If meet a open bracket, use two variable to count num of open and close brackets in a while loop, until index reaches the end or the brackets is balance
Call recursion! Append the result
Other cases, just append the char

Run time: $O(n)$, space: $O(1)$

public String decodeString(String s) {
    StringBuilder sb = new StringBuilder();
    int count = 0;
    for (int i = 0; i <s.length();i++) {
        char c = s.charAt(i);
        if (c <= '9' && c >= '0') {
            System.out.println("prev: "+count);
            count = count * 10 + c -'0'; // the number can be more than one digit!
            System.out.println(count);
        } else if (c == '[') {
            int j = i+1;
            int open = 1, close = 0;
            i++;
            while (i < s.length() && open != close) {
                if (s.charAt(i) == '[') open++;
                else if (s.charAt(i) == ']') close++;
                i++;
            }
            String sub = decodeString(s.substring(j,--i));
            for (int f = 0; f < count;f++) {
                sb.append(sub);
            }
            count = 0;
        } else {
            sb.append(c);
        }
    }
    
    return sb.toString();
}

Usual way: use a stack to keep all chars, once meet a close bracket, pop chars from stack until see a open bracket and number

247. Strobogrammatic Number II

Recursion; start from length 0 and 1, then add pairs to the left and right of the current number
Run time: $O(n!)$, space: $O(n!)$

public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    public List<String> helper(int targetLen, int totalLen) {
        if (targetLen == 0) {
            return new ArrayList(Arrays.asList(""));
        }
        if (targetLen == 1) {
            return new ArrayList(Arrays.asList("1", "8", "0"));
        }
        List<String> sub = helper(targetLen - 2, totalLen); // start from center
        List<String> result = new ArrayList<>();
        for (String str : sub) {
            if (targetLen != totalLen) { // avoid last round adding 0
                result.add("0" + str + "0");
            }
            result.add("1" + str + "1");
            result.add("6" + str + "9");
            result.add("9" + str + "6");
            result.add("8" + str + "8");
        }
        return result;
    }

Iterative: check if length is even or odd
Run time: $O(n!)$, space: $O(n!)$

public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        if (n % 2 == 0) {
            result.add(""); // middle element
        }
        else {
            result.add("1");
            result.add("8");
            result.add("0");
        }
        while (n >= 2) {
            List<String> tmp = result; // use current list to build new ones
            result = new ArrayList<String>();
            for (String str : tmp) {
                if (n > 3) { // have to add outer number after adding 0
                    result.add("0" + str + "0");
                }
                result.add("1" + str + "1");
                result.add("8" + str + "8");
                result.add("6" + str + "9");
                result.add("9" + str + "6");
            }
            n -= 2;
        }
        return result;
    }
}

222. Count Complete Tree Nodes

First way: recursive, $O(n)$

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    else return 1 + countNodes(root.left) + countNodes(root.right);
}

Second way: $O((log(n))^2) $

public int countNodes(TreeNode root) {
    if (root == null) return 0;

    int leftHeight = leftHeight(root);
    int rightHeight = rightHeight(root);

    /**
     * case 1: When Height(Left sub-tree) = Height(right sub-tree)
     * 2^h - 1
     */
    if (leftHeight == rightHeight) return (1 << leftHeight) - 1;
    else return 1 + countNodes(root.left) + countNodes(root.right);
}


private int leftHeight(TreeNode root) {
    if (root == null) return 0;
    return 1 + leftHeight(root.left);
}

private int rightHeight(TreeNode root) {
    if (root == null) return 0;
    return 1 + rightHeight(root.right);
}

Permutation

31. Next Permutation

i records the starting index that breaks descending, -1 if the whole array is descending
i starts from the second to last index. After while loop, if i is non-negative, find the rightmost first larger id j, and swap i and j
Reverse the array from index i+1 to the last index

Run time: $O(n)$, space: $O(1)$

public void nextPermutation(int[] nums) {
    if(nums == null || nums.length <= 1) return;
    int i = nums.length - 2;
    while(i >= 0 && nums[i] >= nums[i + 1]) i--; // Find 1st id i that breaks descending order
    if(i >= 0) {                           // If not entirely descending
        int j = nums.length - 1;              // Start from the end
        while(nums[j] <= nums[i]) j--;           // Find rightmost first larger id j
        swap(nums, i, j);                     // Switch i and j
    }
    reverse(nums, i + 1, nums.length - 1);       // Reverse the descending sequence
}

public void swap(int[] A, int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

public void reverse(int[] A, int i, int j) {
    while(i < j) swap(A, i++, j--);
}

1220. Count Vowels Permutation

Keep track of the order of alphabets that could be added to the current string, since based on the rule one must be followed by some others, so we accumulate combinations that ends with a particular letter.

Run time: $O(n)$, space: $O(1)$

public int countVowelPermutation(int n) {
  int[][] moves = { {1}, {0, 2}, {0, 1, 3, 4}, {2, 4}, { 0 } };
  int[] v = { 1, 1, 1, 1, 1 };
  while (--n > 0) {
    int[] v1 = { 0, 0, 0, 0, 0 };
    for (int i = 0; i < 5; i++) {
      for (int j : moves[i]){
            v1[j] = (v1[j] + v[i]) % 1000000007;
          // System.out.println(j+" "+v1[j]);
      }
    }
    v = v1;
  }
  return (int)(((long)v[0] + v[1] + v[2] + v[3] + v[4]) % 1000000007);
}

Maps

---

1124. Longest Well-Performing Interval

Use a map to put <num of balanced performing days ended at i, i>. If today is greater than 8, increment the score by 1, otherwise decrement it by 1.
If the score is positive, which means there’s more tiring days, just update the answer since it should be the maximum now. Otherwise, put the pair <current score, i> into the map if this key does not exist yet. If the map contains the key score-1, which is the balanced days less the last not-tiring day, update the answer if i-seen.get(score-1) is greater.

Run time: $O(n)$, space: $O(n)$

public int longestWPI(int[] hours) {
    int res = 0, score = 0, n = hours.length;
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < n; i++) {
        if(hours[i] > 8) score++;
        else score--;
        if (score > 0) {
            res = i + 1;
        } else {
            seen.putIfAbsent(score, i);
            if (seen.containsKey(score-1))
                res = Math.max(res, i - seen.get(score-1));
        }
    }
    return res;
}

588. Design In-Memory File System (Nordstrom FT, failed in 2019)

Relevant link with problem description
Use TreeMap to contain children nodes - so they are sorted.

private class TreeNode implements Comparable<TreeNode> {
    String label;
    boolean isDir;
    Map<String, TreeNode> dirContents = new TreeMap<>();
    String fileContents;
    
    public int compareTo(TreeNode other) {
        return label.compareTo(other.label);
    }
    
    public int hashCode() {
        return Objects.hash(label);
    }
    
    public boolean equals(Object treeNode) {
        TreeNode other = (TreeNode) treeNode;
        return Objects.equals(label, other.label);
    }
}    

private Tre     
public List<String> ls(String path) {
    String[] labels = path.split("/");
    TreeNode curr = (labels.length != 0) ? sentinel : sentinel.dirContents.get("");
    List<String> result = new ArrayList<>();
    for(String label : labels) {
        curr = curr.dirContents.get(label);
        System.out.println(">>" + curr);
    }
    if(curr.isDir) {
        for(String label : curr.dirContents.keySet()) {
            result.add(label);
        }
    } else {
        result.add(curr.label);
    }
    return result;
}

public void mkdir(String path) {
    String[] labels = path.split("/");
    TreeNode curr = sentinel;
    int currIndex = 0;
    for(String label : labels) {
        TreeNode next = curr.dirContents.get(label);
        if(next == null) {
            break;
        }
        currIndex++;
        curr = next;
    }
    
    for(int i = currIndex; i < labels.length; i++) {
        TreeNode newDir = new TreeNode();
        newDir.isDir = true;
        newDir.label = labels[i];
        curr.dirContents.put(labels[i], newDir);
        
        curr = newDir;
    }
}

public void addContentToFile(String filePath, String content) {
    String[] labels = filePath.split("/");
    TreeNode curr = sentinel, prev = null;
    
    for(String label : labels) {
        prev = curr;
        if(curr == null) {
            break;
        }
        curr = curr.dirContents.get(label);
    }
    
    if(curr == null) {
        curr = new TreeNode();
        curr.isDir = false;
        curr.label = labels[labels.length - 1];
        curr.fileContents = content;
        prev.dirContents.put(curr.label, curr);
    }
    else {
        curr.fileContents = curr.fileContents == null ? content : curr.fileContents + content;
    }
}

public String readContentFromFile(String filePath) {
    String[] labels = filePath.split("/");
    TreeNode curr = sentinel;
    
    for(String label : labels) {
        curr = curr.dirContents.get(label);
    }
    return (curr.fileContents == null) ? "" : curr.fileContents;
}

Second way: Create a File class and each of them has a map containing file name and File

class File {
    boolean isFile = false;
    Map<String, File> children = new HashMap<>();
    String content = "";
}

File root = null;

public FileSystem() {
    root = new File();
}

public List<String> ls(String path) {
    String[] dirs = path.split("/");
    File node = root;
    List<String> result = new ArrayList<>();
    String name = "";
    for (String dir : dirs) {
        if (dir.length() == 0) continue;
        if (!node.children.containsKey(dir)) {
            return result;
        }
        node = node.children.get(dir);
        name = dir;
    }
    
    if (node.isFile) {
        result.add(name);
    }
    else {
        for (String key : node.children.keySet()) {
            result.add(key);
        }
    }
    
    Collections.sort(result);
    
    return result;
}

public void mkdir(String path) {
    String[] dirs = path.split("/");
    File node = root;
    for (String dir : dirs) {
        if (dir.length() == 0) continue;
        if (!node.children.containsKey(dir)) {
            File file = new File();
            node.children.put(dir, file);
        }
        node = node.children.get(dir);
    }
}

public void addContentToFile(String filePath, String content) {
    String[] dirs = filePath.split("/");
    File node = root;
    for (String dir : dirs) {
        if (dir.length() == 0) continue;
        if (!node.children.containsKey(dir)) {
            File file = new File();
            node.children.put(dir, file);
        }
        node = node.children.get(dir);
    }
    node.isFile = true;
    node.content += content;
}

public String readContentFromFile(String filePath) {
    String[] dirs = filePath.split("/");
    File node = root;
    for (String dir : dirs) {
        if (dir.length() == 0) continue;
        if (!node.children.containsKey(dir)) {
            File file = new File();
            node.children.put(dir, file);
        }
        node = node.children.get(dir);
    }

    return node.content;
}

535. Encode and Decode TinyURL (M)

Use a map to store the decoded url and the original url, then use another map to store the reversed pair for duplication check

public class Codec {
    Map<String, String> index = new HashMap<String, String>();
    Map<String, String> revIndex = new HashMap<String, String>();
    static String BASE_HOST = "http://tinyurl.com/";
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (revIndex.containsKey(longUrl)) return BASE_HOST + revIndex.get(longUrl);
        String charSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        String key = null;
        
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++) {
                int r = (int) (Math.random() * charSet.length());
                sb.append(charSet.charAt(r));
            }
            key = sb.toString();
        } while (index.containsKey(key));
        index.put(key, longUrl);
        revIndex.put(longUrl, key);
        return BASE_HOST + key;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return index.get(shortUrl.replace(BASE_HOST, ""));
    }
}

1153. String Transforms Into Another String (G)

Use a map to store <char from str1, char from str2>, and a set to store char from str2
For each index, put char from str2 into the set, and check if the corresponding map is consistent (return false if not), put the key-value pair if not exist
After the loop, if two strings are not equal and both of them have used all 26 characters, which implies there is no potential transformation, return false

Runtime: $O(n)$, space: $O(n)$

public boolean canConvert(String str1, String str2){
    Set<Character> set = new HashSet<>();
    Map<Character, Character> map = new HashMap<>();
    for(int i = 0; i < str1.length(); i++){
        char c1 = str1.charAt(i), c2 = str2.charAt(i);
       set.add(c2);
       if(map.containsKey(c1) && map.get(c1) != c2) 
           return false;
       map.put(c1, c2);
    }
    if(!str1.equals(str2) && map.size() == 26 && set.size() == 26) 
       return false; // both of strs have used all characters
   return true;
}

676. Implement Magic Dictionary (G)

For each word in dictionary, remove the char and put the rest of the word as key (e.g. “ello", "hllo”, “helo", "helo”, “hell*”), the removed char as the value. If the modified string exists, set the value as 0.
When we search a word, we try to remove different char and see if the map contains this key, and the removed char is different.

class MagicDictionary {
    Map<String, Character> map;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        map = new HashMap<>();
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for(String s: dict){
            for(int i = 0; i < s.length(); i++){
                String temp = s.substring(0, i)+"*"+s.substring(i+1);
                
                if(!map.containsKey(temp)) map.put(temp, s.charAt(i));
                else if(map.get(temp) != s.charAt(i)) map.put(temp, '0');
            }
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    public boolean search(String word) {
        for (int i = 0; i < word.length(); i++) {
            String temp = word.substring(0, i)+"*"+word.substring(i+1);
            if (map.containsKey(temp) && map.get(temp) != word.charAt(i))
                return true;
        }
        return false;
    }
}

911. Online Election (G)

Use TreeMap

Time complexity for constructor TopVotedCandidate(int[] persons, int[] times) is O(nlogn), and for q(int t) is O(logn).

class TopVotedCandidate {
    private TreeMap<Integer, Integer> tm = new TreeMap<>(); // time and leading candidate
    public TopVotedCandidate(int[] persons, int[] times) {
        int[] count = new int[persons.length]; // count[i]: count of votes for persons[i].
        for (int i = 0, max = -1; i < times.length; ++i) {
            ++count[persons[i]]; // at times[i], persons[i] got a vote.
            if (max <= count[persons[i]]) { // is persons[i] leading?
                max = count[persons[i]]; // update leading count.
                tm.put(times[i], persons[i]); // update leading candidate.
            }
        }
    }
    public int q(int t) {
        return tm.floorEntry(t).getValue(); // fetch the corresponding information. 
    }
}

Binary Search

Runtime: Constructor $O(n)$, q(int t) is $O(logn)$

class TopVotedCandidate {
    private Map<Integer, Integer> map = new HashMap<>(); // time and leading candidate
    private int[] times;
    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        int[] count = new int[persons.length + 1]; // count[i]: count of votes for persons[i].
        for (int i = 0, winner = -1; i < times.length; ++i) {
            ++count[persons[i]]; // at times[i], persons[i] got a vote.
            // is persons[i] leading? update winner.
            if (map.isEmpty() || count[winner] <= count[persons[i]]) { winner = persons[i]; } 
            map.put(times[i], winner); // update time and winner.
        }
    }
    public int q(int t) {
        int idx = Arrays.binarySearch(times, t); // search for the time slot.
        return map.get(times[idx < 0 ? -idx - 2 : idx]); // fetch the corresponding information.
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */

1146. Snapshot Array (G)

Use a list of map to store different versions of snapshots.
Use a map to store the index and value when method set is called.
Add the map to list when snap is called, reset the map, and return the last index in list

Run time: $O(n)$, space: $O(n)$

class SnapshotArray {
    private List<Map<Integer, Integer>> shot;
    private Map<Integer, Integer> diff;
    
    public SnapshotArray(int length) {
        shot  = new ArrayList<>(length);
        diff  = new HashMap<>(length);
    }
    
    public void set(int index, int val) {
        diff.put(index, val);
    }
    
    public int snap() {
        shot.add(diff);
        diff = new HashMap<>();
        return shot.size() - 1;
    }
    
    public int get(int index, int snap_id) {
        for (int i = snap_id; i >= 0; --i)
             if (shot.get(i).containsKey(index))   
                 return shot.get(i).get(index); 
        return 0;
    }
}

Use a map to store <current id+index, corresponding value>
Each time only search the id+index and return the value if exist

class SnapshotArray {
    int snapId = 0;
    Map<String, Integer> map;
    public SnapshotArray(int length) {
        map = new HashMap<>();
    }
    
    public void set(int index, int val) {
        String cur = snapId + "," + index;
        map.put(cur, val);
    }
    
    public int snap() {       
        return snapId++;
    }
    
    public int get(int index, int snap_id) {
        while (snap_id >= 0) {
            String temp = snap_id-- + "," + index;
            if (map.containsKey(temp)) {
                return map.get(temp);
            } 
        } 
        return 0;
    }
}

1244. Design A Leaderboard

1.Use HashMap to record the people’s score
2.Use TreeMap to find the topK in O(klogn) by traverse the treemap
3.Reset we can just remove the key from the treemap which is O(log n), same for addScore().

class Leaderboard {
    Map<Integer, Integer> map;
    TreeMap<Integer, Integer> sorted;
    public Leaderboard() {
        map = new HashMap<>();
        sorted = new TreeMap<>(Collections.reverseOrder());
    }
    
    public void addScore(int playerId, int score) {
        if (!map.containsKey(playerId)) {
            map.put(playerId, score);
            sorted.put(score, sorted.getOrDefault(score, 0) + 1);
        } else {
            int preScore = map.get(playerId);
            sorted.put(preScore, sorted.get(preScore) - 1);
            if (sorted.get(preScore) == 0) {
                sorted.remove(preScore);
            }
            int newScore = preScore + score;
            map.put(playerId, newScore);
            sorted.put(newScore, sorted.getOrDefault(newScore, 0) + 1);
        }
    }
    
    public int top(int K) {
        int count = 0;
        int sum = 0;
        for (int key : sorted.keySet()) {
            int times = sorted.get(key);
            for (int i = 0; i < times; i++) {
                sum += key;
                count++;
                if (count == K) break;
            }
            if (count == K) break;
        }
        return sum;
    }
    
    public void reset(int playerId) {
        int preScore = map.get(playerId);
        sorted.put(preScore, sorted.get(preScore) - 1);
        if (sorted.get(preScore) == 0) {
            sorted.remove(preScore);
        }
        map.remove(playerId);
    }
}

My way: HashMap to store <playerId, score>, priority queue to store the score in decreasing order

class Leaderboard {
    Map<Integer, Integer> map;
    PriorityQueue<Integer> pq;
    public Leaderboard() {
        map = new HashMap<>();
        pq = new PriorityQueue(Collections.reverseOrder());
    }
    
    public void addScore(int playerId, int score) {
        
        if(map.containsKey(playerId)) {
            int prev = map.get(playerId);
            reset(playerId);
            map.put(playerId, score+prev);
            pq.add(score+prev);
        }
        else {
            map.put(playerId, score);
            pq.add(score);
        }
    }
    
    public int top(int K) {
        if(K > pq.size()) return -1;
        int sum = 0;
        Object[] a = pq.toArray();
        Integer[] temp = Arrays.copyOf(a, a.length, Integer[].class);
        Arrays.sort(temp, Collections.reverseOrder());
        int i = 0;
        while(K > 0) {
            sum += temp[i++];
            K--;
        }
        return sum;
    }
    
    public void reset(int playerId) {
        if(map.containsKey(playerId)) {
            pq.remove(map.get(playerId));
            map.remove(playerId);
        }
    }
}

/**
 * Your Leaderboard object will be instantiated and called as such:
 * Leaderboard obj = new Leaderboard();
 * obj.addScore(playerId,score);
 * int param_2 = obj.top(K);
 * obj.reset(playerId);
 */

205. Isomorphic Strings (G)

Use a HashMap to store the conversion between two characters

Run time: $O(n)$, space: $O(n)$

public boolean isIsomorphic(String s, String t) {
    if(s == null) return true;
    HashMap<Character, Character> map = new HashMap<Character, Character>();
    for(int i = 0 ; i< s.length(); i++){
        char a = s.charAt(i), b = t.charAt(i);
        if(map.containsKey(a)){
             if(map.get(a).equals(b)) continue;
            else return false;
        }else{
            if(!map.containsValue(b)) map.put(a,b);
            else return false;
        }
    }
    return true;
}

1. Two Sum

Put <value, index> into the map, each time find if the target is in the map. If there is, get the index and put it in the first entry, with the current index in the second entry.

Run time: $O(n)$, space: $O(n)$

public int[] twoSum(int[] nums, int target) {
    if(nums == null || nums.length < 2) return new int[]{-1,-1};
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int n = nums[i];
        int diff = target - n;
        if(map.containsKey(diff)) return new int[]{map.get(diff), i};
        map.put(n, i);
    }
    return new int[]{-1,-1};
}

621. Task Scheduler

Put <taskName, frequencies> into the map, update the max
Calculate the count using (max-1)*(cooldown+1)

Run time: $O(n)$, space: $O(n)$

public int leastInterval(char[] tasks, int cooldown) {
    HashMap<Character, Integer> map = new HashMap<>();
    int max = 0;
    int n = tasks.length;
    for (char c : tasks) {
        if(!map.containsKey(c)) map.put(c, 0);
        map.put(c, map.get(c) + 1);
        max = Math.max(max, map.get(c));
    }
    int count = (max-1) * (cooldown + 1);
    int extra = 0;
    for(int val : map.values()){
        if(val > max - 1) extra++;
    }
    return Math.max(count + extra, n);
}

Simplified question: the order is given and fixed

public int processTasks(int[] orderList, int cooldown) {
// key is the task Id, value is the recently time it should be put
   Map<Integer, Integer> map = new HashMap<>();
   int time = 0;
   for (int id : orderList) {
     if (map.containsKey(id)) {
       time = Math.max(map.get(id) + cooldown + 1, time);
     }
     map.put(id, time++);
   }
   return time;
}

347. Top K Frequent Elements

Use a hashmap (number, occurences) and an array of interger lists (index is occurences, store list of elements in the original array). Loop backwards to add all integers to the answer.

Run time: $O(n)$, space: $O(n)$

public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer>[] bucket = new List[nums.length+1];
    Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

    for (int n : nums) frequencyMap.put(n, frequencyMap.getOrDefault(n, 0)+1);
    for (int key: frequencyMap.keySet()) {
        int frequency = frequencyMap.get(key);
        if (bucket[frequency] == null) bucket[frequency] = new ArrayList<>();
        bucket[frequency].add(key);
    }
    List<Integer> ans = new ArrayList<>();
    for (int pos = bucket.length - 1; pos >= 0 && ans.size() < k; pos--) {
        if (bucket[pos] != null) ans.addAll(bucket[pos]);
    }
    return ans;
}

218. The Skyline Problem

Create a list and put [left, -height] and [right, height]
Sort the intervals by left, then right, in increasing order
Create a TreeMap and keep the keys in decreasing order
For each value in the list, see if the height is in the map. If it’s left pair, then increment the occurrences. If it’s right pair, then decrement the occurrences or remove it
Then get the first key (max one) from the treemap, and if this height is different from the previous height, add it to the result list.

public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> heights = new ArrayList<>();
    for (int[] b: buildings) {
        heights.add(new int[]{b[0], -b[2]});
        heights.add(new int[]{b[1], b[2]});
    }
    Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
    TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
    heightMap.put(0,1);
    int prevHeight = 0;
    List<List<Integer>> skyLine = new LinkedList<>();
    for (int[] h: heights) {
        if (h[1] < 0) {
            Integer cnt = heightMap.get(-h[1]);
            cnt = ( cnt == null ) ? 1 : cnt + 1;
            heightMap.put(-h[1], cnt);
        } else {
            Integer cnt = heightMap.get(h[1]);
            if (cnt == 1) {
                heightMap.remove(h[1]);
            } else {
                heightMap.put(h[1], cnt - 1);
            }
        }
        int currHeight = heightMap.firstKey();
        if (prevHeight != currHeight) {
            skyLine.add(Arrays.asList(h[0], currHeight));
            prevHeight = currHeight;
        }
    }
    return skyLine;
}

460. LFU Cache (G)

Store the following entries: <key, value>, <key, freq>, <freq, list of keys>.
Use LinkedHashSet to record list of keys in insertion order

Run time: $O(n\log n)$, space: $O(n)$

class LFUCache {
    HashMap<Integer, Integer> vals;
    HashMap<Integer, Integer> counts;
    HashMap<Integer, LinkedHashSet<Integer>> lists; // count, 
    int cap;
    int min = -1;
    public LFUCache(int capacity) {
        cap = capacity;
        vals = new HashMap<>();
        counts = new HashMap<>();
        lists = new HashMap<>();
        lists.put(1, new LinkedHashSet<>());
    }
    
    public int get(int key) {
        if(!vals.containsKey(key))
            return -1;
        int count = counts.get(key);
        counts.put(key, count+1);
        lists.get(count).remove(key);
        if(count==min && lists.get(count).size()==0)
            min++;
        if(!lists.containsKey(count+1))
            lists.put(count+1, new LinkedHashSet<>());
        lists.get(count+1).add(key);
        return vals.get(key);
    }
    
    public void put(int key, int value) {
        if(cap<=0)
            return;
        if(vals.containsKey(key)) {
            vals.put(key, value);
            get(key);
            return;
        } 
        if(vals.size() >= cap) {
            int evit = lists.get(min).iterator().next();
            lists.get(min).remove(evit);
            vals.remove(evit);
            counts.remove(evit);
        }
        vals.put(key, value);
        counts.put(key, 1);
        min = 1;
        lists.get(1).add(key);
    }
}

853. Car Fleet

So we use the distance to target as key and speed as value, iterate through all cars in order of their distances to the target.
keep track of currently slowest one(which might block the car behind), if a car can catch up current slowest one, it will not cause a new group.
Otherwise, we count a new group and update the info of slowest

Run time: $O(n\log n)$, space: $O(n)$

public int carFleet(int target, int[] position, int[] speed) {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    int n = position.length;
    for(int i=0; i<n; ++i) map.put(target - position[i], speed[i]);

    int count = 0;
    double r = -1.0;
 /*for all car this value must > 0, so we can count for the car closest to target*/
    for(Map.Entry<Integer, Integer> entry: map.entrySet()){
        int d = entry.getKey(); // distance
        int s = entry.getValue(); // speed
        double t = 1.0*d/s; // time to target
        if(t>r){ // this car is unable to catch up previous one, form a new group and update the value
            ++count;
            r = t;
        }
    }
    return count;
}

340. Longest Substring with At Most K Distinct Characters

Run time: $O(n)$, space: $O(n)$

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    int result = 0, i=0;
    Map<Character, Integer> map = new HashMap<>();
 
    for(int j=0; j<s.length(); j++){
        char c = s.charAt(j);
        map.put(c, map.getOrDefault(c, 0)+1); // count occurrences
 
        if(map.size()<=k) result = Math.max(result, j-i+1); // num of unique chars
        else{
            while(map.size() > k){
                char l = s.charAt(i);
                int count = map.get(l);
                if(count==1) map.remove(l);
                else map.put(l, map.get(l)-1);
                i++;
            }
        }
    }
    return result;
}

246. Strobogrammatic Number

Use map to record pairs of numbers, then use two pointers check one by one
Run time: $O(n)$, space: $O(1)$

public boolean isStrobogrammatic(String num) {
    Map<Character, Character> map = new HashMap<>();
    map.put('1','1');
    map.put('0','0');
    map.put('8','8');
    map.put('6','9');
    map.put('9','6');
    
    int left = 0, right = num.length() - 1; // two pointers
    while (left <= right) {
        if (!map.containsKey(num.charAt(left)) || !map.get(num.charAt(left)).equals(num.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

528. Random Pick with Weight

Use TreeMap to store the accumulated weight and index
Use higherKey to get the key given the randomly generated key, return the index

    int weight = 0;
    TreeMap<Integer, Integer> map = new TreeMap<>();
    Random rnd= new Random();
    public Solution(int[] w) {
        for (int i = 0; i < w.length; i++){
            weight += w[i];
            map.put(weight, i);
        }
    }
    
    public int pickIndex() {
        // int key= map.ceilingKey(rnd.nextInt(cnt)+1); don't forget to +1, because rand.nextInt(cnt) generate random integer in range [0,cnt-1]
        int key= map.higherKey(rnd.nextInt(weight));
        return map.get(key);
    }
}

359. Logger Rate Limiter (G)

Use map to store message and timestamp, if the key exists and the previous timestamp is less than 10, then false, otherwise update timestamp and print
Run time: $O(kn)$ ($k$ is time interval), space: $O(n)$

public class Logger {
    Map<String, Integer> map = new HashMap<>(); // msg : lst print timestamp
    int limiter = 10;
    /** Initialize your data structure here. */
    public Logger() {
    }

    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
        if(!map.containsKey(message)){
            map.put(message, timestamp);
            return true;
        }else{
            if(timestamp - map.get(message) >= limiter){
                map.put(message, timestamp);
                return true;
            }
        }
        return false;
    }
}

/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
 */

class Logger {
     
    private Map<String, Integer> map;
    /** Initialize your data structure here. */
    public Logger() {
        map = new HashMap<>();
    }
     
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
        prune(timestamp);
        if (!map.containsKey(message)) {
            map.put(message, timestamp);
            return true;
        }
        return false;
    }
     
    private void prune(int timestamp) {
        Iterator<String> itr = map.keySet().iterator();
        while (itr.hasNext()) {
            String k = itr.next();
            if (map.get(k) + 10 <= timestamp) {
                itr.remove();
            }
        }
    }
}

843. Guess the Word (G)

class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        Arrays.sort(wordlist);
        Map<String, Integer> badWords = new HashMap();
        for(String word:wordlist) {
            if (validateWord(word, badWords)){
                int score = master.guess(word);
                if (score==6) {
                    return;
                }
                badWords.put(word, score);
            }
        }
    }
    
    private boolean validateWord(String candidate, Map<String, Integer> badWords) {
        int similarity = 0;
        Integer score = 0;
        for(String w:badWords.keySet()) {
            similarity = similarity(w, candidate);
            score = badWords.get(w);
            if ( (score==0 && similarity > 0) || similarity != score ){
                return false;
            }
        }
        return true;
    }
    
    public int similarity(String s1, String s2) {
        int count = 0;
      for(int i=0; i<s1.length(); i++) {
          if (s1.charAt(i)==s2.charAt(i)) {
              count++;
          }
      }
        return count;
    }
}

380. Insert Delete GetRandom O(1) (G) (M)

class RandomizedSet {
    ArrayList<Integer> nums;
    HashMap<Integer, Integer> locs;
    java.util.Random rand = new java.util.Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        locs = new HashMap<Integer, Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        boolean contain = locs.containsKey(val);
        if ( contain ) return false;
        locs.put( val, nums.size());
        nums.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        boolean contain = locs.containsKey(val);
        if ( ! contain ) return false;
        int loc = locs.get(val);
        if (loc < nums.size() - 1 ) { // not the last one than swap the last one with this val
            int lastone = nums.get(nums.size() - 1 );
            nums.set( loc , lastone );
            locs.put(lastone, loc);
        }
        locs.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return nums.get( rand.nextInt(nums.size()) );
    }
}

56. Merge Intervals (M)

Override compare method, then sort the array
Then compare and merge the intervals

Run time: $O(n\log n)$, space: $O(n^2)$

Use TreeMap, put <start, +1> and <end,-1>
If the value of the key is 0, which implies there’s overlap

Run time: $O(n)$, space: $O(n)$

public int[][] merge(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return new int[0][0];
    Map<Integer, Integer> map = new TreeMap<>();
    for (int[] interval : intervals) {
        int start = interval[0], end = interval[1];
        map.put(start, map.getOrDefault(start, 0) + 1);
        map.put(end, map.getOrDefault(end, 0) - 1);
    }
    List<int[]> ans = new LinkedList<>();
    int newStart = 0, count = 0;
    for (Integer key : map.keySet()) {
        if (count == 0) newStart = key;
        count += map.get(key);
        // this count == 0 means a full interval has been completed
        if (count == 0) {
            ans.add(new int[]{newStart, key});
        }
    }
    return ans.toArray(new int[ans.size()][]);
}

Others

---

```
</details>

<details>
<summary>1281. Subtract the Product and Sum of Digits of an Integer</summary>

> 

Run time: $O(n)$, space: $O(1)$

``` java
    public int subtractProductAndSum(int n) {
        int prod = 1, sum = 0;
        while(n != 0){
            int temp = n % 10;
            prod *= temp;
            sum += temp;
            n = n / 10;
        }
        return prod-sum;
    }

1007. Minimum Domino Rotations For Equal Row

Count the occurrence of all numbers in A and B, and also the number of domino with two same numbers.

Try all possibilities from 1 to 6. If we can make number i in a whole row, it should satisfy that countA[i] + countB[i] - same[i] = n.

Run time: $O(n)$, space: $O(1)$

public int minDominoRotations(int[] A, int[] B) {
    int[] countA = new int[7], countB = new int[7], same = new int[7];
    int n = A.length;
    for (int i = 0; i < n; i++) {
        countA[A[i]]++;
        countB[B[i]]++;
        if (A[i] == B[i]) same[A[i]]++;
    }
    for (int i = 1; i <= 6; i++) {
        if (countA[i] + countB[i] - same[i] == n) return n - Math.max(countA[i], countB[i]);
    }
    return -1;
}

1276. Number of Burgers with No Waste of Ingredients

Solve these two equations each time
4 * jumbo + 2 * small = tomatoSlices
jumbo + small = cheeseSlices

Run time: $O(1)$, space: $O(1)$

public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
    List<Integer> ans = new ArrayList<>();
    
    // need to solve 2 equations
    // 4 * jumbo + 2 * small = tomatoSlices, jumbo + small = cheeseSlices
    
    if(tomatoSlices % 2 == 1) return ans;
    int jumbo = tomatoSlices - 2 * cheeseSlices;
    if(jumbo < 0 || jumbo % 2 == 1) return ans;
    jumbo /= 2;
    int small = cheeseSlices - jumbo;
    if(small < 0) return ans;
    
    ans.add(jumbo);
    ans.add(small);
    return ans;
}

public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
    if(tomatoSlices % 2 == 1 || tomatoSlices < cheeseSlices) return new ArrayList<Integer>();
    List<Integer> ans = new ArrayList<>();
    for(int i = 0; i <= cheeseSlices; i++){ // i is number of Jumbo
        int j = cheeseSlices - i;
        if(4*i+2*j == tomatoSlices){
            ans.add(i);
            ans.add(j);
            return ans;
        }
    }
    return ans;
}

1275. Find Winner on a Tic Tac Toe Game

Remember to separate different cases

public String tictactoe(int[][] moves) {
    if(moves.length < 5) return "Pending";
    char[][] board = new char[3][3];
    
    for(int i = 0; i < moves.length; i++){
        if(i % 2 == 0) board[moves[i][0]][moves[i][1]] = 'X';
        else board[moves[i][0]][moves[i][1]] = 'O';
    }
    String[] b = new String[3];
    b[0] = String.valueOf(board[0]);
    b[1] = String.valueOf(board[1]);
    b[2] = String.valueOf(board[2]);

    boolean xWin = isGameOver(b, 'X');
    boolean oWin = isGameOver(b, 'O');
    if(xWin) return "A";
    else if(oWin) return "B";
    else if(moves.length == 9) return "Draw";
    return "Pending";
}

public boolean isGameOver(String[] board, char player) {
    // check horizontal
    for (int i = 0; i < 3; i++) {
        if (board[i].charAt(0) == player && board[i].charAt(0) == board[i].charAt(1) && board[i].charAt(1) == board[i].charAt(2)) {
            return true;
        }
    }

    // check vertical
    for (int j = 0; j < 3; j++) {
        if (board[0].charAt(j) == player && board[0].charAt(j) == board[1].charAt(j) && board[1].charAt(j) == board[2].charAt(j)) {
            return true;
        }
    }

    // check diagonal
    if (board[1].charAt(1) == player && (board[0].charAt(0) == board[1].charAt(1) && board[1].charAt(1) == board[2].charAt(2)
            || board[0].charAt(2) == board[1].charAt(1) && board[1].charAt(1) == board[2].charAt(0))) {
        return true;
    }
    return false;
}

1093. Statistics from a Large Sample

First iteration: if the frequency count is not zero, update the min (only once), max, mode, and sum, number of elements
Find out the average, calculate the median in two ways: (total + 1) / 2 and total / 2 + 1
Second iteration: Keep track of the current number of elements, and compare with two medians, add first half and second half

Run time: $O(n)$, space: $O(1)$

public double[] sampleStats(int[] count) {
    int total = 0, mode = 0;
    double median = 0, min = -1, max = 0, avg = 0, sum = 0;
    for (int i = 0; i < 256; i++) {
        if (count[i] > 0) {
            total += count[i];
            if (min < 0) min = i;
            max = i;
            sum += i * count[i];
            if (count[i] > count[mode]) mode = i;
        }
    }
    avg = sum / total;
    if (total == 1) median = sum; // single element.
    int m1 = (total + 1) / 2, m2 = total / 2 + 1; // m1-th and m2-th items are medians.
    for (int i = 0, cnt = 0; total > 1 && i < 256; i++) { // more than 1 elements.
        if (cnt < m1 && cnt + count[i] >= m1) // find m1-th item.
            median += i / 2.0d; // add its half.
        if (cnt < m2 && cnt + count[i] >= m2) // find m2-th item.
            median += i / 2.0d; // add its half.
        cnt += count[i];
    }
    return new double[]{min, max, avg, median, mode};
}

341. Flatten Nested List Iterator

Use stack and push all NestedIterator in the list, no matter if it is a list or not
Then each time when hasNext() is called, if the top element is a list, push the elements in this list to the stack

Run time: $O(1)$ for each method?, space: $O(n)$

public class NestedIterator implements Iterator<Integer> {
    private Stack<NestedInteger> stack;
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        flattenList(nestedList);
    }

    @Override
    public Integer next() {
        if(hasNext()) return stack.pop().getInteger();
        return null;
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (stack.peek().isInteger()) return true;
            flattenList(stack.pop().getList());
        }
        return false;
    }

    private void flattenList(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            stack.push(list.get(i));
        }
    }
}

1267. Count Servers that Communicate

Use two maps to store the row and list of columns, the column and list of rows, then add to the set

Run time: $O(n^2)$, space: $O(n^2)$

public int countServers(int[][] grid) {
    Map<Integer, ArrayList<Integer>> row = new HashMap<>();
    Map<Integer, ArrayList<Integer>> col = new HashMap<>();
    Set<String> set = new HashSet<>();
    int m = grid.length, n = grid[0].length;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 1){
                ArrayList<Integer> temp = row.getOrDefault(i, new ArrayList<>());
                temp.add(j);
                row.put(i, temp);
                ArrayList<Integer> temp2 = col.getOrDefault(j, new ArrayList<>());
                temp2.add(i);
                col.put(j, temp2);
            }
        }
    }
    
    for(int i: row.keySet()){
        if(row.get(i).size() > 1) {
            for(int j: row.get(i)){
                String s = i+" "+j;
                if(!set.contains(s)) set.add(s);
            }
        }
    }
    for(int i: col.keySet()){
        if(col.get(i).size() > 1) {
            for(int j: col.get(i)){
                String s = j+" "+i;
                if(!set.contains(s)) set.add(s);
            }
        }
    }
    return set.size();
}

1266. Minimum Time Visiting All Points

Traverse the input array, for each pair of neighboring points, comparing the absolute difference in x and y coordinates, the larger value is the minimum time need to travel between them; Sum these time.

Run time: $O(n)$, space: $O(1)$

public int minTimeToVisitAllPoints(int[][] points) {
    int ans = 0;
    for (int i = 1; i < points.length; i++) {
        int[] cur = points[i], prev = points[i - 1];
        ans += Math.max(Math.abs(cur[0] - prev[0]), Math.abs(cur[1] - prev[1]));
    }
    return ans;        
}

public int minTimeToVisitAllPoints(int[][] points) {
    int ans = 0;
    for(int i = 1; i < points.length; i++){
        int dX = Math.abs(points[i][0]-points[i-1][0]);
        int dY = Math.abs(points[i][1]-points[i-1][1]);
        int minMove = Math.min(dX, dY);
        ans += dX + dY - minMove;
    }
    return ans;
}

836. Rectangle Overlap (M)

Case 1:if the maximum of rec1 is less than or equal to the minimum from rec2 in the x
Case 2:if the maximum of rec1 is less than or equal to the minimum from rec2 in the y
Case 3: just swap rec1 and rec2 in Case 1
Case 4:Just swap rec1 and rec2 in Case 2

Run time: $O(1)$, space: $O(1)$

public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    return !(rec1[1] >= rec2[3] // higher
            || rec1[3] <= rec2[1] // lower
            || rec1[2] <= rec2[0] // lefter
            || rec1[0] >= rec2[2]); // righter
}

794. Valid Tic-Tac-Toe State (M)

Since the board is 3x3, to check if the game is over, just brute force

public boolean validTicTacToe(String[] board) {
    if (board.length == 0) return false;

    // turns = 0 represents 'X' will move, otherwise, 'O' will move
    int turns = 0;

    // check whether 'X' wins or 'O' wins, or no players win
    boolean xWin = isGameOver(board, 'X');
    boolean oWin = isGameOver(board, 'O');

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length(); j++) {
            if (board[i].charAt(j) == 'X') {
                turns++;
            } else if (board[i].charAt(j) == 'O') {
                turns--;
            }
        }
    }

    /**
     * Four conditions will be the invalid tic tac toe board:
     * 1. there are more 'O' than 'X'
     * 2. the board has 2 more 'X' than 'O'
     * 3. number of 'X' is equal to number of 'O', but 'X' wins, it is impossible because if 'X' wins, the game is 
     * over, 'O' cannot play again, then number of 'O' MUST less than 'X'
     * 4. number of 'X' is more than number of 'O', but 'O' wins, it is impossible because if 'O' wins, the game is
     * over, 'X' cannot play again, then number of 'X' CANNOT greater than 'O'
     * */
    if (turns < 0 || turns > 1 || turns == 0 && xWin || turns == 1 && oWin) {
        return false;
    }
    return true;
}

public boolean isGameOver(String[] board, char player) {
    // check horizontal
    for (int i = 0; i < 3; i++) {
        if (board[i].charAt(0) == player && board[i].charAt(0) == board[i].charAt(1) && board[i].charAt(1) == board[i].charAt(2)) {
            return true;
        }
    }

    // check vertical
    for (int j = 0; j < 3; j++) {
        if (board[0].charAt(j) == player && board[0].charAt(j) == board[1].charAt(j) && board[1].charAt(j) == board[2].charAt(j)) {
            return true;
        }
    }

    // check diagonal
    if (board[1].charAt(1) == player && (board[0].charAt(0) == board[1].charAt(1) && board[1].charAt(1) == board[2].charAt(2)
            || board[0].charAt(2) == board[1].charAt(1) && board[1].charAt(1) == board[2].charAt(0))) {
        return true;
    }
    return false;
}

69. Sqrt(x) (M)

In a while loop, when i > x / i, update i to be (i + x / i) / 2

Run time: $O(\log n)$?, space: $O(1)$

public int mySqrt(int x) {
    if(x == 0) return 0;
    long i = x;
    while(i > x / i) i = (i + x / i) / 2;	    	
    return (int) i;
}

227. Basic Calculator II (M)

Keep track of the last sign, the current number, temporary sum, and total sum

Run time: $O(n)$, space: $O(1)$

public int calculate(String s) {
    int sum = 0;
    int tempSum = 0;
    int num = 0;
    char lastSign = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) num = num * 10 + (c-'0');
        if (i == s.length() - 1 || !Character.isDigit(c) && c!=' ') {
            switch(lastSign) {
                case '+':
                    sum += tempSum;
                    tempSum = num;
                    break;
                case '-':
                    sum += tempSum;
                    tempSum = -num;
                    break;
                case '*':
                    tempSum *= num;
                    break;
                case '/':
                    tempSum /= num;
                    break;
            }
            lastSign = c;
            num = 0;
        }
    }
    sum += tempSum;
    return sum;
}

Use stack

Run time: $O(n)$, space: $O(n)$

public int calculate(String s) {
    int len;
    if(s == null || (len = s.length()) == 0) return 0;
    Stack<Integer> stack = new Stack<Integer>();
    int num = 0;
    char sign = '+';
    for(int i = 0; i < len; i++){
        if(Character.isDigit(s.charAt(i))) num = num*10 + (s.charAt(i)-'0');
        if((!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ') || i == len-1){
            if(sign=='-') stack.push(-num);
            if(sign=='+') stack.push(num);
            if(sign=='*') stack.push(stack.pop()*num);
            if(sign=='/') stack.push(stack.pop()/num);
            sign = s.charAt(i);
            num = 0;
        }
    }

    int re = 0;
    for(int i: stack) re += i;
    return re;
}

295. Find Median from Data Stream (M)

Use a max heap and min heap
Every time we add a num, if max heap is empty, or the top element is greater than this one, add it. If not, add to the min heap. If the max heap size differs the min heap size by more than 1, move the largest element in max heap to min heap. If the min heap size is greater than the max heap size, move the smallest element in min heap to the max heap
When finding the median, if the max heap size and min heap size are the same, get the average of top elements. Otherwise, return the top element in max heap

class MedianFinder {
     /** initialize your data structure here. */
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    /** initialize your data structure here. */
    public MedianFinder() {  
        maxHeap = new PriorityQueue<Integer>((a,b) -> b - a);
        minHeap = new PriorityQueue<Integer>((a,b) -> a - b);
    }  
    public void addNum(int num) {
        if(maxHeap.isEmpty() || maxHeap.peek() >= num){
            maxHeap.add(num);
        }else{
            minHeap.add(num);
        }
        
        if(minHeap.size() + 1 < maxHeap.size()) {
            minHeap.add(maxHeap.poll());
        } else if(maxHeap.size() < minHeap.size()){
            maxHeap.add(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if(maxHeap.size() == minHeap.size()){
            return (maxHeap.peek() + minHeap.peek())/2.0;
        }
        return maxHeap.peek();
    }
}

716. Max Stack

class MaxStack {

    Stack<Integer> stack;
    Stack<Integer> maxStack;
    /** initialize your data structure here. */
    public MaxStack() {
        stack = new Stack<>();
        maxStack = new Stack<>();
    }
    
    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        stack.push(x);
    }
    
    public int pop() {
        maxStack.pop();
        return stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int peekMax() {
        return maxStack.peek();
    }
    
    public int popMax() {
        int val = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != val) { buffer.push(pop()); }
        pop();
        while (!buffer.isEmpty()) { push(buffer.pop()); }
        return val;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */

1238. Circular Permutation in Binary Representation

Generate one bit diff permutation list. Rotate the list to make it start from “start”.
Use Collections.rotate() to make the code neater.

public List<Integer> circularPermutation(int n, int start) {
    List<Integer> res = oneBitDiffPermutation(n);
    int i = 0;
    while (res.get(i) != start) i++;
    Collections.rotate(res, -i);
    return res;
}

public List<Integer> oneBitDiffPermutation(int n){
    List<Integer> tmp = new ArrayList<>();
    tmp.add(0);
    if(n == 0) return tmp;

    for(int i = 0; i < n; i ++){
        for(int j = tmp.size() - 1; j >= 0; j --){
            tmp.add(tmp.get(j) + (1 << i));
        }
    }
    return tmp;
}

My way: same idea

public List<Integer> circularPermutation(int n, int start) {
    List<String> arr = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    arr.add("0");  
    arr.add("1");  

    int j;  
    for (int i = 2; i < (1<<n); i = i<<1){  
        for (j = i-1 ; j >= 0 ; j--) arr.add(arr.get(j));  
        for (j = 0 ; j < i ; j++) arr.set(j, "0" + arr.get(j));  
        for (j = i ; j < 2*i ; j++) arr.set(j, "1" + arr.get(j));  
    }  

    for (int i = 0 ; i < arr.size() ; i++) ans.add(Integer.parseInt(arr.get(i), 2));
    int index = ans.indexOf(start);
    for(int i = 0; i < index; i++){
        int temp = ans.get(0);
        ans.remove(0);
        ans.add(temp);
    }
    return ans;
}

1237. Find Positive Integer Solution for a Given Equation

Rephrase the problem:
Given a matrix, each row and each column is increasing.
Find all coordinates (i,j) that A[i][j] == z

Runtime: $O(X+Y)$, space: $O(X)$

public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
    List<List<Integer>> res = new ArrayList<>();
    int x = 1, y = 1000;
    while (x <= 1000 && y > 0) {
        int v = customfunction.f(x, y);
        if (v > z) --y;
        else if (v < z) ++x;
        else res.add(Arrays.asList(x++, y--));
    }
    return res;
}

My brute force way

public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
    List<List<Integer>> ans = new ArrayList<>();
    for(int x = 1; x <= 1000; x++){
        for(int y = 1; y <= 1000; y++){
            if(customfunction.f(x, y) == z){
                List<Integer> temp = Arrays.asList(x, y);
                ans.add(temp);
            }
        }
    }
    return ans;
}

299. Bulls and Cows

Iterate over the numbers in secret and in guess and count all bulls right away. For cows maintain an array that stores count of the number appearances in secret and in guess. Increment cows when either number from secret was already seen in guest or vice versa.

Runtime: $O(n)$, space: $O(1)$

public String getHint(String secret, String guess) {
    int bulls = 0, cows = 0;
    int[] numbers = new int[10];
    for (int i = 0; i < secret.length(); i++) {
        if (secret.charAt(i) == guess.charAt(i)) bulls++;
        else {
            if (numbers[secret.charAt(i)-'0']++ < 0) cows++;
            if (numbers[guess.charAt(i)-'0']-- > 0) cows++;
        }
    }
    return bulls + "A" + cows + "B";
}

Slow and straightforward way

public String getHint(String secret, String guess) {
    if((secret == null && guess == null) || 
       secret.length() != guess.length()) return null;
    int bull = 0, cow = 0;
    Map<Character,Integer> map = new HashMap<>();
    for(int i = 0; i < secret.length(); i++){
        char c1 = secret.charAt(i), c2 = guess.charAt(i);
        if(c1 == c2) bull++;
        else map.put(c1, map.getOrDefault(c1, 0)+1);
    }
    for(int i = 0; i < secret.length(); i++){
        char c1 = secret.charAt(i), c2 = guess.charAt(i);
        if(c1 != c2) {
            if(map.containsKey(c2)){
                cow++;
                if(map.get(c2) == 1) map.remove(c2);
                else map.put(c2, map.get(c2)-1);
            }
        }
    }
    return new String(bull+"A"+cow+"B");
}

73. Set Matrix Zeroes

Two boolean variables to flag the first row and column, and mark the first entry in corresponding row and column to be zero

Runtime: $O(n^2)$, space: $O(1)$ (in-place)

public void setZeroes(int[][] matrix) {
    boolean fr = false,fc = false;
    for(int i = 0; i < matrix.length; i++) {
        for(int j = 0; j < matrix[0].length; j++) {
            if(matrix[i][j] == 0) {
                if(i == 0) fr = true;
                if(j == 0) fc = true;
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    for(int i = 1; i < matrix.length; i++) {
        for(int j = 1; j < matrix[0].length; j++) {
            if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if(fr) {
        for(int j = 0; j < matrix[0].length; j++) {
            matrix[0][j] = 0;
        }
    }
    if(fc) {
        for(int i = 0; i < matrix.length; i++) {
            matrix[i][0] = 0;
        }
    }
}

393. UTF-8 Validation

Rule 2:
Record the count of consecutive of 1.
Move the number 5 bit right, if it equals “110” means there is one ‘1’.
Move the number 4 bit right, if it equals “1110” means there are two ‘1’.
…
Move the number 7 bit right, if it equals “1” means it is “10000000” which has no meaning, return false.
Rule 1:
If it is not started with “10”, return false;

Runtime: $O(n)$, space: $O(1)$

    public boolean validUtf8(int[] data) {
        int count = 0;
        for(int d:data){
          if(count == 0){
            if((d >> 5) == 0b110) count = 1;
            else if((d >> 4) == 0b1110) count = 2;
            else if((d >> 3) == 0b11110) count = 3;
            else if((d >> 7) ==  1) return false;
          } else {
            if((d>>6) != 0b10) return false;
            else count--;
          }
        }
        return count == 0;
    }```
</details>

<details>
<summary>1188. Design Bounded Blocking Queue</summary>

> Use AtomicInteger to keep track of current size

``` java
public class BoundedBlockingQueue<E> {  
   private final Queue<E> queue = new LinkedList<E>();  
   private final int capacity;  
   private final AtomicInteger count = new AtomicInteger(0);  

   public BoundedBlockingQueue(int capacity) {  
     if (capacity <= 0)  throw new InvalidArgumentException("The capacity of the queue must be > 0.");
     this.capacity = capacity;  
   }  
   
   public int size() {  
     return count.get();  
   }  
   
   public synchronized void add(E e) throws RuntimeException {  
     if (e == null) throw new NullPointerException("Null element is not allowed.");  
   
     int oldCount = -1;
     while (count.get() == capacity) wait();  
   
     queue.add(e);  
     oldCount = count.getAndIncrement();  
     if (oldCount == 0) {
       notifyAll(); // notify other waiting threads (could be producers or consumers)  
     }
   }  
   
   public synchronized E remove() throws NoSuchElementException {  
     int oldCount = -1;
     while (count.get() == 0) wait();  
  
     E e = queue.remove();  
     oldCount = count.getAndDecrement();  
     if (oldCount == this.capacity) {
       notifyAll(); // notify other waiting threads (could be producers or consumers)  
     }
     return e;
   } 
 
   /* Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty. */
   public E peek() {  
     if (count.get() == 0) return null;  
     synchronized(this) {
       return queue.peek();  
     }
   }  
 }  

829. Consecutive Numbers Sum

Runtime: $O(\log n)$, space: $O(n)$

public int consecutiveNumbersSum(int N) {
    int ans = 1, count = 0;
    while (N % 2 == 0) N /= 2;
    for (int i = 3; i*i <= N; ans *= count+1, i += 2){
        count = 0;
        while(N % i == 0){
            N /= i;
            count++;
        }
    }
    if(N == 1) return ans;
    return 2*ans;
}

Roblox OA 1

Use BigInteger and pass the string and base to it, then convert to long

Runtime: $O(n)$, space: $O(n)$

public static long getNumber(SinglyLinkedListNode binary) {
// Write your code here
    String s = "";
    while(binary != null){
        int n = binary.data;
        s += Integer.toString(n);
        binary = binary.next;
    }
    
    return new BigInteger(s, 2).longValue();
}

Pure Storage OA

public class Solution {
    // Complete the compute_number_score function below.
    static int compute_number_score(int number) {
        int i = 0, score = 0, numSum = 0;
        char[] arr = (""+number).toCharArray();
        while(i < arr.length){
            if(arr[i] == '7') score += 1; // 7
            if((arr[i]-'0') % 2 == 0) score += 4; // even digit
            numSum += (arr[i]-'0');
            i++;
        }
        if(numSum % 3 == 0) score += 2; // multiple of 3

        i = 0;
        int count5 = 0;
        while(i < arr.length-1){ // consecutive 5s
            if(arr[i] == '5' && arr[i+1] == '5') count5++;
            i++;
        }
        score += count5 * 3;

        i = 0;
        int len = 0;
        while(i < arr.length){ // descending
            len++;
            while(i+1 < arr.length && ((arr[i]-'0') - (arr[i+1]-'0') == 1)) {
                len++;
                i++;
            }
            score += len*len;
            len = 0;
            i++;
        }
        return score;
    }

public class Solution {
    // Complete the check_log_history function below.
    static int check_log_history(List<String> events) {
        Stack<String> stack = new Stack<>();
        Set<String> keys = new HashSet<>();
        for(int i = 0; i < events.size(); i++){
            String op = events.get(i).split(" ")[0];
            String key = events.get(i).split(" ")[1];
            if(op.equals("ACQUIRE")) {
                if(keys.contains(key)) return i+1;
                else {
                    stack.push(key);
                    keys.add(key);
                }
            }
            else if(op.equals("RELEASE")){
                String lastKey = stack.peek();
                if(lastKey.equals(key)) {
                    stack.pop();
                    keys.remove(key);
                }
                else return i+1;
            }
        }
        if(!stack.isEmpty()) return events.size()+1;
        return 0;
    }

157. Read N Characters Given Read4

Iterative: read files by 4 chars each time, if less than 4 then it’s the end of file

Runtime: $O(n)$, space: $O(n)$

public int read(char[] buf, int n) {
  boolean eof = false;      // end of file flag
  int total = 0;            // total bytes have read
  char[] tmp = new char[4]; // temp buffer

  while (!eof && total < n) {
    int count = read4(tmp);

    // check if it's the end of the file
    eof = count < 4;

    // get the actual count
    count = Math.min(count, n - total);

    // copy from temp buffer to buf
    for (int i = 0; i < count; i++) 
      buf[total++] = tmp[i];
  }
  return total;
}

158. Read N Characters Given Read4 II - Call multiple times

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */
 
public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    private char[] buf4 = new char[4];
    private int buf4Index = 4;
    private int buf4Size = 4;
    public int read(char[] buf, int n) {
        int i = 0;
        while (i < n) {
            if (buf4Index >= buf4Size) {
               buf4Size = read4(buf4);
               buf4Index = 0;
               if (buf4Size == 0) {
                   break;
               }
            }
            buf[i] = buf4[buf4Index];
            buf4Index ++;
            i ++;
        }
        return i;
    }
}

Queues (Priority Queues)

---

```
</details>

<details>
<summary>DMV Hustle (Okta OA 2019)</summary>

> 

``` java
    public int[] solution(String[] customers, int numWindows, int queueSize) {
        int num = 0;
        int[] ans = new int[numWindows+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[0]-b[0] : a[1]-b[1]); // [id, endTime], sort by endTime
    	Queue<Integer> q = new LinkedList<>(); // waitUntil time
    	
    	// add all available windows
    	for(int i = 1; i <= numWindows; i++) pq.add(new int[]{i, 0}); 
	
    	for(int i = 0; i < customers.length; i++){
    	    int arrTime = Integer.parseInt(customers[i].split(",")[0]);
    	    int serviceTime = Integer.parseInt(customers[i].split(",")[1]);
    	    int maxEnd = Integer.parseInt(customers[i].split(",")[2]);
    	    int[] curWindow = pq.poll();
    	    
    	    if(arrTime >= curWindow[1]){ // available when this customer arrives
    	        curWindow[1] = arrTime + serviceTime;
    	        pq.add(curWindow);
    	        ans[curWindow[0]]++;
    	        num++;
    	    } else if(arrTime+maxEnd < curWindow[1]) { // exceed the tolerance time
    	        pq.add(curWindow);
    	        continue;
    	    } else{ // wait and serve
    	        while(!q.isEmpty() && q.peek() <= arrTime) q.poll();
    	        if(q.size() >= queueSize) continue;
    	        
    	        curWindow[1] += serviceTime;
    	        pq.add(curWindow);
    	        ans[curWindow[0]]++;
    	        num++;
    	        q.add(curWindow[1]); // wait in the queue
    	    }
    	}
    	ans[0] = num;
    	return ans;
    }

1094. Car Pooling (G)

Process all trips, adding passenger count to the start location, and removing it from the end location. After processing all trips, a positive value for the specific location tells that we are getting more passengers; negative - more empty seats.
Finally, scan all stops and check if we ever exceed our vehicle capacity.

Run time: $O(n)$, space: $O(n)$

public boolean carPooling(int[][] trips, int capacity) {    
    int stops[] = new int[1001]; 
    for (int t[] : trips) {
        stops[t[1]] += t[0];
        stops[t[2]] -= t[0];
    }
    for (int i = 0; capacity >= 0 && i < 1001; i++) capacity -= stops[i];
    return capacity >= 0;
}

Save all time points and the change on current capacity
Sort all the changes on the key of time points.
Track the current capacity and return false if negative

Run time: $O(n\log n)$, space: $O(n)$

public boolean carPooling(int[][] trips, int capacity) {
    Map<Integer, Integer> m = new TreeMap<>();
    for (int[] t : trips) {
        m.put(t[1], m.getOrDefault(t[1], 0) + t[0]);
        m.put(t[2], m.getOrDefault(t[2], 0) - t[0]);
    }
    for (int v : m.values()) {
        capacity -= v;
        if (capacity < 0) return false;
    }
    return true;
}

Sort the trips array by start location;
Use a PriorityQueue to store the trips, order by ending location.
Loop through the trips array, for each start location, keep polling out the arrays with correpoinding end location <= current start location, for each polled out array, add the corresponding passengers to capacity; deduct passengers at current start location from capacity, if capacity < 0, return false.
Repeat 3 till end, if never encounter false, return true.

Run time: $O(n\log n)$, space: $O(n)$

public boolean carPooling(int[][] trips, int capacity) {
    Arrays.sort(trips, Comparator.comparing(trip -> trip[1]));
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(trip -> trip[2]));
    for (int[] trip : trips) {
        while (!pq.isEmpty() && trip[1] >= pq.peek()[2]) {// any passengers need to get off?
            capacity += pq.poll()[0]; // more capacity as passengers out.
        }
        capacity -= trip[0]; // less capacity as passengers in.
        if (capacity < 0) return false; // not enough capacity.
        pq.offer(trip); // put into PriorityQueue the infomation at current location.
    }
    return true;
}

253 . Meeting Rooms II

Sort list by starting time, use PriorityQueue to store end time
If current smallest one in the minHeap is earlier than the starting time in the array, poll it
Return the size of minHeap

Run time: $O(n\log n)$, space: $O(n)$

public int minMeetingRooms(int[][] meetings) {
	if (meetings.length == 0) return 0;
    Arrays.sort(meetings, Comparator.comparingInt(meeting -> meeting[0]));
    Queue<Integer> minHeap = new PriorityQueue<>();
    minHeap.add(meetings[0][1]);
    for (int i = 1; i < meetings.length; i++) {
        if (minHeap.peek() <= meetings[i][0])
            minHeap.poll();
        minHeap.add(meetings[i][1]);
    }
    return minHeap.size();
}

Sort array by starting time
Use min heap sorted by ending time, add first interval into the heap
For the rest of the intervals, see if the ending

Run time: $O(n\log n)$, space: $O(n)$

public int minMeetingRooms(Interval[] intervals) {
	if(intervals == null || intervals.length == 0) return 0;
	Arrays.sort(intervals, (a,b) -> a.start - b.start);
	PriorityQueue<Interval> minHeap = new PriorityQueue<>((a,b) -> a.end - b.end);
	minHeap.add(intervals[0]);
	for(int i = 0; i < intervals.length; i++){
		Interval current = intervals[i];
		Interval earliest = minHeap.remove();
		if(current.start >= earliest.end) earliest.end = current.end; // no conlict
		else minHeap.add(current);
		minHeap.add(earliest);
	}
	return minHeap.size();
}

Sliding Window

---

```
</details>


<details>
<summary>438. Find All Anagrams in a String</summary>

> 

Runtime: $O(n)$, space: $O(n)$

``` java
    public List<Integer> findAnagrams(String s, String p) {
        int left = 0;
        int right = 0;
        int matchSize = p.length();
        int[] map = new int[256];
        List<Integer> res = new ArrayList<>();
        // count the char number in p 计算p中各个字符的数量
        for (char c:p.toCharArray()) map[c]++;

        // build window 开始进行sliding window
        while (right < s.length()){
           // this char exists in p  
           // 如果当前的char是存在于p中，则目标大小matchsize就得减少
           // 判断标准就是他的值不是为-1
           if (map[s.charAt(right)] > 0)
               matchSize --;
            map[s.charAt(right)] --;

           // if the window size equals to p
           // 如果此时左右指针的差值等于p的长度
           if (right - left == p.length()-1){
               // check matchSize equals to 0
               // 如果此时目标大小也是0，说明这就是需要的一个子串
               if (matchSize == 0)
                   // add the left index
                   res.add(left);

               // move left pointer to start new search
               // 如果当这个字符原来是p中的话，现在移动指针需要还原以前原有的matchSize，开始新的搜索
               if (map[s.charAt(left)] >= 0)
                   matchSize ++;
               // 还原以前每个元素减去的1
               map[s.charAt(left)]++;
               left++;
           }
          // move right
           // 老哥们别忘了
          right++;
        }
        return res;
    }

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    if(s == null || p == null || s.length() < p.length()) return ans;
    int[] a1 = new int[26];
    int[] a2 = new int[26];
    int pLen = p.length();
    for(char c : p.toCharArray()){
        a1[c-'a']++;
    }
    
    for(int i = 0; i < pLen; i++){
        char c = s.charAt(i);
        a2[c-'a']++;
    }
    if(Arrays.equals(a1, a2)) ans.add(0);
    for(int i = pLen; i < s.length(); i++){
        char c = s.charAt(i);
        a2[c-'a']++;
        c = s.charAt(i - pLen);
        a2[c-'a']--;
        if(Arrays.equals(a1, a2)) ans.add(i - pLen + 1); //O(26)
    }
    return ans;
}

Longest Subarray having sum of elements at most K (G)

Relevant link: GFG
Given an array of integers, our goal is to find the length of largest subarray having sum of its elements at most k where k>0.
1.Traverse the array and check if on adding the current element its sum is less than or equal to k.

2. If it’s less than k then add it to sum and increase the count.
   3.Else: Remove the first element of subarray and decrease the count.
   Again check if on adding the current element its sum is less than or equal to k.
   If it’s less than k then add it to sum and increase the count.
3. Keep track of Maximum count.

Run time: $O(n)$, space: $O(1)$

public static int atMostSum(int arr[], int n, int k) { 
    int sum = 0; 
    int cnt = 0, maxcnt = 0; 
  
    for (int i = 0; i < n; i++) { 
        // If adding current element doesn't 
        // cross limit add it to current window 
        if ((sum + arr[i]) <= k) { 
            sum += arr[i];  
            cnt++; 
        }  
  
        // Else, remove first element of current 
        // window. 
        else if(sum!=0) { 
        sum = sum - arr[i - cnt] + arr[i]; 
       } 
        // keep track of max length. 
        maxcnt = Math.max(cnt, maxcnt);  
    } 
    return maxcnt; 
} 

(Brute Force)
Find all the subarrays whose sum is less than or equal to k and return the one with largest length.

Run time: $O(n^2)$

727. Minimum Window Substring (G)

Find minimum window substring from s that contains all characters in t.
Need an indicator to show whether to move tail or head

Run time: $O(n)$, space: $O(1)$

public String minWindow(String s, String t){
	Map<Character, Integer> map = new HashMap<>();
	for(char c: s.toCharArray()) map.put(temp, 0);
	for(char c: t.toCharArray()){
		if(map.containsKey(c)) map.put(c, map.get(c)+1);
		else return ""; // does not contain all chars in t
	}
	int start = 0, end = 0, minLen = Integer.MAX_VALUE, minStart = -1, numOfTargets = t.length();
	while(end < s.length()){
		char c = s.charAt(end);
		if(map.get(c) > 0) numOfTargets--; // found a qualified char in s
		map.put(c, map.get(c)-1);
		while(numOfTargets == 0){ // the window satisfies the requirement
			if(minLen > end - start + 1){
				minLen = end - start + 1;
				minStart = start;
			}
			char head = s.charAt(start);
			if(map.get(head) >= 0) numOfTargets--;
			map.put(head, map.get(head)+1);
			start++;
		}
		end++; // move tail of window forward
	}
	return minStart == -1? "" : s.substring(minStart, minStart+minLen);
}

1248. Count Number of Nice Subarrays

Sliding window: Exactly K times = at most K times - at most K - 1 times

Run time: $O(n)$, space: $O(1)$

public int numberOfSubarrays(int[] A, int k) {
    return atMost(A, k) - atMost(A, k - 1);
}

public int atMost(int[] A, int k) {
    int res = 0, i = 0, n = A.length;
    for (int j = 0; j < n; j++) {
        k -= A[j] % 2;
        while (k < 0)
            k += A[i++] % 2;
        res += j - i + 1;
    }
    return res;
}

public int numberOfSubarrays(int[] nums, int k) {
    int count = 0; 
    int prefix[] = new int[nums.length]; 
    int odd = 0; 
  
    // traverse in the array 
    for (int i = 0; i < nums.length; i++) { 
        prefix[odd]++; 
        if ((nums[i] & 1) == 1) odd++; // if odd 

        if (odd >= k) count += prefix[odd - k]; 
    } 
    return count; 
}

239. Sliding Window Maximum

Run time: $O(n)$, space: depends

   public int[] maxSlidingWindow(int[] nums, int k) {		
	if (nums == null || k <= 0) {
		return new int[0];
	}
	int n = nums.length;
	int[] r = new int[n-k+1];
	int ri = 0;
	// store index
	Deque<Integer> q = new ArrayDeque<>();
	for (int i = 0; i < nums.length; i++) {
		// remove numbers out of range k
		while (!q.isEmpty() && q.peek() < i - k + 1) {
			q.poll();
		}
		// remove smaller numbers in k range as they are useless
		while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
			q.pollLast();
		}
		// q contains index... r contains content
		q.offer(i);
		if (i >= k - 1) {
			r[ri++] = nums[q.peek()];
		}
	}
	return r;
}

159. Longest Substring with At Most Two Distinct Characters

i records starting index, j records second distinct index
First, we could simplify the problem by assuming that S contains two or more distinct characters, which means T must contain exactly two distinct characters. The brute force approach is O(n3) where n is the length of S. We can form every possible substring, and for each substring insert all characters into a Set which the Set’s size indicating the number of distinct characters. This could be easily improved to O(n2) by reusing the same Set when adding a character to form a new substring.

The trick is to maintain a sliding window that always satisfies the invariant where there are always at most two distinct characters in it. When we add a new character that breaks this invariant, how can we move the begin pointer to satisfy the invariant? Using the above example, our first window is the substring “abba”. When we add the character ‘c’ into the sliding window, it breaks the invariant. Therefore, we have to readjust the window to satisfy the invariant again. The question is which starting point to choose so the invariant is satisfied.

Run time: $O(n)$, space: $O(n)$

public int lengthOfLongestSubstringTwoDistinct(String s) {
   int i = 0, j = -1, maxLen = 0;
   for (int k = 1; k < s.length(); k++) {
      if (s.charAt(k) == s.charAt(k - 1)) continue;
      if (j >= 0 && s.charAt(j) != s.charAt(k)) {
         maxLen = Math.max(k - i, maxLen);
		i = j + 1; 
      }
	j = k - 1; 
   }
   return Math.max(s.length() - i, maxLen);
}

Follow up: at most k distinct characters

public int lengthOfLongestSubstringTwoDistinct(String s) {
   int[] count = new int[256];
   int i = 0, numDistinct = 0, maxLen = 0;
   for (int j = 0; j < s.length(); j++) {
      if (count[s.charAt(j)] == 0) numDistinct++;
      count[s.charAt(j)]++;
      while (numDistinct > 2) {
         count[s.charAt(i)]--;
         if (count[s.charAt(i)] == 0) numDistinct--;
         i++;
}
      maxLen = Math.max(j - i + 1, maxLen);
   }
   return maxLen;
}

Arrays, Matrices, List

---

```
</details>

<details>
<summary>287. Find the Duplicate Number</summary>

> The problem is the same as find the cycle in LinkedList!

Run time: $O(n)$, space: $O(1)$

``` java
public int findDuplicate(int[] nums) {
    int n = nums.length;
    int slow = n;
    int fast = n;
    do{
        slow = nums[slow-1];
        fast = nums[nums[fast-1]-1];
    }while(slow != fast);
    slow = n;
    while(slow != fast){
        slow = nums[slow-1];
        fast = nums[fast-1];
    }
    return slow;
}

you perceive the indices as the values.
Then count the number of values lesser than the mid
If the if the count is lesser than mid, we assume the duplicate number should be on the higher side of the number scale.
so we make low = mid + 1
else we assume the duplicate number should be on the lower end of the number scale.
so we make high = mid - 1
We continue until low <=hight no longer holds true.

Run time: $O(\log n)$, space: $O(1)$

public int findDuplicate(int[] nums) {
    int low = 1, high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low)/2;
        int cnt = 0;
        for (int a : nums) {
            if (a <= mid) cnt++;
        }
        if (cnt <= mid) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

283. Move Zeroes

Keep track of the index of first zero position. Use a for loop, if the current number is not zero, swap with the zero index and increment the zero index.

Run time: $O(n)$, space: $O(1)$

public void moveZeroes(int[] nums) {
    if (nums == null || nums.length <= 1) return;

    int cur = 0; // zero position index
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            if(i == cur){
                cur++;
                continue;
            }
            int temp = nums[cur];
            nums[cur++] = nums[i];
            nums[i] = temp;
        }
    }
}

54. Spiral Matrix (M)

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> ans = new LinkedList<>();
    if(matrix.length == 0) return ans;
    
    int m = matrix.length, n = matrix[0].length;
    int r = 0, c = 0;        

    while (r < m && c < n){           
        for (int j = c; j < n; j++) ans.add(matrix[r][j]);
        r++; // new starting row
        
        for (int j = r; j < m; j++) ans.add(matrix[j][n-1]);
        n--; // adjust row bound
        
        if (r < m) {
            for (int j = n-1; j >= c; j--) ans.add(matrix[m-1][j]);
        }
        m--; // adjust col bound
        
        if (c < n) {
            for (int j = m-1; j >= r; j--) ans.add(matrix[j][c]);
        }
        c++;
    }
    return ans;
}

Recursion way (asked in Point72 interview)

public List<Integer> spiralOrder(int[][] matrix) {
    // Check for edge cases for the matrix
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return new ArrayList<Integer>();
    
    List<Integer> res = new ArrayList<Integer>();
    // Run our recursion starting with the first and last eligible rows and the first and last eligible columns
    spiralOut(res, matrix, 0, matrix.length - 1, 0, matrix[0].length - 1);
    return res;
}

private void spiralOut(List<Integer> res, int[][] m, int r1, int r2, int c1, int c2){
    // Return if we've exhausted all values to the point of invalid indices
    if(r1 > r2 || c1 > c2) return;
    
    // TOP ROW: left to right
    for(int c = c1; c <= c2; c++) res.add(m[r1][c]);
    
    // RIGHT COLUMN: top to bottom
    for(int r = r1 + 1; r <= r2; r++) res.add(m[r][c2]);
    
    // Return if we've processed the last row/column because we'd otherwise repeat values
    if(r1 == r2 || c1 == c2) return;
    
    // BOTTOM ROW: right to left
    for(int c = c2 - 1; c >= c1; c--) res.add(m[r2][c]);
    
    // LEFT COLUMN: bottom to top
    for(int r = r2 - 1; r >= r1 + 1; r--) res.add(m[r][c1]);
    
    // Recursion through the inner matrix
    spiralOut(res, m, r1 + 1, r2 - 1, c1 + 1, c2 - 1);
}

1262. Greatest Sum Divisible by Three

Keep track of the minimum sums that are 1 mod 3 and 2 mod 3, and also update the total sum.

Run time: $O(n)$, space: $O(1)$

public int maxSumDivThree(int[] nums) {
    int res = 0, leftOne = 20000, leftTwo = 20000;
    for(int n:nums){
        res+=n;
        if(n%3==1){
            leftTwo = Math.min(leftTwo,leftOne+n);
            leftOne = Math.min(leftOne,n);
        }
        if(n%3==2) {
            leftOne = Math.min(leftOne,leftTwo+n);
            leftTwo = Math.min(leftTwo,n);
        }
    }
    if(res%3==0) return res;
    if(res%3==1) return res-leftOne;
    return res - leftTwo;
    
}

1260. Shift 2D Grid

Number the cells from 0 to m * n - 1;
In case k >= m * n, use k % (m * n) to avoid those whole cycles of m * n operations;
Since shifting right will put the last k cells in grid on the first k cells, we start from the kth cells from last, the index of which is m * n - k % (m * n).

public List<List<Integer>> shiftGrid(int[][] grid, int k) {
    int m = grid.length, n = grid[0].length; 
    int start = m * n - k % (m * n);
    List<List<Integer>> ans = new LinkedList<>();
    for (int i = start; i < m * n + start; i++) {
        int j = i % (m * n), r = j / n, c = j % n;
        if ((i - start) % n == 0)
            ans.add(new ArrayList<>());
        ans.peekLast().add(grid[r][c]);
    }
    return ans;
}

665. Non-decreasing Array (M)

Keep track of the number of decreasing pairs
First set the previous element to be -1, update it in each iteration
If the current one is greater than the next one, check if the previous element plus 1 if greater than the next one or not, if it is, set the next one to be the current element plus 1

Run time: $O(n)$, space: $O(1)$

public boolean checkPossibility(int[] nums) {
    int decreasingCount = 0;
    int prev = -1;
    for (int i = 0; i < nums.length-1; i++) {
        if (nums[i] > nums[i+1]) {
            if (prev+1 > nums[i+1]) nums[i+1] = nums[i] + 1;
            decreasingCount++;
        }
        prev = nums[i];
    }
    return decreasingCount <= 1;
}

325. Maximum Size Subarray Sum Equals K (G)

Use a map to store <tempSum, index> and iterate through the array
If sum-k is in the map, update the longest length of subarray

public int maxSubArrayLen(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int result = 0;
    int sum = 0;
 
    for(int i=0; i<nums.length; i++){
        sum += nums[i];
        if(map.containsKey(sum - k)){
            result = Math.max(result, i - map.get(sum - k));
        }
        map.putIfAbsent(sum, i);
    }
 
    return result;
}

363. Max Sum of Rectangle No Larger Than K (G)

Use the same rule to get the all the submatrix prefixSum. The reason $\log n$` is here we use balanced BST here. (In java, TreeSet or TreeMap)

Run time: $O(n^2 m\log m)$, space: $O(n)$, where $n$ is the col size and $m$ is row size

public int maxSumSubmatrix(int[][] matrix, int k) {
    int row = matrix.length;
    int col = matrix[0].length;
    int result = Integer.MIN_VALUE;

    for(int j = 0; j < col; j++) {
        int[] sum = new int[row];

        for(int current = j; current < col; current++) {
            for(int i = 0; i < row; i++) {
                sum[i] += matrix[i][current];
            }
            result = Math.max(find(sum, k), result);
        }
    }
    return result;
}
//O(MlgM) find the maxium gap
private int find(int[] sum, int k) {
    int result = Integer.MIN_VALUE;
    TreeSet<Integer> set = new TreeSet<>();
    set.add(0);
    int current = 0;
    for(int i = 0; i < sum.length; i++) {
        current += sum[i];

        Integer target = set.ceiling(current - k); 

        if(target != null) {
            result = Math.max(result, current - target);
        }
        set.add(current);
    }
    return result;
}

Print shortest path to print a string on screen (G)

Relevant link: GFG Given a screen containing alphabets from A-Z, we can go from one character to another characters using a remote. The remote contains left, right, top and bottom keys. Find shortest possible path to type all characters of given string using the remote. Initial position is top left and all characters of input string should be printed in order.
The idea is to consider screen as 2D-matrix of characters. Then we consider all characters of given string one by one and print out the shortest path between current character and next character in the matrix. In order to find shortest path, we consider the coordinates of current character and next character in the matrix. Based on the difference between x and y values of current and next character’s coordinates, we move left, right, top or bottom.

// Function to print shortest possible path to 
// type all characters of given string using a remote 
static void printPath(String str) { 
    int i = 0; 
    int curX = 0, curY = 0; // start from character 'A' present at position (0, 0) 
    while (i < str.length()) { 
        // find coordinates of next character 
        int nextX = (str.charAt(i) - 'A') / 5; 
        int nextY = (str.charAt(i) - 'B' + 1) % 5; 
   
        while (curX > nextX) { // Move Up if destination is above
            System.out.println("Move Up"); 
            curX--; 
        } 
   
        while (curY > nextY) { // Move Left if destination is to the left 
            System.out.println("Move Left"); 
            curY--; 
        } 
   
        while (curX < nextX) { // Move down if destination is below 
            System.out.println("Move Down"); 
            curX++; 
        } 
   
        while (curY < nextY) { // Move Right if destination is to the right  
            System.out.println("Move Right"); 
            curY++; 
        } 
   
        System.out.println("Press OK"); // At this point, destination is reached  
        i++; 
    } 
} 

36. Valid Sudoku (M)

In outer for loop, use three sets to store current row, column, and cube values
For checking numbers in cube, the entry is board[i+j/3][3*j%3+j%3].

Run time: $O(n^2)$, space: $O(n^2)$

public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i<9; i++){
        HashSet<Character> rows = new HashSet<Character>();
        HashSet<Character> columns = new HashSet<Character>();
        HashSet<Character> cube = new HashSet<Character>();
        for (int j = 0; j < 9;j++){
            if(board[i][j]!='.' && !rows.add(board[i][j]))
                return false;
            if(board[j][i]!='.' && !columns.add(board[j][i]))
                return false;
            int RowIndex = 3*(i/3);
            int ColIndex = 3*(i%3);
            if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
                return false;
        }
    }
    return true;
}

Use one set to store occurrences by adding string to differentiate entry

public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            char number = board[i][j];
            if (number != '.')
                if (!seen.add(number + " in row " + i) ||
                    !seen.add(number + " in column " + j) ||
                    !seen.add(number + " in block " + i/3 + "-" + j/3))
                    return false;
        }
    }
    return true;
}

658. Find K Closest Elements (G)

Binary search
We can binary research i
We compare the distance between x - A[mid] and A[mid - k] - x
If x - A[mid] > A[mid + k] - x,
it means A[mid + 1] ~ A[mid + k] is better than A[mid] ~ A[mid + k - 1],
and we have mid smaller than the right i.
So assign left = mid + 1.

Run time: $O(log(N - K))$ to binary research and find result, $O(K)$ to create the returned list.

public List<Integer> findClosestElements(int[] A, int k, int x) {
    int left = 0, right = A.length - k;
    while (left < right) {
        int mid = (left + right) / 2;
        if (x - A[mid] > A[mid + k] - x)
            left = mid + 1;
        else
            right = mid;
    }
    return Arrays.stream(A, left, left + k).boxed().collect(Collectors.toList());
}

Use two pointers to find the bound of qualified subarray
While the bound >= k, if the distance of lo and x is greater than that of hi and x, move lo, otherwise move hi

Run time: $O(n)$, space: $O(n)$

  public List<Integer> findClosestElements(int[] arr, int k, int x) {
      int lo = 0;
int hi = arr.length - 1;
while (hi - lo >= k) {
	if (Math.abs(arr[lo] - x) > Math.abs(arr[hi] - x)) {
		lo++;
	} else {
		hi--;
	}
}
List<Integer> result = new ArrayList<>(k);
for (int i = lo; i <= hi; i++) {
	result.add(arr[i]);
}
return result;
  }

1250. Check If It Is a Good Array

Chinese Remainder Theorem

Run time: $O(n)$, space: $O(1)$

public boolean isGoodArray(int[] A) {
    int x = A[0], y;
    for (int a: A) {
        while (a > 0) {
            y = x % a;
            x = a;
            a = y;
        }
    }
    return x == 1;
}

public boolean isGoodArray(int[] nums) {
    long g = nums[0];
    for (int i = 1; i < nums.length; i++) {
        g = gcd(g, nums[i]);
    }
    return (g == 1);
}
long gcd(long a, long b) { 
  if (b == 0) return a; 
  return gcd(b, a % b);  
} 

1243. Array Transformation

Use a flag to indicate if this round has no change

public List<Integer> transformArray(int[] arr) {
    if(arr == null || arr.length == 0) return new ArrayList<Integer>();
    if(arr.length == 1) return Arrays.asList(arr[0]);
    if(arr.length == 2) return Arrays.asList(arr[0], arr[1]);
    int prev = arr[0];
    boolean noChange = false;
    while(!noChange){
        int num = 0;
        for(int i = 1; i < arr.length-1; i++){
            int temp = arr[i], next = arr[i+1];
            if(temp < prev && temp < next) arr[i]++;
            else if(temp > prev && temp > next) arr[i]--;
            // System.out.println(i+" "+Arrays.toString(arr));
            if(temp != arr[i]) num++;
            if(i == arr.length-2) prev = arr[0];
            else prev = temp;
        }
        if(num == 0) noChange = true;
    }
    List<Integer> list = new ArrayList<>(); 
  
    for (int t : arr) list.add(t); 
  
    return list; 
}

public List<Integer> transformArray(int[] arr) {
    int[] ans = new int[arr.length];
    while (!Arrays.equals(ans, arr)) {
        ans = arr.clone();
        for (int i = 1; i < arr.length - 1; ++i) {
            if (ans[i - 1] < ans[i] && ans[i] > ans[i + 1]) {
                --arr[i];
            }else if ( ans[i - 1] > ans[i] && ans[i] < ans[i + 1]) {
                ++arr[i];
            }
        }
    }
    return arr.length < 3 ? arr : Arrays.stream(ans).boxed().collect(Collectors.toList());
}

560. Subarray Sum Equals K

Use HashMap to put <sum, num occurrences>, first put <0, 1>
Calculate the accumulated sum, and see if the map contains sum-k
If there is, get the number of occurrences and add to the count
Then put this sum and update the number of occurrences

Run time: $O(n)$, space: $O(n)$

public int subarraySum(int[] nums, int k) {
    int sum = 0, result = 0;
    Map<Integer, Integer> preSum = new HashMap<>(); // sum, num of occurences
    preSum.put(0, 1);
    
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (preSum.containsKey(sum - k)) result += preSum.get(sum - k);

        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
    }
    
    return result;
}

Normal way
Run time: $O(n^2)$, space: $O(1)$

public int subarraySum(int[] nums, int k) {
    if(nums.length == 0) return 0;
    int minLength = nums.length;
    int count = 0;
    for(int i = 0; i < nums.length; i++){
        if (nums[i] == k) count++;
        int temp = nums[i];
        for(int j = i-1; j >= 0; j--){
            temp += nums[j];
            if(temp == k) count++;
        }
    }
    return count;
}

88. Merge Sorted Array (M)

i records last index in nums1, j records last valid index in nums1; k records last index in nums2

Run time: $O(n)$, space: $O(1)$

public void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int i = m+n-1, j = m-1, k = n-1; i>=0; i--) {
        if (j < 0) nums1[i] = nums2[k--];
        else if (k < 0) continue; // rest numbers in nums1 is sorted already
        else if (nums1[j] > nums2[k]) nums1[i] = nums1[j--];
        else nums1[i] = nums2[k--];
    }   
}

238. Product of Array Except Self

Use one array to keep track of the products of all previous numbers
Then a backward loop and a variable to accumlate the product

Run time: $O(n)$, space: $O(1)$

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) res[i] = res[i-1] * nums[i-1];
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res;
}

62. Unique Paths

Same way, use fewer space

Run time: $O(mn)$, space: $O(n)$

public int uniquePaths(int m, int n) {
    if (m == 0 || n == 0) return 0;
    if (m == 1 || n == 1) return 1;
    
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) dp[i] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) dp[j] += dp[j - 1];
    }
    return dp[n - 1];
}

Straightforward way (this is also called DP???)

Run time: $O(mn)$, space: $O(mn)$

public int uniquePaths(int m, int n) {
    if(m == 0 || n == 0) return 0;
    
    int[][] path = new int[m][n];
    for(int j = 0; j < n; j++) path[0][j] = 1;
    for(int i = 0; i < m; i++) path[i][0] = 1;
    
    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            path[i][j] = path[i][j-1] + path[i-1][j];
        }
    }
    return path[m-1][n-1];
}

Math way, binomial coefficient, might not work as expected when m,n is pretty large

Run time: $O(n)$, space: $O(1)$

public int uniquePaths(int m, int n) {
    double value = 1;
    for (int i = 1; i <= n - 1; i++) {
        value *= ((double) (m + i - 1) / (double) i);
    }
    return (int) Math.round(value);
}

33. Search in Rotated Sorted Array

Use binary search to find the target, need start and end indices
If start is smaller than mid, then this range is in order; otherwise right part is in order
If target is in the ordered range, update the start/end index
More ways: link

Run time: $O(\log n)$, space: $O(1)$

public int search(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (target == nums[mid]) return mid;
        if (nums[start] <= nums[mid]) { // left part is in increasing order
            // target is here
            if (target >= nums[start] && target < nums[mid]) end = mid - 1;
            else start = mid + 1;
        } else { // right part is in increasing order
            if (target > nums[mid] && target <= nums[end]) start = mid + 1;
            else end = mid - 1;
        }
    }
    return -1;
}

523. Continuous Subarray Sum

Use map to record tempSum mod k and the current index
If the tempSum is in the map, which means that the range (i,j] is a qualified subarray.

Run time: $O(n)$, space: $O(n)$

public boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};
    int tempSum = 0;
    for (int i = 0; i < nums.length; i++){
        tempSum += nums[i];
        if (k != 0) tempSum %= k; // get tempSum mod k if k is not zero 
        Integer prev = map.get(tempSum); // get the corresponding index
        if (prev != null) { // exist before, the range of subarray is qualified
            if (i - prev > 1) return true;
        }
        else map.put(tempSum, i);
    }
    return false;
}

59. Spiral Matrix II

Set four bounds: rowBegin, rowEnd, colBegin, colEnd. Follow the direction and use four for loops to fill in the number.

Run time: $O(n^2)$, space: $O(n^2)$

public int[][] generateMatrix(int n) {
    int[][] res = new int[n][n];

    int cur = 1;
    int rowBegin = 0, rowEnd = n - 1, colBegin = 0, colEnd = n - 1;
    
    while(cur <= n*n) {
            int i = rowBegin, j = colBegin;
            //left to right
            for(j = colBegin ; j <= colEnd; j++) res[rowBegin][j] = cur++;
            rowBegin++;
            //top to bottom
            for(i = rowBegin ; i <= rowEnd; i++) res[i][colEnd] = cur++;
            colEnd--;
            //right to left
            for(j = colEnd ; j >= colBegin; j--) res[rowEnd][j] = cur++;
            rowEnd--;
            //bot to top
            for(i = rowEnd; i >= rowBegin; i--) res[i][colBegin] = cur++;
            colBegin++;
    }
    return res;
}

215. Kth Largest Element in an Array (M)

Quick select: two pointers, move from two sides of array, sort and see if the element is found

public int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, k);
}

int quickSelect(int[] nums, int low, int high, int k) {
    int pivot = low;

    // use quick sort's idea
    // put nums that are <= pivot to the left
    // put nums that are  > pivot to the right
    for (int j = low; j < high; j++) {
        if (nums[j] <= nums[high]) swap(nums, pivot++, j);
    }
    swap(nums, pivot, high);

    // count the nums that are > pivot from high
    int count = high - pivot + 1;
    // pivot is the one!
    if (count == k) return nums[pivot];
    // pivot is too small, so it must be on the right
    if (count > k) return quickSelect(nums, pivot + 1, high, k);
    // pivot is too big, so it must be on the left
    return quickSelect(nums, low, pivot - 1, k - count);
}
void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

public int findKthLargest(int[] nums, int k) {
    k = nums.length - k; // convert to index of k largest
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int i = l; // partition [l,r] by A[l]: [l,i]<A[l], [i+1,j)>=A[l]
        for (int j = l + 1; j <= r; j++)
            if (nums[j] < nums[l]) swap(nums, j, ++i);
        swap(nums, l, i);

        if (k < i) r = i - 1;
        else if (k > i) l = i + 1;
        else return nums[i];
    }
    return -1; // k is invalid
}

public void swap(int[] a, int i, int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Common way: sort the array then loop and find the element

public int findKthLargest(int[] nums, int k) {
    if(k > nums.length) return -1;
    Arrays.sort(nums);
    for(int i = nums.length-1; i >= 0; i--){
        if(i == nums.length-k) return nums[i];
    }
    return nums[0];
}

128. Longest Consecutive Sequence

Use a hashset and put all elements in
Then loop through the array, set the left and right pointer, if removing this element from the set is successful, then increment/decrement by 1. After two while loops, use right-left-2+1 to find the current length.

Run time: $O(n)$, space: $O(n)$

public int longestConsecutive(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    Set<Integer> set = new HashSet<>();
    int ans = 0;
    for(int n : nums) set.add(n);
    for(int n : nums){
        int left = n-1, right = n+1;
        while(set.remove(left)) left--;
        while(set.remove(right)) right++;
        ans = Math.max(ans, right-left-2+1);
    }
    return ans;
}

334. Increasing Triplet Subsequence

It is the same is finding the two min elements and see if there is a third one
If it’s the minimum, update; else if it is smaller than the second minimum, update
else, there exists an increasing triplet subsequence!

Run time: $O(n)$, space: $O(1)$

public boolean increasingTriplet(int[] nums) {
    int min = Integer.MAX_VALUE;
    int min2 = Integer.MAX_VALUE;
    for(int num : nums){
        if(num <= min) min = num;
        else if(num < min2) min2 = num;
        else if(num > min2) return true;
    }
    return false;
}

1144. Decrease Elements To Make Array Zigzag

Run time: $O(n)$, space: $O(1)$

public int movesToMakeZigzag(int[] nums) {
    int res[] = new int[2],  n = nums.length, left, right;
    for (int i = 0; i < n; i++) {
        left = i > 0 ? nums[i - 1] : 1001;
        right = i + 1 < n ? nums[i + 1] : 1001;
        res[i % 2] += Math.max(0, nums[i] - Math.min(left, right) + 1);
    }
    return Math.min(res[0], res[1]);
}

Roblox OA 2

GFG link: Maximum value in an array after m range increment operations

Run time: $O(m+n)$, space: $O(n)$

public static long listMax(int n, List<List<Integer>> operations) {
    long[] a = new long[n+1];
    long max = 0, sum = 0;
    for(int i = 0; i < operations.size(); i++){
        List<Integer> op = operations.get(i);
        int start = op.get(0)-1, end = op.get(1)-1, num = op.get(2);
        a[start] += num; 
        a[end + 1] -= num; 
    }
    for (int i = 0; i < n; i++){ 
        sum += a[i]; 
        max = Math.max(max, sum); 
    } 
    return max;
}

1217. Play with Chips

Since only when moving odd steps, the cost will be one, we only need to keep track of two possible answers.

Run time: $O(n)$, space: $O(1)$

public int minCostToMoveChips(int[] chips) {
    int[] cnt = new int[2];
    for (int chip : chips)
        ++cnt[chip % 2];
    return Math.min(cnt[0], cnt[1]);
}

Brute force: loop through every possible solution and find the min one

Run time: $O(n^2)$, space: $O(1)$

public int minCostToMoveChips(int[] chips) {
    Set<Integer> set = new HashSet<>();
    for(int c: chips) set.add(c);
    int min = Integer.MAX_VALUE;
    for(int loc: set){
        int total = 0;
        for(int c: chips){
            int dist = Math.abs(c - loc);
            total += dist % 2;
        }
        min = Math.min(min, total);
    }
    return min;
}

15. 3Sum

Loop from index 0 to length-2
Two pointers from i+1 and length-1
Once find an answer, move two pointers to skip duplicates, then increment/decrement

Run time: $O(n^2)$, space: depends

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < nums.length-2; i++) {
        if (i == 0 || (i > 0 && nums[i] != nums[i-1])) { // skip duplicate
            int lo = i+1, hi = nums.length-1, sum = 0 - nums[i];
            while (lo < hi) {
                if (nums[lo] + nums[hi] == sum) {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[lo+1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi-1]) hi--;
                    lo++; hi--;
                } else if (nums[lo] + nums[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}

766. Toeplitz Matrix

Loop through first row and column, check edge cases
Run time: $O(n^2)$, space: $O(1)$

public boolean isToeplitzMatrix(int[][] matrix) {
    if(matrix.length == 1 || matrix[0].length == 1) return true;
    
    for(int i = 0; i < matrix.length; i++){ // left part
        int curr = matrix[i][0];
        for(int j = i+1; j < matrix.length && j-i < matrix[0].length; j++){
            if(matrix[j][j-i] != curr) return false;
        }
    }
    
    for(int i = 1; i < matrix[0].length; i++){ // right part
        int curr = matrix[0][i];
        for(int j = i+1; j-i < matrix.length && j < matrix[0].length; j++){
            if(matrix[j-i][j] != curr) return false;
        }
    }
    
    return true;
}

163. Missing Ranges

One loop, one variable to keep track of the current starting range
Skip duplicate, increment by 1 if the same
Otherwise, find the range between the var and the current num minus 1
Then update the var
Run time: $O(n)$, space: $O(n)$

public List<String> findMissingRanges(int[] nums, int lower, int upper) {
	List<String> result = new ArrayList<>();
    	int start = lower;        
   	 if(lower==Integer.MAX_VALUE) return result; // no need to continue
	 for(inti i = 0; i < nums.length; i++){
	 	if(i < nums.length-1 && nums[i] == nums[i+1]) continue; // skip duplicate
		if(nums[i] == start) start++; // found in the array
		else{ // there is a gap between start and current num
			result.add(getRange(start, nums[i]-1));
			if(nums[i] == Integer.MAX_VALUE) return result;
			start = nums[i] + 1;
		}
	 }
	 
	 if(start <= upper) result.add(getRange(start, upper));
	 return result;
}

private String getRange(int n1, int n2) {
    return n1 == n2 ? String.valueOf(n1) : String.format("%d->%d" , n1, n2);
}

57. Insert Interval

One pointer, three while loops, one way
Create a list and put all intervals that end before the new interval
For the list that starts before or on the end time of the new interval, get min of starting time, get max of ending time
Add the rest of the intervals to the list
Run time: $O(n)$, space: $O(n)$

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> ans = new ArrayList<>();
    int i = 0, n = intervals.length;
    while(i < n && intervals[i][1] < newInterval[0]){
        ans.add(intervals[i]);
        i++;
    }
    while(i < n && intervals[i][0] <= newInterval[1]){
        newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
        newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
        i++;
    }
    ans.add(newInterval);
    
    while(i < n){
        ans.add(intervals[i]);
        i++;
    }
    n = ans.size();
    int[][] newIntervals = new int[n][2];
    for(int k = 0; k < n; k++){
        newIntervals[k][0] = ans.get(k)[0];
        newIntervals[k][1] = ans.get(k)[1];
    }
    return newIntervals;
}

308. Range Sum Query 2D - Mutable

Use two matrices; one for copying original matrix, one for calculating accumulating column sum
When updating specific entry, loop through all rows on the same column, and update the value
When summing the region, looping through col1 to col2, add the difference between row2 and row1

public class NumMatrix {

    public int[][] colSum;
    public int[][] matrix;
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        if (matrix == null || matrix.length == 0) {
            return;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        colSum = new int[m + 1][n];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                colSum[i][j] = colSum[i - 1][j] + matrix[i - 1][j];
            }
        }
    }
    
    public void update(int row, int col, int val) {
        for (int i = row + 1; i < colSum.length; i++) {
            colSum[i][col] = colSum[i][col] - matrix[row][col] + val;
        }
        matrix[row][col] = val;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int j = col1; j <= col2; j++) {
            sum += colSum[row2 + 1][j] - colSum[row1][j]; 
        }
        return sum;
    }
}

939. Minimum Area Rectangle

Use Map<Integer, Set> to store x-value, and set of y-values
Then use nested for loop, skip points with same x or y values, see if they can form a rectangle, then update the min
Run time: $O(n^2)$, space: $O(n^2)$

public int minAreaRect(int[][] points) {
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for(int[] a: points){
        Set<Integer> set = map.getOrDefault(a[0], new HashSet());
        set.add(a[1]); // or say if not exist, then put a new set,
        map.put(a[0], set); // then do map.get(a[0]).add(a[1]);
    }
    
    int min = Integer.MAX_VALUE;
    for(int[] a1: points){
        for(int[] a2: points){
            if(a1[0] == a2[0] || a1[1] == a2[1]) continue;
            if(map.get(a1[0]).contains(a2[1]) && 
              map.get(a2[0]).contains(a1[1])){ // form a rectangle
                min = Math.min(min, Math.abs((a1[0]-a2[0])*(a1[1]-a2[1])));
            }
        }
    }
    if(min == Integer.MAX_VALUE) return 0;
    return min;

Strings

---

647. Palindromic Substrings

Extend palindrome on each char (2 cases), and keep track of the number

Run time: $O(n^2)$, space: $O(1)$

public int countSubstrings(String s) {
    if(s == null || s.length() == 0) return 0;
    if(s.length() == 1) return 1;
    int count = 0;
    
    for(int i = 0; i < s.length(); i++){
        count += numPalin(s, i, i) + numPalin(s, i-1, i);
    }
    return count;
}

private int numPalin(String s, int i, int j){
    if(i > j) return 0;
    int c = 0;
    while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
        i--;
        j++;
        c++;
    }
    return c;
}

DP way: dp[i + 1][j - 1] is referred to the string in between dp[i][j], which is the last status before expanding to dp[i][j], that’s why we are using dp.
For j - i < 3, think that you have a string AXA, and j-i here is 2, since A is matched with A, X does not matter here.
So when the strings in between is less than or equal to 1 char, we can ignore it.

public int countSubstrings(String s) {
    int n = s.length();
    int res = 0;
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
            if(dp[i][j]) res++;
        }
    }
    return res;
}

71. Simplify Path

Elegant solution! Split the original string by “/”. Push the element to stack if it is not .., ., or empty. If it is .., then pop the top element from the stack.
Then append “/” and each element to the string builder. If in the end the string builder is empty, return /.

Run time: $O(n)$, space: $O(n)$

public String simplifyPath(String path) {
    StringBuilder sb = new StringBuilder();
    Stack<String> stack = new Stack<>();
    for (String dir : path.split("/")){
        if (dir.equals("..") && !stack.isEmpty()) {
            stack.pop();
        } else if (!dir.equals("..") && !dir.equals(".")&& !dir.equals("")){
            stack.push(dir);
        }
    }
    for(String s : stack) sb.append("/"+ s);
    return sb.length() == 0? "/": sb.toString();
}

482. License Key Formatting (M)

First remove all - and change to upper case
Create StringBuilder variable and initialize the index to be length-K
Decrement i by K each time we have inserted -

Run time: $O(n)$, space: $O(n)$

 public String licenseKeyFormatting(String S, int K) {
    S = S.replaceAll("-", "").toUpperCase();
    StringBuilder sb = new StringBuilder(S);
    // Starting from the end of sb, and going backwards. 
    int i = sb.length() - K;
    while(i > 0) {
        sb.insert(i, '-');
        i -= K;
    }
    return sb.toString();
}

680. Valid Palindrome II (FB intern, failed in 2018)

Use a boolean to flag whether one character has been removed or not

Run time: $O(n)$, space: $O(1)$

public boolean validPalindrome(String s) {
    if(s == null || s.length() <= 1) return true;
    return helper(s, 0, s.length()-1, false);
}

boolean helper(String s, int i, int j, boolean del){
    if(i == j) return true;
    while(i <= j){
        if(s.charAt(i) == s.charAt(j)){
            i++;
            j--;
        }
        else if (!del){
            return helper(s, i+1, j, true) || helper(s, i, j-1, true);
        }
        else return false;
    }
    return true;
}

12. Integer to Roman (M)

public String intToRoman(int num) {
    StringBuilder sb = new StringBuilder();
    int[] values ={1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] tokens={"M", "CM","D","CD","C","XC","L","XL","X","IX","V","IV", "I"};
    int i = 0;
    while(num > 0){
        // if greater than values[i], could repeat multi times, not increment i here
        if(num >= values[i]){
            num-= values[i];
            sb.append(tokens[i]);
        } else  i++; // if less than values[i], safely move forward 
    }
    return sb.toString();
}

public String intToRoman(int num) {
    String M[] = {"", "M", "MM", "MMM"};
    String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    return M[num/1000] + C[(num%1000)/100]+ X[(num%100)/10] + I[num%10];
}

1055. Shortest Way to Form String (G)

// inverted index data structure
// dict[i][c - ‘a’] represents the earliest index >= i where character c occurs in source.
// time complexity: O(M + N) 97.67% 1ms --> M is the length of source, N is the length of target
// space complexity: O(M) 100%

public int shortestWay(String source, String target) {
    char[] s = source.toCharArray();
    char[] t = target.toCharArray();
    int M = s.length;
    int N = t.length;
    int[][] dict = new int[M][26];
    Arrays.fill(dict[M-1], -1); // -1 means no that char in source
    dict[M - 1][s[M - 1] - 'a'] = M - 1;
    for(int x = M - 2; x >= 0; --x) {
        dict[x] = Arrays.copyOf(dict[x + 1], 26);
        dict[x][s[x] - 'a'] = x;
    }
    int ans = 0;
    int idx = 0;
    for(char c: t) {
        if(dict[0][c - 'a'] == -1) return -1;
        if(dict[idx][c - 'a'] == -1) {
            ++ans;
            idx = 0;
        }
        
        idx = dict[idx][c - 'a'] + 1;
        if(idx == M) {
            ++ans;
            idx = 0;
        }
    }
    return ans + (idx == 0 ? 0 : 1);
}

把字符串S里的所有字符统计一下，记录它们出现的位置
然后一个个字符去扫描t
假设t是abcabab,
一开始找到了a的最左边的Index 0,
那我在找第二个字母b的时候，b必须要出现在之前index的后面
第三个字母c，也必须出现在前面的index的后面
所以扫描的时候记录一下之前找到的index就可以了
为了快速查找，用treeset实现o(logn)找index

Run time: $O(n\log n)$, space: $O(n)$

public int shortestWay(String s, String t) {
    Map<Character, TreeSet<Integer>> map = new HashMap();
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        TreeSet<Integer> set = map.getOrDefault(c, new TreeSet());
        set.add(i);
        map.put(c, set);
    }
    
    int res = 1, prev = -1;
    for(int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        TreeSet<Integer> set = map.get(c);
        if(set == null) return -1;
        Integer high = set.higher(prev);
        if(high != null) {
            prev = high;
        } else {
            res++;
            prev = set.first();
        }            
    }
    return res;
}

Brute force: check each substring one by one

Run time: $O(mn)$, space: $O(1)$, where $m$ is the length of source, $n$ is the length of target

public int shortestWay(String source, String target) {
    int t = 0, res = 0;
    while (t < target.length()) {
        int start = t;
        for (int s = 0; s < source.length(); s++) 
            if (t < target.length() && target.charAt(t) == source.charAt(s)) t++;
        if (start == t) return -1;
        res++;
    }
    return res;
}

678. Valid Parenthesis String (G)

low: take ‘*’ as ‘)’, if there are some ‘(’ not matched; high: take ‘*’ as ‘(’

if high < 0 means too much ‘)’
if low > 0 , after the count finished, means too much ‘(’

Since low take ‘*’ as ‘)’, there might be too much ‘)’, so that low might less than 0. That’s why low-- should happen only low>0. This can thought as, low only take as much as '('s ‘)’ and ignore other ‘)’ s. This will not cause problem since: ‘*’ can be treated as empty; high has deal with the situation that too much ‘)’ exist

Run time: $O(n)$, space: $O(1)$

public boolean checkValidString(String s) {
    int low = 0, high = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            low++;
            high++;
        } else if (s.charAt(i) == ')') {
            if (low > 0) low--;
            high--;
        } else {
            if (low > 0) low--;
            high++;
        }
        if (high < 0) return false;
    }
    return low == 0;
}

Dynamic programming
How to check valid parenthesis w/ only ( and )? Easy. Count each char from left to right. When we see (, count++; when we see ) count–; if count < 0, it is invalid () is more than (); At last, count should == 0.
This problem added *. The easiest way is to try 3 possible ways when we see it. Return true if one of them is valid.

Run time: $O(n^2)$, space: $O(n^2)$

private Boolean[][] dp;
public boolean checkValidString(String s) {
    dp = new Boolean[s.length() + 1][s.length() + 1];
    return check(s, 0, 0);
}
private boolean check(String s, int start, int count) {
    if (count < 0) return false;
    int y = count;
    if (dp[start][y] != null) return dp[start][y];
    for (int i = start; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            count++;
        } else if (c == ')') {
            if (count <= 0) return false;
            count--;
        } else if (c == '*') {
            dp[start][y] = (check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count));
            return dp[start][y];
        }
    }
    dp[start][y] = (count == 0);
    return dp[start][y];
}

524. Longest Word in Dictionary through Deleting (G)

Compare each word, if it works, check if it is smaller lexicographical order or longer

Run time: $O(n\log n)$, space: $O(1)$, where $n$ is the length of dictionary

public String findLongestWord(String s, List<String> d) {
    String longest = "";
    for (String dictWord : d) {
        int i = 0;
        for (char c : s.toCharArray()) 
            if (i < dictWord.length() && c == dictWord.charAt(i)) i++;

        if (i == dictWord.length() && dictWord.length() >= longest.length()) 
            if (dictWord.length() > longest.length() || dictWord.compareTo(longest) < 0)
                longest = dictWord;
    }
    return longest;
}

Sort the dictionary by lexicographical order first

Run time: $O(n)$, space: $O(1)$, where $n$ is the length of dictionary

public String findLongestWord(String s, List<String> d) {
    Collections.sort(d, (a,b) -> a.length() != b.length() ? -Integer.compare(a.length(), b.length()) :  a.compareTo(b));
    for (String dictWord : d) {
        int i = 0;
        for (char c : s.toCharArray()) 
            if (i < dictWord.length() && c == dictWord.charAt(i)) i++;
        if (i == dictWord.length()) return dictWord;
    }
    return "";
}

My way

public String findLongestWord(String s, List<String> d) {
    String ans = "";
    for(String str: d){
        if(helper(s, str)){
            if(ans.length() < str.length()) ans = str; 
            else if(ans.length() == str.length() && ans.compareTo(str) > 0) ans = str; 
        } 
    }
    return ans;
}

private boolean helper(String s, String str){
    if(s.length() < str.length()) return false;
    int i = 0;
    for(char c: s.toCharArray()){
        if(i < str.length() && str.charAt(i) == c) i++;
    }
    if(i == str.length()) return true;
    return false;
}

809. Expressive Words (G)

Use a helper function to check is this word can be extended
If the original word is longer than the extended one, return false
For each comparison, if the character are not the same, return false
Otherwise move the index until not the same or reach the end
Calculate the number of repeated words
If the repeated length in extended word is less than 3 and it is not equal to the word in list, false
If the repeated length in extended word >= 3 and it is smaller than the word in list, false

Run time: $O(mn)$, space: $O(1)$ , where $m$ is length of longest word, $n$ is number of words

public int expressiveWords(String S, String[] words) {
    int count = 0;
    for(int i = 0; i < words.length; i++){
        if(canExtend(S, words[i])) count++;
    }
    return count;
}

private boolean canExtend(String S, String word){
    if(S.length() < word.length()) return false; // impossible
    
    int indexS = 0, indexW = 0;
    while(indexS < S.length() && indexW < word.length()){
        int initialS = indexS, initialW = indexW;
        char s = S.charAt(indexS), w = word.charAt(indexW);
        if(s != w) return false;
        else{
            while(indexW < word.length() && s == word.charAt(indexW)) indexW++;
            while(indexS < S.length() && s == S.charAt(indexS)) indexS++;
            
            int cnt1 = indexS - initialS;
            int cnt2 = indexW - initialW;
            if(cnt1 < 3){
                if(cnt1 != cnt2) return false;
            } else {
                if(cnt1 < cnt2) return false;
            }
        }
    }
    return indexS == S.length() && indexW == word.length();
}

1249. Minimum Remove to Make Valid Parentheses

Edited the code to append all characters except those invalid open parentheses, then reverse the stringbuilder. This will achieve O(N) with slight headache.
A new StringBuilder is created for the result, but you could reuse the first one by replacing the ( in place and prune the starting open number of chars.

Run time: $O(n)$, space: $O(n)$

public String minRemoveToMakeValid(String s) {
    StringBuilder sb = new StringBuilder();
    int open = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') 
            open++;
        else if (c == ')') {
            if (open == 0) continue;
            open--;
        }
        sb.append(c);
    }

    StringBuilder result = new StringBuilder();
    for (int i = sb.length() - 1; i >= 0; i--) {
        if (sb.charAt(i) == '(' && open-- > 0) continue;
        result.append(sb.charAt(i));
    }
    return result.reverse().toString();
}

The intuition is counting the number of invalid ( and removing the invalid ) in the first pass.
If there are open number of invalid ( left, we just need to remove them from the end in the second pass.

Run time: $O(n)$, space: $O(n)$

public String minRemoveToMakeValid(String s) {
    String input = s;
    char[] p = new char[]{'(',')'};
    int l = 0;
    StringBuilder sb = new StringBuilder();
    for (int i =0; i<input.length(); i++) {
        if (input.charAt(i) == p[0]) {
            l++;
        } else if (input.charAt(i) == p[1]) {
            l--;
        }
        if (l<0) {
            l++;
        } else {
            sb.append(input.charAt(i));
        }
    }
    if (l != 0) {
        return new StringBuilder(minRemoveToMakeValid(sb.reverse().toString(), new char[]{')', '('})).reverse().toString();
    }
    return sb.toString();
}

1247. Minimum Swaps to Make Strings Equal

public int minimumSwap(String s1, String s2) {
    int n1 = s1.length(), n2 = s2.length();
    if(n1 != n2) return -1;
    int count1 = 0, count2 = 0;
    
    for(int i = 0; i < n1; i++){
        if(s1.charAt(i) != s2.charAt(i)){
            if(s1.charAt(i) == 'x') count1 ++;
            else count2 ++;
        }
    }
    if((count1 + count2) % 2 == 1) return -1;
    
    int ans = 0;
    ans += count1/2 + count2/2;
    if(count1 % 2 == 0) return ans;
    
    return ans + 2;
}

Count the number of x-y and y-x pairs separately
Also check if the total number of x and total number of y is even or not
Answer: half num of x-y + half num of y-x+ 1 if x-y is odd + 1 if y-x is odd

Run time: $O(n)$, space: $O(1)$

public int minimumSwap(String s1, String s2) {
    if(s1.length() != s2.length()) return -1;
    if(s1.equals(s2)) return 0;
    int[] a = new int[2];
    int[] swap = new int[2];
    for(int i = 0; i < s1.length(); i++){
        char c1 = s1.charAt(i), c2 = s2.charAt(i);
        if(c1 == 'x') a[0]++;
        else if (c1 == 'y') a[1]++;
        else return -1;
        
        if(c2 == 'x') a[0]++;
        else if (c2 == 'y') a[1]++;
        else return -1;
        
        if(c1 == 'x' && c2 == 'y') swap[0]++;
        else if(c1 == 'y' && c2 == 'x') swap[1]++;
    }
    if(a[0] % 2 == 1 || a[1] % 2 == 1) return -1;

    return swap[0]/2+swap[1]/2+swap[0]%2+swap[1]%2;
}

5. Longest Palindromic Substring (M)

Helper method to find the current longest substring (2 cases)

Run time: $O(n^2)$, space: $O(n)$

    public String longestPalindrome(String s) {
        String max = "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = extend(s, i, i), s2 = extend(s, i, i + 1);
            if (s1.length() > max.length()) max = s1;
            if (s2.length() > max.length()) max = s2;
        }
        return max;
    }
    
    private String extend(String s, int i, int j) {
        while (0 <= i && j < s.length()) {
            if (s.charAt(i) != s.charAt(j)) break;
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
}

Stupid recursive way written by myself

public String longestPalindrome(String s) {
    String ans = "";
    for(int i = 0; i < s.length(); i++){
        String temp = s.substring(i,i+1);
       for(int j = s.length() -1; j>=i; j--){
            if(isPalin(s,i,j)) temp = s.substring(i,j+1);
            if(ans.length() < temp.length()) ans = temp;
        } 
    }
    return ans;
}
public boolean isPalin(String a, int lo, int hi){
    if(lo == hi)
        return true;
    } else if(lo +1 == hi){
        if(a.charAt(lo) == a.charAt(hi)) return true;
        else return false;
    } else{
        return a.charAt(lo) == a.charAt(hi) && isPalin(a,lo+1,hi-1);
    }
}

32. Longest Valid Parentheses

Use stack to record the starting index for a possible sequence of valid parentheses
Push the index when there’s no match, otherwise pop the element and update the max length

Run time: $O(n)$, space: $O(n)$

public int longestValidParentheses(String s) {
    LinkedList<Integer> stack = new LinkedList<>();
    int result = 0;
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
            stack.pop();
            result = Math.max(result, i - stack.peek());
        } else {
            stack.push(i);
        }
    }
    return result;
}

224. Basic Calculator

Use stack to store the value and sign
If it is digit, then continue checking if there’s other digits, then compute the result and add to the result
If it is +/-, set the sign variable to be 1/-1.
If it is (, push the result and current sign to the stack, and reset result and sign
If it is ), compute the result. The first popped element will be sign, the next one will be result

Run time: $O(n)$, space: $O(n)$

   public int calculate(String s) {
int len = s.length(), sign = 1, result = 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < len; i++) {
	if (Character.isDigit(s.charAt(i))) {
		int sum = s.charAt(i) - '0';
		while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
			sum = sum * 10 + s.charAt(i + 1) - '0';
			i++;
		}
		result += sum * sign;
	} else if (s.charAt(i) == '+') sign = 1;
	else if (s.charAt(i) == '-') sign = -1;
	else if (s.charAt(i) == '(') {
		stack.push(result);
		stack.push(sign);
		result = 0;
		sign = 1;
	} else if (s.charAt(i) == ')') {
		result = result * stack.pop() + stack.pop();
	}

}
return result;

273. Integer to English Words

List possible formats: less than ten, twenty, hundred, thousand, million, billion
Then list the general string cases for less than ten, twenty, hundred
Check edge case when input is 0
Helper function to recursive translate number from largest digit to smallest digit, trim in the end

Run time: $O(n)$, space: $O(n)$

    private final String[] below10 = new String[]{"", "One", "Two", "Three", 
                                                  "Four", "Five", "Six", "Seven", 
                                                 "Eight", "Nine"};
    private final String[] below20 = new String[]{"Ten", "Eleven", "Twelve", "Thirteen", 
                                                  "Fourteen", "Fifteen", "Sixteen", "Seventeen", 
                                                 "Eighteen", "Nineteen"};
    private final String[] below100 = new String[]{"", "Ten", "Twenty", "Thirty", "Forty", 
                                                   "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        
    public String numberToWords(int num) {
        if(num == 0) return "Zero";
        return helper(num);
    }
    
    public String helper(int num){
        String result = new String();
        if (num < 10) result = below10[num];
        else if (num < 20) result = below20[num-10];
        else if (num < 100) result = below100[num/10]+" "+helper(num%10);
        else if (num < 1000) result = helper(num/100)+" Hundred "+helper(num%100);
        else if (num < 1000000) result = helper(num/1000)+" Thousand "+helper(num%1000);
        else if (num < 1000000000) result = helper(num/1000000)+" Million "+helper(num%1000000);
        else result = helper(num/1000000000)+" Billion "+helper(num%1000000000);
        return result.trim(); // delete extra space
    }
}

67. Add Binary

Use one while loop to get the sum of each digit (if applicable) and carry-in
Mod 2 and appended, divided by 2 and stored to carry-in
At last, if carry-in is 1, append it, and reverse and to string

Run time: $O(n)$, space: $O(n)$

public String addBinary(String a, String b) {
    // String ans = "";
    StringBuilder sb = new StringBuilder();
    int ptr1 = a.length()-1, ptr2 = b.length()-1;
    int carryin = 0;
    while(ptr1 >= 0 || ptr2 >= 0){
        int sum = carryin;
        if(ptr2 >= 0) sum += b.charAt(ptr2--)-'0';
        if(ptr1 >= 0) sum += a.charAt(ptr1--)-'0';
        sb.append(sum % 2);
        carryin = sum / 2;
    }
    if(carryin != 0) sb.append(carryin);
    return sb.reverse().toString();
}

125. Valid Palindrome (M)

Use while loop to skip non-letter or non-digit

Run time: $O(n)$, space: $O(1)$

    int start = 0; 
    int end = s.length() - 1;
    while(start <= end) {
        while(start <= end && !Character.isLetterOrDigit(s.charAt(start))) {
            start++;
        }
        while(start <= end && !Character.isLetterOrDigit(s.charAt(end))) {
            end--;
        }
        if(start <= end && Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

68. Text Justification

Walk through each word, if current row is empty, then add it
else if there is enough space for this word with a space, append space and add this word
otherwise, adjust the space in the line, add this line to answer, create a new line
In the end, adjust the last line and add to the answer
Run time: $O(n)$, space: $O(n)$

public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> ans = new ArrayList<>();
    if (words.length == 0) return ans; // check empty
    
    StringBuilder cur = new StringBuilder();
    for (int i = 0; i < words.length; i++) {
        String w = words[i];
        if (cur.length() == 0) { // first word in the line
            cur.append(w);
        } else if (maxWidth - cur.length() >= w.length() + 1) {
            cur.append(' ').append(w); // can fit this word
        } else {
            format(cur, maxWidth, false); // fix current line
            ans.add(cur.toString());
            cur.setLength(0); // new line
            i--; // go back to the same word
        }
    }
    
    format(cur, maxWidth, true);
    ans.add(cur.toString());
    
    return ans;
}

private void format(StringBuilder cur, int maxWidth,  boolean leftJustify) {
    boolean hasSpace = false;
    for (int i = 0; i < cur.length(); i++) {
        if (cur.charAt(i) == ' ') {
            hasSpace = true;
            break;
        }
    }
    
    if (leftJustify || !hasSpace) { // last line
        while (cur.length() < maxWidth) cur.append(' '); // add space
    } else {
        int si = 1;
        while (cur.length() < maxWidth) {
            while (cur.charAt(si) != ' ' || cur.charAt(si-1) == ' ') {
                si++;
                if (si == cur.length()) si = 1;
            } 
            cur.insert(si, ' ');
            if(si == cur.length()) si = 1;
            else si++;
            // si = si == curr.length() ? 1 : si+1;
        }                        
    }
}

3. Longest Substring Without Repeating Characters

More efficient way!
Run time: $O(n)$, space: $O(n)$

public int lengthOfLongestSubstring(String s) {
    // sanity check
    if (s == null || s.length() == 0) return 0;
    char[] chars = s.toCharArray();
    int[] counts = new int[256];
    int begin = 0, maxLen = 1;
    for (int i = 0; i < chars.length; ++i) {
        counts[chars[i]]++;
        if (counts[chars[i]] == 2) {
            while (begin < i && counts[chars[i]] == 2) counts[chars[begin++]]--;
        }
        maxLen = Math.max(i-begin+1, maxLen);
    }
    return maxLen;
}

Find the max length starting with each char in the string
Run time: $O(n^2)$, space: $O(n)$

public int lengthOfLongestSubstring(String s) {
    if(s.length() == 1) return 1;
    Map<Character, Integer> map;
    int max = 0;
    for(int i = 0; i < s.length(); i++){
        map = new HashMap<>();
        
        int j = i;
        while(j < s.length()){
            if(map.containsKey(s.charAt(j))) {
                max = Math.max(max, j-i);
                break;
            }
            else map.put(s.charAt(j), 0);
            j++;
        }
        if(j == s.length()) max = Math.max(max, j-i);
    }
    return max;
}

767. Reorganize String

Map to record occurrences, max heap to store Map.Entry and order the chars
Run time: $O(n\log n)$, space: $O(n)$

public String reorganizeString(String S) {
    StringBuilder res = new StringBuilder();
    Map<Character, Integer> hm = new HashMap<>();
    for (char c : S.toCharArray()) hm.put(c, hm.getOrDefault(c, 0) + 1);

    PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
    pq.addAll(hm.entrySet());
    Map.Entry<Character, Integer> prev = null;
    while (!pq.isEmpty()) {
        Map.Entry<Character, Integer> entry = pq.poll();
        if (prev != null && prev.getValue() > 0) pq.offer(prev);

        res.append((char) entry.getKey());
        entry.setValue(entry.getValue() - 1);
        prev = entry;
    }
    return (res.length() == S.length()) ? res.toString() : "";
}

844. Backspace String Compare

Use StringBuilder to add/delete char (setLength)
Run time: $O(n)$, space: $O(n)$

public boolean backspaceCompare(String S, String T) {
    String s = buildStr(S), t = buildStr(T);
    return s.equals(t);
}

String buildStr(String s){
    StringBuilder sbS = new StringBuilder();
    for(char c: s.toCharArray()){
        if(c == '#'){
            if(sbS.length() >= 1) sbS.setLength(sbS.length()-1);
        }
        else sbS.append(c);
    }
    return sbS.toString();
}

Two pointers
Run time: $O(n)$, space: $O(1)$

public boolean backspaceCompare(String S, String T) {
    int i = S.length()-1;
    int j = T.length()-1;
    int countS = 0;
    int countT = 0;
    while (i >= 0 || j >= 0) {
        while (i >= 0 && (countS > 0 || S.charAt(i) == '#')) {
            if (S.charAt(i) == '#') countS++;
            else countS--;
            i--;
        }
        char left = i < 0 ? '@' : S.charAt(i);
        while (j >= 0 && (countT > 0 || T.charAt(j) == '#')) {
            if (T.charAt(j) == '#') countT++;
            else countT--;
            j--;
        }
        char right = j < 0 ? '@' : T.charAt(j);
        if (left != right) return false;
        i--;
        j--;
    }
    return true;
}