LeetCode 1-100

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[] {};
        }
        
        int[] result = new int[2];

        // <Element, Index>
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[0] = i;
                result[1] = map.get(target - nums[i]);
                return result;
            }
            map.put(nums[i], i);
        }
        
        return result;
    }
}

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode dummyHead = new ListNode(0); // dummy head of new list
        ListNode cur = dummyHead; // traverse new list

        int carry = 0;

        // still have digits
        while (l1 != null || l2 != null || carry != 0) {
            int val = 0;

            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;

            val = (val1 + val2 + carry) % 10;
            carry = (val1 + val2 + carry) / 10;
            
            // insert a new node
            cur.next = new ListNode(val); 
            cur = cur.next;

            // move pointers forward
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        
        return dummyHead.next;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        
        char[] array = s.toCharArray();

        int begin, end = 0; // two pointers to mark the longest substring
        int result = 0; // longest substring's length
        
        int[] map = new int[128]; // <Character, Index>
        Arrays.fill(map, -1);

        for (begin = 0, end = 0; end < s.length(); end++) {
            char currentChar = array[end];
            
            // if this is a repeating character, we either reset begin index to last appearance index + 1 to avoid duplicate
            // or remains unchanged. It is possible that [map[currentChar] + 1, begin] contains duplicate characters
            if (map[currentChar] >= 0) {
                begin = Math.max(begin, map[currentChar] + 1);
            }
            
            // update current character's last position index
            map[currentChar] = end;
            
            // update result
            result = Math.max(result, end - begin + 1);
        }
        return result;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        
        // make sure nums2 is the smaller array
        if (m < n) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int low = 0, high = n * 2;
        while (low <= high) {
            int cut2 = (low + high) / 2;
            int cut1 = m + n - cut2;

            // avoid boundary exception
            double L1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[(cut1-1)/2];
            double L2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[(cut2-1)/2];
            double R1 = (cut1 == m * 2) ? Integer.MAX_VALUE : nums1[(cut1)/2];
            double R2 = (cut2 == n * 2) ? Integer.MAX_VALUE : nums2[(cut2)/2];

            if (L1 > R2) {
                // nums1's lower half is too big; need to move C1 left (C2 right)
                low = cut2 + 1;
            } else if (L2 > R1) {
                // nums2's lower half too big; need to move C2 left.
                high = cut2 - 1;
            } else {
                // Otherwise, that's the right cut.
                return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
            }
        }
        return -1;
    }
}

class Solution {
    private int startIndex = 0, maxLen = 0;
    
    private void checkPalindrome(char[] array, int left, int right) {
        while (left >= 0 && right <= array.length - 1 && array[left] == array[right]) {
            left--;
            right++;
        }

        // update maxLen = (right - 1) - (left + 1) + 1 = right - left - 1
        if (maxLen < right - left - 1) {
            maxLen = right - left - 1;
            startIndex = left + 1;
        }
    }

    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }

        char[] array = s.toCharArray();
        for (int i = 0; i < array.length - 1; i++) {
            checkPalindrome(array, i, i); // assume odd length
            checkPalindrome(array, i, i+1); // assume even length
        }
        
        return s.substring(startIndex, startIndex + maxLen);
    }
}

class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();

        // every row is a StringBuilder
        StringBuilder[] sb = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            sb[i] = new StringBuilder();
        }

        // index to traverse the whole string
        int index = 0;
        while (index < len) {
            // vertically down
            for (int i = 0; i < numRows && index < len; i++) {
                sb[i].append(s.charAt(index++));
            }
            
            // obliquely up (not include the first and last row)
            for (int i = numRows - 2; i >= 1 && index < len; i--) {
                sb[i].append(s.charAt(index++));
            }
        }

        // append all rows of result
        for (int i = 1; i < numRows; i++) {
            sb[0].append(sb[i]);
        }
        
        return sb[0].toString();
    }
}

class Solution {
    public int reverse(int x) {
        long result = 0;

        while (x != 0) {
            // obtain the last bit
            result = result * 10 + x % 10; 
            x /= 10;
            
            // overflow check
            if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
                return 0;
            }
        }

        return (int)result;
    }
}

class Solution {
    public int myAtoi(String str) {
        // trim leading blank space
        str = str.trim();
        if (str.length() == 0) {
            return 0;
        }

        // detect sign
        char firstChar = str.charAt(0);
        int sign = 1;
        int digitStart = 0; // default no sign char, thus digit start from index 0
        if (firstChar == '+' || firstChar == '-') {
            sign = (firstChar == '+') ? 1 : -1;
            digitStart++;
        }

        // add digits
        long sum = 0;
        for (int i = digitStart; i < str.length(); i++) {
            char current = str.charAt(i);

            // non-digit, return sum immediately
            if (current < '0' || current > '9') {
                return (int)sum * sign;
            }
            
            // continue adding current digit
            sum = sum * 10 + current - '0';

            // overflow checking
            if (sign == 1 && sum > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            if (sign == -1 && -sum < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
        }
        return (int)sum * sign;
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        // exclude negative number and 10's multiple
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        int result = 0;
        
        // only need to reverse half of all digits
        while (x > result) {
            result = result * 10 + x % 10;
            x /= 10;
        }
        
        // odd or even length
        return (x == result || x == result / 10); 
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        
        // s and p are both empty, so they can match
        dp[0][0] = true;

        // pattern cannot start with '*'
        if (p.length() > 0 && p.charAt(0) == '*') {
            return false;
        }

        // '*' match
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == '*' && dp[0][j-1]) {
                dp[0][j+1] = true;
            }
        }
    
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                // regular matching, or '.' matching
                if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                    dp[i+1][j+1] = dp[i][j];    
                } else if (p.charAt(j) == '*') {
                    // * can only be matched as empty char
                    if (s.charAt(i) != p.charAt(j-1)) {
                        dp[i+1][j+1] = dp[i+1][j-1];
                    }
                    
                    // * can be matched as 0, 1 or multiple chars
                    if (s.charAt(i) == p.charAt(j-1) || p.charAt(j-1) == '.') {
                        dp[i+1][j+1] = dp[i+1][j-1] || dp[i+1][j] || dp[i][j+1]; 
                    }
                }
            }
        }
        
        return dp[s.length()][p.length()];
    }
}

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int result = 0, current = 0; // max area, current area

        while (left < right) {
            current = (right - left) * Math.min(height[left], height[right]);
            result = Math.max(result, current);

            // keep the higher edge, and try to increase the other edge
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }
}

class Solution {
    public String intToRoman(int num) {
        int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < value.length; i++) {
            while (num >= value[i]) {
                sb.append(roman[i]);
                num = num - value[i];
            }
        }
        
        return sb.toString();
    }
}

class Solution {
    public int romanToInt(String s) {
        if (s.length() == 0) {
            return 0;
        }

        int i = 0;
        int len = s.length();
        int result = 0;

        while (i < len) {
            char c = s.charAt(i); // current character
            char nextChar = '.'; // if there is a next character
            if (i != len - 1) {
                nextChar = s.charAt(i+1);
            }

            // need to check IV and IX
            if (c == 'I') {
                if (nextChar == 'V') {
                    result += 4;
                    i += 2;
                } else if (nextChar == 'X') {
                    result += 9;
                    i += 2;
                } else {
                    result += 1;
                    i += 1;
                }
            }

            else if (c == 'V') {
                result += 5;
                i += 1;
            }

            // need to check XL and XC
            else if (c == 'X') {
                if (nextChar == 'L') {
                    result += 40;
                    i += 2;
                } else if (nextChar == 'C') {
                    result += 90;
                    i += 2;
                } else {
                    result += 10;
                    i += 1;
                }
            }

            else if (c == 'L') {
                result += 50;
                i += 1;
            }

            // need to check CD and CM
            else if (c == 'C') {
                if (nextChar == 'D') {
                    result += 400;
                    i += 2;
                } else if (nextChar == 'M') {
                    result += 900;
                    i += 2;
                } else {
                    result += 100;
                    i += 1;
                }
            }

            else if (c == 'D') {
                result += 500;
                i += 1;
            }

            else if (c == 'M') {
                result += 1000;
                i += 1;
            }
        }
        return result;
    }
}

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        // initialized as the first word of strs
        String result = strs[0];

        for (int i = 0; i < strs.length; i++) {
            // keeps removing the last character until matching the common prefix requirement
            while (strs[i].indexOf(result) != 0) {
                result = result.substring(0, result.length() - 1);
                if (result.length() == 0) {
                    break;
                }
            }
        }
            
        return result;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        
        int len = nums.length;
        if (len < 3) {
            return result;
        }

        // sort so we can use pointers to quickly sum
        Arrays.sort(nums); 
        
        // skip impossible cases
        if (3 * nums[0] > 0 || 3 * nums[len - 1] < 0) {
            return result;
        }

        for (int first = 0; first < len - 2; first++) {
            // skip if nums[first] is duplicate
            if (first > 0 && nums[first] == nums[first-1]) {
                continue; 
            }
            
            // too big, no need to check subsequent combinations
            if (3 * nums[first] > 0) {
                break; 
            }
            
            // too small, we need to start from a larger nums[first]
            if (nums[first] + 2 * nums[len - 1] < 0) {
                continue;
            }

            int second = first + 1, third = len - 1;
            while (second < third) {
                if (nums[first] + nums[second] + nums[third] == 0) {
                    result.add(Arrays.asList(nums[first], nums[second], nums[third]));

                    // skip nums[second] and nums[third] duplicates
                    while (second < third && nums[second] == nums[second + 1]) {
                        second++;
                    }
                    while (third > second && nums[third] == nums[third - 1]) {
                        third--;
                    }

                    // move pointers
                    second++;
                    third--;
                } else if (nums[first] + nums[second] + nums[third] < 0) {
                    second++;
                } else {
                    third--;
                }
            }
        }
        return result;
    }
}

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int result = 0;

        // less than three numbers, directly return all num's sum
        if (len <= 3) {
            for (int num : nums) {
                result += num;
            }
            return result;
        }

        // initialized as the sum of first three elements
        result = nums[0] + nums[1] + nums[2];
        
        // sort so we can use pointers to quickly sum
        Arrays.sort(nums);

        for (int first = 0; first < len - 2; first++) {
            // skip if nums[first] is duplicate
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }

            int second = first + 1, third = len - 1;
            while (second < third) {
                int tempSum = nums[first] + nums[second] + nums[third];
                
                // determine if tempSum is equal to target, or try to get tempSum closer to target
                if (tempSum == target) {
                    return tempSum;
                } else if (tempSum < target) {
                    second++;
                } else {
                    third--;
                }

                // update result
                if (Math.abs(target - result) > Math.abs(target - tempSum)) {
                    result = tempSum;
                }
            }
        }
        
        return result;
    }
}

class Solution {
    private List<String> result = new ArrayList<>();
    private final String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return result;
        }
        
        backtrack(new StringBuilder(), digits, 0);
        
        return result;
    }
    
    private void backtrack(StringBuilder current, String digits, int index) {
        // find a combination, add to result
        if (current.length() == digits.length()) {
            result.add(current.toString());
            return;
        }
        
        // get all possible letters that are matching with current digit
        int digit = digits.charAt(index) - '0';
        String letters = mapping[digit];
        
        for (char letter: letters.toCharArray()) {
            current.append(letter);
            backtrack(current, digits, index + 1);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int len = nums.length;
        if (len < 4) {
            return result;
        }

        // sort so we can use pointers to quickly sum
        Arrays.sort(nums);
        
        // too big or small
        Long potentialMin = (long)4 * nums[0];
        if (potentialMin > target) {
            return result;
        }
        
        Long potentialMax = (long)4 * nums[len - 1];
        if (potentialMax < target) {
            return result;
        }

        for (int first = 0; first < len - 3; first++) {
            // skip if nums[first] is duplicate
            if (first > 0 && nums[first] == nums[first-1]) {
                continue;
            }
            
            // too big, no need to check subsequent combinations
            Long potentialRestFourMin = (long)4 * nums[first];
            if (potentialRestFourMin > target) {
                break;
            }
            
            // too small, we need to start from a larger nums[first]
            Long potentialRestThreeMax = (long)3 * nums[len - 1];
            if (nums[first] + potentialRestThreeMax < target) {
                continue;
            }

            for (int second = first + 1; second < len - 2; second++) {
                // skip if nums[first] is duplicate
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                
                // too big, no need to check subsequent combinations
                Long potentialRestThreeMin = (long)3 * nums[second];
                if (potentialRestThreeMin + nums[first] > target) {
                    break;
                }
                
                // too small, we need to start from a larger nums[second]
                if (nums[first] + nums[second] + 2 * nums[len - 1] < target) {
                    continue;
                }

                int third = second + 1, fourth = len - 1;
                while (third < fourth) {
                    if (nums[first] + nums[second] + nums[third] + nums[fourth] == target) {
                        result.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth]));
                        
                        // skip duplicates
                        while (second < len - 2 && nums[second] == nums[second + 1]) {
                            second++;
                        }
                        while (third < fourth && nums[third] == nums[third + 1]) {
                            third++;
                        }
                        while (third < fourth && nums[fourth] == nums[fourth - 1]) {
                            fourth--;
                        }

                        // move pointers
                        third++;
                        fourth--;
                    } else if (nums[first] + nums[second] + nums[third] + nums[fourth] < target) {
                        third++;
                    } else {
                        fourth--;
                    }
                }
            }
        }
        return result;
    }
}

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        
        // slow and fast pointers
        ListNode slow = dummyHead, fast = dummyHead;

        // fast moves n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // move slow and fast together
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // delete nth node
        slow.next = slow.next.next;

        return dummyHead.next;
    }
}

class Solution {
    public boolean isValid(String s) {
        if (s.length() == 0) {
            return true;
        }

        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // push all left parentheses into stack
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                // current right parenthesis must match with top parenthesis in the stack
                if (st.size() == 0) {
                    return false;
                }

                if (c == ')' && st.peek() != '(') {
                    return false;
                } else if (c == ']' && st.peek() != '[') {
                    return false;
                } else if (c == '}' && st.peek() != '{') {
                    return false;
                } else {
                    // successfully matched, pop the top parenthesis
                    st.pop();
                }
            }
        }
        return st.isEmpty();
    }
}

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        // merge after smaller node
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;

        while (l1 != null && l2 != null) {
            // decide which element to be added to the result list
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        
        // one list reaches the end, add the rest list elements to result
        cur.next = (l2 == null) ? l1 : l2;
        
        return dummyHead.next;
    }
}

class Solution {
    List<String> result = new ArrayList<>();
    
    public List<String> generateParenthesis(int n) {
        generate("", 0, 0, n);
        return result;
    }

    // left: left parentheses' count
    // right: right parentheses' count
    private void generate(String s, int left, int right, int n) {
        if (right == n) {
            // finish construction
            result.add(s); 
        } else {
            // always prefer to generate left parenthesis first
            if (left < n) {
                generate(s + "(", left + 1, right, n);
            }
            
            // left is greater than right, then generate a right parenthesis
            if (left > right) {
                generate(s + ")", left, right + 1, n);
            }
        }
    }
}

/**
 * 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 mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        // override priority queue's comparator in ascending order
        Queue<ListNode> pq = new PriorityQueue<>((ListNode l1, ListNode l2) -> {
            return l1.val - l2.val;
        });

        // add each list's head (smallest) node into the priority queue
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }

        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;

        while (!pq.isEmpty()) {
            // pick out the smallest element from priority queue
            ListNode currentHead = pq.poll();
            cur.next = currentHead;
            cur = cur.next;

            // add its next element into the queue
            if (cur.next != null) {
                pq.offer(cur.next);
            }
        }
        
        return dummyHead.next;
    }
}

/**
 * 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 mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        // invalid interval
        if (l > r) {
            return null; 
        }
        
        // interval only has one list group
        if (l == r) {
            return lists[l]; 
        }

        // divide k lists into two groups
        int mid = l + (r - l) / 2;
        ListNode left = merge(lists, l, mid);
        ListNode right = merge(lists, mid + 1, r);

        // merge two "big" lists together
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        
        while (left != null || right != null) {
            // right list is null, or the head of left list is smaller than the one of right list
            if (right == null || (left != null && left.val < right.val)) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        
        return dummyHead.next;
    }
}

/**
 * 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 swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // previous second node now bcomes the head node
        ListNode newHead = head.next; 

        // regard all other nodes as an entity, and the head of this entity is head.next.next
        head.next = swapPairs(head.next.next); 

        // previous head node now becomes the second node
        newHead.next = head;

        return newHead;
    }
}

/**
 * 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 reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        // move cur k nodes forward
        ListNode cur = head;
        int count = 0;
        while (cur != null && count != k) {
            count++;
            cur = cur.next;
        }

        // we get k nodes in a group now
        if (count == k) {
            // recursively complete all other nodes first to get the modified sub-list
            cur = reverseKGroup(cur, k);

            // reverse k nodes
            while (count-- > 0) {
                // get the second element among k nodes
                ListNode second = head.next;
                
                // current first element (head) will point to the modified sub-list 
                head.next = cur;

                // previous head has become the head of the modified sub-list
                cur = head;
                
                // previous second element now becomes the new head of the un-reversed part
                head = second; 
            }
            
            // after reverse, the head of the modified sub-list is actually the head of the whole list
            head = cur;
        }
        
        return head;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return len;
        }

        int result = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[result] = nums[i]; // in-place modification
                result++;
            }
        }
            
        return result;
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;

        int result = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                nums[result] = nums[i]; // in-place modification
                result++;
            }
        }
            
        return result;
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
        int hLen = haystack.length(), nLen = needle.length();
        
        // needle is an empty string
        if (nLen == 0) {
            return 0; 
        }
        
        // haystack is empty and impossible to contain needle
        if (hLen == 0) {
            return -1; 
        }

        for (int i = 0; i <= hLen - nLen; i++) {
            // current char is equal to needle's first char & substring is equal to needle
            if (haystack.charAt(i) == needle.charAt(0) && haystack.substring(i, i + nLen).equals(needle)) {
                return i;
            }
        }

        return -1;
    }
}

class Solution {
    public int divide(int dividend, int divisor) {
        // corner case
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        
        long dividendCopy = (long)dividend, divisorCopy = (long)divisor;

        // get rid of sign 
        long a = Math.abs(dividendCopy), b = Math.abs(divisorCopy);
        long result = 0;

        while (a >= b) {
            int x = 0;

            // count how many divisor does the dividend "has"
            while (a >= (b << 1 << x)) {
                x++;
            }
            
            result += 1 << x;
            a -= b << x;
        }

        // determine if dividend and divisor have same sign
        return (dividend > 0) == (divisor > 0) ? (int)result : (int)-result;
    }
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (words.length == 0) {
            return result;
        }

        // how many times each word is supposed to occur
        Map<String, Integer> expected = new HashMap<>();
        for (String word : words) {
            expected.put(word, expected.getOrDefault(word, 0) + 1);
        }
            
        // each word's length and all words' count
        int len = words[0].length(), count = words.length;
        if (s.length() < count * len) {
            return result;
        }

        for (int i = 0; i < len; i++) {
            for (int j = i; j <= s.length() - count * len; j += len) {
                // how many times every word actually occurs in each substring
                Map<String, Integer> actual = new HashMap<>();

                // iterate from the last
                for (int k = count - 1; k >= 0; k--) {
                    // extract current word
                    String currentWord = s.substring(j + k * len, j + (k + 1) * len);
                    
                    // current word is not supposed to occur
                    if (!expected.containsKey(currentWord)) {
                        break;
                    } else {
                        int occurences = actual.getOrDefault(currentWord, 0) + 1;
                        
                        // can not exceed expected occurences
                        if (occurences > expected.get(currentWord)) {
                            // start right after invalid occurence, as previous choices will include invalid.
                            j += k * len;
                            break;
                        }
                        
                        actual.put(currentWord, occurences);
                        
                        // all words appear
                        if (k == 0) {
                            result.add(j);
                        }
                    }
                }
            }
        }
        return result;
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        // search from right to left and find the first element to break the ascending order
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }

        // if there is an element that break the ascending order
        if (i >= 0) {
            int j = nums.length - 1;

            // find the rightmost element which is larger than nums[i]
            while (nums[i] >= nums[j]) {
                j--;
            }
            
            // swap nums[i] and nums[j]
            swap(nums, i, j);
        }
        // reverse all elements after index i
        reverseArray(nums, i + 1, nums.length - 1);
    }

    // swap two nums
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // reverse part of the array
    private void reverseArray(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        int result = 0;
        
        ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
        
        // the index preceding to potential start of valid parentheses
        stack.push(-1);
        
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (curr == '(') {
                stack.push(i);
            } else {
                // no matter we get valid parentheses or not, we need to pop here
                // if valid, we need to get last index to calculate diff
                // if unvalid, we update with current index
                stack.pop();
                
                if (stack.isEmpty()) {
                    // the stack is empty only if we have an extra ')'. Any further extensions of valid parentheses is impossible
                    // push current index, since it is preceding to potential start of valid parentheses
                    stack.push(i);
                } else {
                    // this may be our longest valid parentheses
                    result = Math.max(result, i - stack.peek());
                }
            }
        }
        
        return result;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            // nums[mid] matches with target, return
            if (nums[mid] == target) {
                return mid;
            }

            // left half is ordered
            if (nums[left] <= nums[mid]) {
                // target is in left half
                if (target >= nums[left] && target <= nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // right half is ordered
            if (nums[mid] <= nums[right]) {
                // target is in right half
                if (target >= nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
}

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

        // left
        int left = 0, right = nums.length;
        while (left < right) { 
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] >= target) {
                right = mid;
            }
        }
        
        if (left != nums.length && nums[left] == target) {
            result[0] = left;
        }

        // right
        left = 0;
        right = nums.length;
        while (left < right) { 
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        
        if (left != 0 && nums[left - 1] == target) {
            result[1] = left - 1;
        }

        return result;
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // num's length +1, therefore right should be 'nums.length' instead of 'nums.length - 1'
        int left = 0, right = nums.length;

        // standard binary search
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // both left and right are valid
        return left; 
    }
}

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] row = new int[9][9]; // row[i][num] indicates the count of 'num' in the i-th row
        int[][] col = new int[9][9]; // col[j][num] indicates the count of 'num' in the j-th column
        int[][] block = new int[9][9]; // block[k][num] indicates the count of 'num' in the k-th 3*3 block

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // only validate filled cells
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int blockIndex = (i/3) * 3 + j/3;

                    // each num should not duplicate in each row, col, block
                    if (row[i][num] > 0 || col[j][num] > 0 || block[blockIndex][num] > 0) {
                        return false;
                    }
                    
                    row[i][num] += 1;
                    col[j][num] += 1;
                    block[blockIndex][num] += 1;
                }
            }
        }
        return true;
    }
}

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board, 0, 0);
    }
    
    // solve based on index
    private Boolean solve(char[][] board, int i, int j) {
        // finish all 9 row
        if (i == 9) {
            return true;
        }
        
        // finish current row, jump to next row
        if (j == 9) {
            return solve(board, i+1, 0);
        }
        
        // non-digit, switch to next column
        if (board[i][j] != '.') {
            return solve(board, i, j+1);
        }

        // backtrack
        for (char c = '1'; c <= '9'; c++) {
            if (check(board, i, j, c)) {
                board[i][j] = c;
                
                // all subsequent cells are valid
                if (solve(board, i, j+1)) {
                    return true;
                }
                
                board[i][j] = '.';
            }
        }
        
        return false; // no solution
    }

    // check if current character is valid
    private Boolean check(char[][] board, int i, int j, char val) {
        for (int c = 0; c < 9; c++) {
            
            // duplicate in current row, column or 3 * 3 block
            if (board[i][c] == val ||
                board[c][j] == val ||
                board[i - i%3 + c/3][j - j%3 + c%3] == val) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }

        // all upper levels' result
        StringBuilder pre = new StringBuilder(countAndSay(n - 1));
        
        // construct this level
        StringBuilder result = new StringBuilder();

        int i = 0;
        while (i < pre.length()) {
            int count = 0; // current number's count
            int j = i; // start index of current number

            char say = pre.charAt(j);
            while (i < pre.length() && pre.charAt(i) == say) {
                count++;
                i++;
            }

            result.append(count);
            result.append(say);
        }
        return result.toString();
    }
}

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] candidates, int target, int index) {
        if (target == 0) {
            result.add(new ArrayList<>(temp));
        } else {
            for (int i = index; i < candidates.length && candidates[i] <= target; i++) {
                temp.add(candidates[i]);
                backtrack(result, temp, candidates, target - candidates[i], i); // allow duplicate, thus starts from i
                temp.remove(temp.size() - 1);
            }
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] candidates, int target, int index) {
        if (target == 0) {
            result.add(new ArrayList<>(temp));
        } else {
            for (int i = index; i < candidates.length && candidates[i] <= target; i++) {
                temp.add(candidates[i]);
                backtrack(result, temp, candidates, target - candidates[i], i + 1); // not allow duplicate, thus starts from i + 1
                temp.remove(temp.size() - 1);
                
                // skip duplicates
                while (i + 1 < candidates.length && candidates[i] == candidates[i + 1]) {
                    i++;
                }
            }
        }
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // if nums[i] is in the range of (0, len] and not in its place,
            // put nums[i] on the (nums[i] - 1)th index of the array
            while (nums[i] > 0 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) {
                // swap nums[i] and nums[nums[i] - 1]
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        // the first number unmatched is the answer
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // all matched, the smallest positive integer is last integer + 1
        return len + 1;
    }
}

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 1) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int currentLevel = 0, result = 0;

        while (left < right) {
            int lowerBound = 0;
            
            // smaller of height[left] and height[right], then move left or right accordingly
            if (height[left] <= height[right]) {
                lowerBound = height[left];
                left++;
            } else {
                lowerBound = height[right];
                right--;
            }   
            
            // update current bar's level
            currentLevel = Math.max(currentLevel, lowerBound);
            
            // new water fills in
            result += currentLevel - lowerBound;
        }
        
        return result;
    }
}