[LeetCode] 721. Accounts Merge

 Problem : https://leetcode.com/problems/accounts-merge/

Use union-find to group email address of the same account.  Remember to sort the mail list in the end.

class UnionFind {
    int[] parent;
    
    UnionFind(int size) {
        parent = new int[size];
        
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    
    void union(int a, int b) {
        int ap = find(a);
        int bp = find(b);
        
        if (ap != bp) {
            parent[ap] = bp;
        }
    }
    
    int find(int a) {
        if (parent[a] == a) {
            return a;
        }
        
        parent[a] = find(parent[a]);
        
        return parent[a];
    }
}


class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int ID = 0;
        
        // convert mail to ids
        HashMap<String, Integer> mailIds = new HashMap();
        HashMap<Integer, String> idToMail = new HashMap();
        HashMap<String, Integer> mailToName = new HashMap();
        
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 1; j < accounts.get(i).size(); j++) {
                if (mailIds.containsKey(accounts.get(i).get(j))) {
                    continue;
                }
                
                mailIds.put(accounts.get(i).get(j), ID);
                idToMail.put(ID, accounts.get(i).get(j));
                ID++;
                mailToName.put(accounts.get(i).get(j), i);
            }    
        }
        
        // use union-find to group mail ids
        UnionFind uf = new UnionFind(ID);
        
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 2; j < accounts.get(i).size(); j++) {
                uf.union(mailIds.get(accounts.get(i).get(j-1)), mailIds.get(accounts.get(i).get(j)));        
            }
        }
        
        // construct the mail list
        HashMap<Integer, List<String>> groups = new HashMap();
        
        for (int i = 0; i < ID; i++) {
            String email = idToMail.get(i);
       
            if (groups.containsKey(uf.find(i))) {
                groups.get(uf.find(i)).add(email);
            } else {
                List<String> emailList = new ArrayList();
                emailList.add(email);
                groups.put(uf.find(i), emailList);
            }
        }
        
        List<List<String>> result = new ArrayList();
        for (int pid : groups.keySet()) {
            List<String> list = new ArrayList();
            
            // sort mails
            Collections.sort(groups.get(pid));
            String name = accounts.get(mailToName.get(idToMail.get(pid))).get(0);
            
            list.add(name);
            list.addAll(groups.get(pid));
            result.add(list);
        }
        
        return result;
    }
}

[LeetCode] 369. Plus One Linked List

 Problem : https://leetcode.com/problems/plus-one-linked-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        // reverse list
        ListNode reversed = reverse(head);
        
        int carry = 1;    
        ListNode p = reversed;
        ListNode last = null;
        
        while(p != null) {
            int total = p.val + carry;
            p.val = total % 10;
            carry = total / 10;
            last = p;
            p = p.next;
        }
        
        if (carry != 0) {
            last.next = new ListNode(carry);
        }
        
        
        return reverse(reversed);
    }
    
    ListNode reverse(ListNode head) {
        ListNode last = null;
        ListNode current = head;
        ListNode next = head.next;
        
        while (next != null) {
            current.next = last;
            last = current;
            current = next;
            next = current.next;
        }
        
        // remember to link the last element!
        current.next = last;
        return current;
    }
}

[LeetCode] 647. Palindromic Substrings

 Problem: https://leetcode.com/problems/palindromic-substrings/

class Solution {
    public int countSubstrings(String s) {
        int N = s.length();
        
        boolean[][] dp = new boolean[N][N];
        int result = 0;
        
        for (int i= N-1; i >= 0; i--) {
            for (int j = N-1; j >= i; j--) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1]);
                if (dp[i][j]) {
                    result += 1;
                }
            }
        }
        
        return result;
    }
}

[LeetCode] 450. Delete Node in a BST

 Problem : https://leetcode.com/problems/delete-node-in-a-bst/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) { 
        if (root == null) {
            return root;
        }
        
        // delete node from left sub-tree
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        
        // delete node from right sub-tree
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        
        // root.val == key
        if (root.left == null) {
            return root.right;
        }
        
        if (root.right == null) {
            return root.left;
        }
        
        // use right node as the new root
        TreeNode newRoot = root.right;
        
        // Because all nodes in right sub-tree are larger than current root node,
        // and left child is less than current root node, 
        // then the left child must be the smallest value comparing to the right sub-tree.
        // Attach current left child to the most left node of the right sub-tree.
        TreeNode p = root.right;
        while (p.left != null) {
            p = p.left;
        }
        
        p.left = root.left;
        
        return newRoot;
    }
}

[LeetCode] 448. Find All Numbers Disappeared in an Array

 Problem : https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Because all numbers in the array is in the range [1, n].  If all numbers exist in the array, we can always swap the numbers to make nums[i] = i + 1.

So try to swap the number to its correct position. Then iterate the array to find the missing number which nums[i] != i + 1

class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<int> {
        for (i in 0 until nums.size) {
            while (nums[i] != i+1) {
                if (nums[nums[i] - 1] == nums[i]) {
                    break
                }
                
                val tmp = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = tmp
            }
        }
        
        val result = mutableListOf<int>()
        
        for (i in 0 until nums.size) {
            if (nums[i] != i + 1) {
                result.add(i+1)
            }
        }
        
        return result
    }
}

[LeetCode] 739. Daily Temperatures

 Problem : https://leetcode.com/problems/daily-temperatures/

Use monotonic stack to keep a decreasing sequence.

class Solution {
    fun dailyTemperatures(temperatures: IntArray): IntArray {
        val stack = Stack<int>()
        val result = IntArray(temperatures.size) { 0 }
        
        for (i in 0 until temperatures.size) {
            // pop all the days which temperature is lower than current day
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                val last = stack.pop()
                result[last] = i - last 
            }
            
            stack.push(i)
        }
        
        return result
    }
}

[LeetCode] 1014. Best Sightseeing Pair

 Problem : https://leetcode.com/problems/best-sightseeing-pair/

Keep tracking the maximum score we encountered. Decrease the maximum score while iterating to right side.

class Solution {
    fun maxScoreSightseeingPair(values: IntArray): Int {
        var mxScore = values[0]
        var result = 0
        
        for (i in 1 until values.size) {
            mxScore -= 1
            
            result = maxOf(result, values[i] + mxScore)    
            mxScore = maxOf(mxScore, values[i])
        }
        
        return result
    }
}

[LeetCode] 1567. Maximum Length of Subarray With Positive Product

 Problem : https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

Positive A * Positive B -> Positive C

Negative A * Negative B -> Positive C

Keep tracking positive and negative product result sub-array length end by current number. 

Reset sub-array length when encounter '0'

class Solution {
    fun getMaxLen(nums: IntArray): Int {
        var positiveSoFar = 0
        var negativeSoFar = 0
        var result = 0
        
        for (n in nums) {
            if (n > 0) {
                positiveSoFar += 1
                negativeSoFar = if (negativeSoFar > 0) negativeSoFar + 1 else 0
            } else if (n < 0) {
                val prePositiveSoFar = positiveSoFar
                positiveSoFar = if (negativeSoFar > 0 ) negativeSoFar + 1 else 0
                negativeSoFar = prePositiveSoFar + 1
                
            } else {
                positiveSoFar = 0
                negativeSoFar = 0
            }
            
            result = maxOf(result, positiveSoFar)
        }
        
        return result
    }
}

[LeetCode] 918. Maximum Sum Circular Subarray

 Problem : https://leetcode.com/problems/maximum-sum-circular-subarray/

In a circular integer, the maximum sum of sub-array can exists in 2 parts:

AAABBBBA'A'A'

It may either exist in the contiguous sub-array [BBBB] or exists in the sub-array [A'A'A'AAA] which combined by the front and rear sub-arrays. 

It is easy to get maximum value of [BBBB].

The maximum value of [A'A'A'AAA] = total value - minimum value of [BBBB]

When the maximum value of [BBBB] <= 0, all numbers in the given array must <= 0.

The the total value == minimum 

The maximum sum of sub-array can only exist in [BBBB].

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        // maximum value of contiguous sub-array
        var mx = nums[0]
        var mxSoFar = nums[0]
        
        // minimum value of contiguous sub-array
        var mi = nums[0]
        var miSoFar = nums[0]
        
        for (i in 1 until nums.size) {
            mxSoFar = maxOf(mxSoFar + nums[i], nums[i])
            mx = maxOf(mx, mxSoFar)
            
            miSoFar = minOf(miSoFar + nums[i], nums[i])
            mi = minOf(mi, miSoFar)
        }
        
        // if mx > 0 :
        //     the maximum value either exists in one contiguous sub-array
        //     or existis in the combination of the front sub-array 
        //     and rear sub-array (= total - miSoFar)
        // if mx <= 0 :
        //     all numbers in the input array <= 0.
        //     mx is the maximum sum of sub-array 
        return if (mx > 0) maxOf(mx, nums.sum() - mi) else mx 
        
    }
}

[LeetCode] 1413. Minimum Value to Get Positive Step by Step Sum

 Problem : https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/

Assume x is a valid start value, then x + 1 is also a start value.

Assume x is an invalid start value, then x - 1 is also a invalid start value.

So there is a contiguous valid start value section. We can use binary search to find the lower bound of the section.

class Solution {
    fun minStartValue(nums: IntArray): Int {
    
        fun isValid(x: Int): Boolean {
            var prefixSum = x
            
            nums.forEach {
                prefixSum += it
                if (prefixSum < 1) {
                    return false
                }
            }
            
            return true
        }
        
        // valid start value section [1, nums.size * 100 + 1]
        // 1 -> when all numbers in the array equal to 0
        // nums.size * 100 + 1 -> when all numbers in the array equal to -100
        
        var left = 1
        var right = nums.size * 100 + 1
        
        while (left < right) {
            val mid = left + (right - left) / 2
            
            if (isValid(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
            
        }
        
        return right
    }
}

[LeetCode] 766. Toeplitz Matrix

 Problem : https://leetcode.com/problems/toeplitz-matrix/

No need to travel diagonally. Only need to check if number of one position equals to the number on its bottom-right position.

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        for y in range(ROW-1):
            for x in range(COLUMN-1):
                if matrix[y][x] != matrix[y+1][x+1]:
                    return False
                
        return True

The one liner solution:

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        return all(matrix[y][x] == matrix[y+1][x+1] for y in range(ROW-1) for x in range(COLUMN-1))

[LeetCode] 404. Sum of Left Leaves

 Problem : https://leetcode.com/problems/sum-of-left-leaves/

Use post-order traversal to accumulate left leave values.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        
        self.result = 0
        
        def postorder(node):
            if not node.left and not node.right:
                # find a leaf
                return True
            
            if node.left and postorder(node.left):
                # find a left leaf
                self.result += node.left.val
            
            if node.right:
                postorder(node.right)
            
            return False
        
        postorder(root)
        return self.result

[LeetCode] 441. Arranging Coins

 Problem : https://leetcode.com/problems/arranging-coins/

Because 1 + 2 + 3 + ... + n = n * (n+1) / 2,  we can use binary search to find the answer.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        
        # the possible result range = [left, right)
        left, right = 1, n + 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            # total coions = mid * (mid + 1) / 2
            if mid *(mid+1)//2 <= n:
                left = mid + 1
            else:
                right = mid 
        
        return left - 1

[LeetCode] 430. Flatten a Multilevel Doubly Linked List

 Problem : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

 Use stack to mimic DFS

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head: return None
        
        dummy = Node()
        p = dummy
        
        stack = [head]
        
        while stack:
            h = stack.pop()
            
            while h:
                p.next = h
                h.prev = p
                p = p.next
                    
                if h.child:
                    if h.next:
                        stack.append(h.next)
                    
                    tmp = h.child
                    h.child = None
                    h = tmp
                else:
                    h = h.next
                
        
        dummy.next.prev = None
        return dummy.next