This is Yizhe's Blog: Easy

Showing posts with label Easy. Show all posts

Sunday, January 31, 2021

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:

/**
 * 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;
    }
}

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);
    }

716. Max Stack

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

MaxStack() Initializes the stack object.
void push(int x) Pushes element x onto the stack.
int pop() Removes the element on top of the stack and returns it.
int top() Gets the element on the top of the stack without removing it.
int peekMax() Retrieves the maximum element in the stack without removing it.
int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

Constraints:

-107 <= x <= 107
At most 104 calls will be made to push, pop, top, peekMax, and popMax.
There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call?

My answer: stack + heap

class MaxStack {
    
    // alternative 1: use stack for max + normal stack, which always pushes max value everytime push(), 
    // it also pops when normal pop()/popMax() -> O(N)/O(N)
    // alternative 2: Double Linked List + TreeMap
    
    LinkedList<Integer> stack;
    PriorityQueue<Integer> heap;

    /** initialize your data structure here. */
    public MaxStack() {
        stack = new LinkedList<Integer>();
        heap = new PriorityQueue<Integer>((a, b) -> {return b.compareTo(a);});
    }
    
    public void push(int x) {
        stack.addLast(x);
        heap.add(x);
    }
    
    public int pop() {
        int removed = stack.removeLast();
        heap.remove(removed);
        return removed;
    }
    
    public int top() {
        return stack.peekLast();
    }
    
    public int peekMax() {
        return heap.peek();
    }
    
    public int popMax() {
        System.out.println(stack);
        int removed = heap.poll();
        int removeIndex = -1;
        for (int i = stack.size() - 1 ; i >= 0 ; i --) {
            if (stack.get(i) == removed) {
                removeIndex = i;
                break;
            }
        }
        stack.remove(removeIndex);
        System.out.println(stack);
        return removed;
    }
}

/**
 * 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();
 */

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:

The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the BST.

My answer: it is one important constraints that both p and q must exits. My answer works for any binary tree, even not BST

Better solution given BST: find the 1st node whose value is between p and q, starting from top-down direction. It is put after below answer.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

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

        if (leftResult == null && rightResult == null) {
            return null;
        } else if (leftResult == null) {
            return rightResult;
        } else if (rightResult == null) {
            return leftResult;
        } else {
            return root;
        }
    }
}

Solution for BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

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

//         if (leftResult == null && rightResult == null) {
//             return null;
//         } else if (leftResult == null) {
//             return rightResult;
//         } else if (rightResult == null) {
//             return leftResult;
//         } else {
//             return root;
//         }
        if (p.val > q.val) {
            TreeNode temp = null;
            temp = p;
            p = q;
            q = temp;
        }
        if (root == null || (root.val >= p.val && root.val <= q.val)) {
            return root;
        }
        if (root.val >= q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val <= p.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return null;
    }
}

Friday, January 29, 2021

605. Can Place Flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

Constraints:

1 <= flowerbed.length <= 2 * 104
flowerbed[i] is 0 or 1.
There are no two adjacent flowers in flowerbed.
0 <= n <= flowerbed.length

My answer:

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) {
            return true;
        }
        // greedy should be enough
        for (int i = 0; i < flowerbed.length; i ++) {
            if (canPlace(i, flowerbed)) {
                flowerbed[i] = 1;
                n--;
                if (n == 0) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean canPlace(int i, int[] flowerbed) {
        return flowerbed[i] == 0 && flowerbed[Math.max(0, i - 1)] == 0 && flowerbed[Math.min(flowerbed.length - 1, i + 1)] == 0;
    }
}

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

My answer:

class MyHashMap {

    // array + chaining, I missed case: existing key is updated
    // use array, and each element is a list, containing nodes, each of node has key and value associated
    
    class Node {
        public int key;
        public int value;
        Node (int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    class ListNode {
        public List<Node> nodes;
        public ListNode () {
            nodes = new ArrayList<Node>();
        }
    }
    
    private ListNode[] elements;
    /** Initialize your data structure here. */
    public MyHashMap() {
         elements = new ListNode[10000];
    }
    
    private int getIndex(int key) {
        return key % elements.length;
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        int index = getIndex(key);
        ListNode nodeList = elements[index]; 
        if (nodeList == null) {
            nodeList = new ListNode();
        }
        boolean existed = false;
        for (Node node : nodeList.nodes) {
            if (node.key == key) {
                node.value = value;
                existed = true;
            }
        }
        if (!existed) {
            nodeList.nodes.add(new Node(key, value));    
        }

        elements[index] = nodeList;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int index = getIndex(key);
        ListNode nodeList = elements[index];
        if (nodeList == null) {
            return -1;
        }
        for (Node node : nodeList.nodes) {
            if (node.key == key) {
                return node.value;
            }
        }
        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int index = getIndex(key);
        ListNode nodeList = elements[index];
        if (nodeList == null || nodeList.nodes.isEmpty()) {
            return;
        }
        int nodeIndex = -1;
        for (int i = 0; i < nodeList.nodes.size(); i ++) {
            if (nodeList.nodes.get(i).key == key) {
                nodeIndex = i;
                break;
            }
        }
        if (nodeIndex != -1) {
            nodeList.nodes.remove(nodeIndex);
        }
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

Wednesday, January 27, 2021

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:

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]);

Labels

Sunday, January 31, 2021

671. Second Minimum Node In a Binary Tree

716. Max Stack

235. Lowest Common Ancestor of a Binary Search Tree

Friday, January 29, 2021

605. Can Place Flowers

706. Design HashMap

Wednesday, January 27, 2021

53. Maximum Subarray