671. Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

If no such second minimum value exists, output -1 instead.

 

 

Example 1:

Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: root = [2,2,2]
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

 

Constraints:

• The number of nodes in the tree is in the range [1, 25].
• 1 <= Node.val <= 231 - 1
• root.val == min(root.left.val, root.right.val) for each internal node of the tree.

 My answer: recursion:

Better solution is put after it:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

/** * 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 int findSecondMinimumValue(TreeNode root) { //find the 1st element larger than root if (root == null || root.left == null) { return -1; } int leftResult = findSecondMinimumValue(root.left); int rightResult = findSecondMinimumValue(root.right); int[] finalValues = new int[]{root.val, root.left.val, root.right.val, leftResult, rightResult}; Arrays.sort(finalValues); for (int i = 0; i < finalValues.length; i ++) { if (finalValues[i] > root.val) { return finalValues[i]; } } return -1; } }

1 2 3 4 5 6 7 8

public int findSecondMinimumValue(TreeNode root) { if(root.left == null) return -1; int l = root.left.val == root.val ? findSecondMinimumValue(root.left) : root.left.val; int r = root.right.val == root.val ? findSecondMinimumValue(root.right) : root.right.val; return l == -1 || r == -1 ? Math.max(l, r) : Math.min(l, r); }

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-100000]
Output: -100000

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. 

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public class Solution { public int maxSubArray(int[] nums) { // answer before 2021 // int globalMax = nums[0]; // int localMax = nums[0]; // for (int i = 1; i < nums.length; i ++) { // // localMax is the bigger value which includes "i"th number, so that the globalMax can be the result of contiguous subarray // localMax = Math.max(nums[i], localMax + nums[i]); // globalMax = Math.max(globalMax, localMax); // } // return globalMax; // answer on 2021 if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } // dp is the value where max sum given i th element must be included int[] dp = new int[nums.length]; dp[0] = nums[0]; for (int i = 1; i < nums.length; i ++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); } int maxSum = dp[0]; for (int i = 1; i < dp.length; i ++) { maxSum = Math.max(maxSum, dp[i]); } return maxSum; } }

Regarding the follow up via Divide and Conqure: below answer is from Leetcode forum. 

Divide and Conquer

The Divide-and-Conquer algorithm breaks nums into two halves and find the maximum subarray sum in them recursively. Well, the most tricky part is to handle the case that the maximum subarray spans the two halves. For this case, we use a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSubArray(nums, 0, nums.size() - 1);
    }
private:
    int maxSubArray(vector<int>& nums, int l, int r) {
        if (l > r) {
            return INT_MIN;
        }
        int m = l + (r - l) / 2, ml = 0, mr = 0;
        int lmax = maxSubArray(nums, l, m - 1);
        int rmax = maxSubArray(nums, m + 1, r);
        for (int i = m - 1, sum = 0; i >= l; i--) {
            sum += nums[i];
            ml = max(sum, ml);
        }
        for (int i = m + 1, sum = 0; i <= r; i++) {
            sum += nums[i];
            mr = max(sum, mr);
        }
        return max(max(lmax, rmax), ml + mr + nums[m]);
    

Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

My answer

I didn't figure out the answer. Answer below is based on top of one good answer. Basically this is a good example of Divide and Conquer. We need to find out which substring is worth checking, and skip ineligible substring, divide substring by such `eligibility`, and conquer each one.

I think one key condition of using Divide and Conquer is if this problem can be divided into sub-problem, and the answer to same question when applied to the sub-problem can help for original problem.

class Solution {
    public int longestSubstring(String s, int k) {
        int defaultLength = 0;
        if (s == null || s.length() < k) {
            return defaultLength;
        }
        Map<Character, Integer> charLocations = new HashMap<Character,Integer>();
        
        for (int i = 0; i < s.length(); i ++) {
            Integer count = charLocations.getOrDefault(s.charAt(i), 0);
            count++;
            charLocations.put(s.charAt(i), count);
        }

        for (int i = 0; i < s.length(); i ++) {
            if (charLocations.get(s.charAt(i)) >= k) {
                int j = i + 1;
                while (j < s.length() && charLocations.get(s.charAt(j)) >= k) {
                    j ++;
                }
                if (j == s.length()) {
                    return j - i;
                }
                 return Math.max(longestSubstring(s.substring(i, j), k), longestSubstring(s.substring(j), k));
            }
        }
        
        return defaultLength;
    }
}