LIKE CODING

Monday, April 26, 2021

Range product (Binary Index Tree)

arr = [1,2,3,4,5,6,7]. return the sub array product [i, j].

https://iq.opengenus.org/fenwick-tree-range-product/

import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world");

        RangeProduct rp = new RangeProduct(new int[]{1,2,3,4,5,6,7});
        rp.buildBIT();
        rp.print();
        //System.out.println(rp.getPrefixProd(5));
        System.out.println(rp.getRangeProd(1, 3));
        

    }
}

class RangeProduct{
    int[] arr;
    int n;
    int[] bit;

    RangeProduct(int[] _arr){
        arr = _arr;
        n = arr.length;
    }

    int getParent(int x){
        return x - (x&(-x));
    }

    int getNext(int x){
        return x + (x&(-x));
    }

    //nlogn
    void buildBIT(){
        bit = new int[n+1];
        Arrays.fill(bit, 1);
        for(int i=1; i<=n; ++i){
            int v = arr[i-1];
            int j = i;
            while(j<=n){
                bit[j] *= v;
                j = getNext(j);
            }
        }
    }

    int getPrefixProd(int i){
        i++;
        int prod = 1;
        while(i>0){
            prod *= bit[i];
            i = getParent(i);
        }
        return prod;
    }

    int getRangeProd(int i, int j){
        int prodj = getPrefixProd(j);
        int prodi = i==0 ? 1 : getPrefixProd(i-1);
        if(prodi!=0) return prodj/prodi;

        j++;
        int parent = getParent(j);
        int prod = 1;
        while(parent>=i){
            if(bit[j]==0) return 0;
            prod *= bit[j];
            j = parent;
            parent = getNext(j);
        }
        while(j>i){
            if(arr[j-1]==0) return 0;
            prod*=arr[j-1];
            j--;
        }
        return prod;
    }

    void print(){
        System.out.println(Arrays.toString(bit));
    }
}

Thursday, April 15, 2021

LeetCode [1448] Count Good Nodes in Binary Tree

1448. Count Good Nodes in Binary Tree

Medium

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

The number of nodes in the binary tree is in the range [1, 10^5].
Each node's value is between [-10^4, 10^4].

/**
 * 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 {
    int cnt = 0;
    public int goodNodes(TreeNode root) {
        helper(root, Integer.MIN_VALUE);
        return cnt;
    }
    
    void helper(TreeNode node, int max){
        if(node==null) return;
        if(node.val>=max) cnt++;
        int m = Math.max(max, node.val);
        helper(node.left, m);
        helper(node.right, m);
    }
}

Saturday, April 3, 2021

LeetCode [938] Range Sum of BST

938. Range Sum of BST

Easy

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23

Constraints:

The number of nodes in the tree is in the range [1, 2 * 104].
1 <= Node.val <= 105
1 <= low <= high <= 105
All Node.val are unique.

/**
 * 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 {
    int sum = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        helper(root, low, high);
        return sum;
    }
    
    void helper(TreeNode node, int low, int high){
        if(node==null) return;
        if(node.val>=low && node.val<=high) sum += node.val;
        if(!(node.val<=low)) helper(node.left, low, high);
        if(!(node.val>=high)) helper(node.right, low, high);
    }
}

Friday, April 2, 2021

LeetCode [1570] Dot Product of Two Sparse Vectors

1570. Dot Product of Two Sparse Vectors

Medium

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

SparseVector(nums) Initializes the object with the vector nums
dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6

Constraints:

n == nums1.length == nums2.length
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 100

class SparseVector {
    Map<Integer, Integer> map;
    SparseVector(int[] nums) {
        map = new HashMap<>();
        for(int i=0; i<nums.length; ++i){
            map.put(i, nums[i]);
        }
    }
    
	// Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int sz1 = map.size();
        int sz2 = vec.map.size();
        if(sz1<sz2) return helper(map, vec.map);
        else return helper(vec.map, map);
    }
    
    int helper(Map<Integer, Integer> map1, Map<Integer, Integer> map2){
        int s = 0;
        for(Map.Entry<Integer, Integer> en : map1.entrySet()){
            int index = en.getKey();
            int value = en.getValue();
            if(map2.containsKey(index)){
                s += value*map2.get(index);
            }
        }
        return s;
    }
}

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);

Thursday, April 1, 2021

LeetCode [680] Valid Palindrome II

680. Valid Palindrome II

Easy

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

class Solution {
    public boolean validPalindrome(String s) {
        int n = s.length(), l = 0, r = n-1, d = 0;
        while(l<r){
            if(s.charAt(l)!=s.charAt(r)){
                return helper(s, l+1, r)||helper(s, l, r-1);
            }
            l++;
            r--;
        }
        return true;
    }
    
    boolean helper(String s, int l, int r){
        while(l<r){
            if(s.charAt(l)!=s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

LeetCode [1249] Minimum Remove to Make Valid Parentheses

1249. Minimum Remove to Make Valid Parentheses

Medium

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.

class Solution {
    public String minRemoveToMakeValid(String s) {
        String s1 = trim1(s);
        String s2 = trim2(new StringBuilder(s1).reverse().toString());
        return new StringBuilder(s2).reverse().toString();
    }
    
    String trim1(String s){
        int l = 0, r = 0;
        StringBuilder sb = new StringBuilder();
        for(char ch : s.toCharArray()){
            boolean skip = false;
            if(ch=='(') l++;
            if(ch==')'){
                r++;
                if(r>l){
                    skip = true;
                    r--;
                } 
            }
            if(!skip) sb.append(ch);
        }
        return sb.toString();
    }
    
    String trim2(String s){
        int l = 0, r = 0;
        StringBuilder sb = new StringBuilder();
        for(char ch : s.toCharArray()){
            boolean skip = false;
            if(ch==')') r++;
            if(ch=='('){
                l++;
                if(l>r){
                    skip = true;
                    l--;
                }
            }
            if(!skip) sb.append(ch);
        }
        return sb.toString();
    }
}

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stk = new Stack<>();
        StringBuilder sb = new StringBuilder(s);
        int n = sb.length();
        for(int i=0; i<n; ++i){
            if(s.charAt(i)=='('){
                stk.add(i);
            }else if(s.charAt(i)==')'){
                if(!stk.isEmpty()){
                    stk.pop();
                }else{//extra ')', remove
                    sb.setCharAt(i, '*');
                }
            }
        }

        while(!stk.isEmpty()){
            int i = stk.pop();
            sb.setCharAt(i, '*');
        }

        return sb.toString().replaceAll("\\*", "");
    }
}