class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

class Solution {
    public int[] sortByBits(int[] arr) {
        int n=arr.length;
        for (int i = 0; i < n-1; i++){
            for (int j = 0; j < n-i-1; j++){
                if (func(arr[j]) > func(arr[j+1]) || (arr[j] > arr[j+1] && func(arr[j]) == func(arr[j+1])))
                {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
    public int func(int n) {
        int count=0;
        while(n!=0){
            if((n&1)==1)
            count++;
            n=n>>>1;
        }
        return count;
    }
}

class Cashier {
    int count=0, order;
    double discountProduct;
    Map<Integer, Integer> map = new HashMap<>();
    
    public Cashier(int n, int discount, int[] products, int[] prices) {
        this.order=n;
        this.discountProduct=1-(double)discount/100;
        for(int i=0; i<prices.length; i++){
            map.put(products[i], prices[i]);
        }
    }
    
    public double getBill(int[] product, int[] amount) {
        count++;
        int total=0;
        for(int i=0; i<amount.length; i++){
            total+=map.get(product[i])*amount[i];
        }
        
        return count%order==0? total*discountProduct : total;
    }
}

class Bank {
    long [] balance;
    public Bank(long[] balance) {this.balance=balance;}
    
    public boolean transfer(int account1, int account2, long money) {
        if(account1>balance.length || account2>balance.length || balance[--account1]<money)
            return false;
        
        balance[account1]-=money;
        balance[account2-1]+=money;
        return true;
    }
    
    public boolean deposit(int account, long money) {
        if(account>balance.length)
            return false;
        balance[account-1]+=money;
        return true;
    }
    
    public boolean withdraw(int account, long money) {
        if(account>balance.length || balance[--account]<money)
            return false;
        balance[account]-=money;
        return true;
    }
}

select product_id, 'store1' as store, store1 as price from products where store1 is not null
union
select product_id, 'store2' as store, store2 as price from products where store2 is not null
union
select product_id, 'store3' as store, store3 as price from products where store3 is not null

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int time=0;
        while(tickets[k]!=0){
            for(int i=0; i<tickets.length; i++){
                if(tickets[i]-- > 0) time++;
                if(tickets[k]==0) break;
            }
        }
        
        return time;
    }
}

class Solution {
    public int firstUniqChar(String s) {
        int arr[] = new int[26];
        for(Character ch: s.toCharArray()){
            arr[ch-'a']++;
        }
        for(Character ch: s.toCharArray()){
            if(arr[ch-'a']==1)
                return s.indexOf(ch);
        }
        
        return -1;
    }
}

class MyStack {
    Queue<Integer> q = new LinkedList<>();
    Queue<Integer> temp = new LinkedList<>();
    public MyStack() {}
    public void push(int x) {
        q.add(x);
        for(int i=0;i<q.size()-1;i++)
        {
           q.add(q.poll());
        }
    }
    public int pop() {
        return q.remove();
    }
    public int top() {
        return q.peek();
    }
    public boolean empty() {
        return q.isEmpty();
    }
}

class Solution {
    public int maxArea(int[] height) {
        int area=0, temp;
        int left=0, right=height.length-1;
        while(left<right){
            temp=(right-left)*Math.min(height[left], height[right]);
            area=Math.max(area, temp);
            if(height[left]>height[right]) {
                right--;
            } else if(height[left]<height[right]) {
                left++;
            } else {
                left++;
                right--;
            }
        }
        return area;
    }
}

class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m=grid.length, n=grid[0].length, counter=m*n-k%(m*n);
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                list.add(grid[i][j]);
            }
        }
        List<Integer> piece;
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=0; i<m; i++){
            piece = new ArrayList<>();
            for(int j=0; j<n; j++){
                piece.add(list.get(counter++ % (m*n)));
            }
            ans.add(piece);
        }
        return ans;
    }
}

select v.customer_id, count(*) as count_no_trans
from visits v
left join transactions t
on v.visit_id=t.visit_id
where t.transaction_id is null
group by customer_id

class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode slow = head.next;
        ListNode fast = head.next;
        int sum=0;
        while(fast!=null){
            sum+=fast.val;
            if(fast.val==0){
                slow.val=sum;
                slow.next=fast.next;
                slow=slow.next;
                sum=0;
            }
            fast=fast.next;
        }
        return head.next;
    }
}

class Solution {
    int sum=0;
    public int sumEvenGrandparent(TreeNode root) {
        if(root==null) return 0;
        helper(root, null, null);
        return sum;
    }
    
    public void helper(TreeNode node, TreeNode p, TreeNode gp){
        if(node == null) return;
        
        if(gp!=null && gp.val%2==0){
            sum+=node.val;
        }
        
        helper(node.left, node, p);
        helper(node.right, node, p);
    }
}

select sell_date,
count(distinct product) as num_sold,
group_concat(distinct product order by product) as products
from activities
group by sell_date

class Solution {
    int sum=0;
    public TreeNode bstToGst(TreeNode root) {
        if(root==null) return null;
        bstToGst(root.right);
        sum+=root.val;
        root.val=sum;
        bstToGst(root.left);
        
        return root;
    }
}

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null) return null;
        convertBST(root.right);
        sum+=root.val;
        root.val=sum;
        convertBST(root.left);
        
        return root;
    }
}

select user_id,
max(time_stamp) as last_stamp
from logins
where year(time_stamp)=2020
group by user_id

select u.name, ifnull(sum(r.distance), 0) as travelled_distance
from users u
left join rides r on u.id=r.user_id
group by u.name
order by travelled_distance desc, u.name asc;

class Solution {
    public int[] processQueries(int[] queries, int m) {
        List<Integer> list = new ArrayList<>();
        for(int i=1; i<=m; i++)
            list.add(i);
        
        int[] ans = new int[queries.length];
        for(int i=0; i<ans.length; i++){
            ans[i]=list.indexOf(queries[i]);
            list.remove(ans[i]);
            list.add(0, queries[i]);
        }
        
        return ans;
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack.length()<needle.length()) return -1;
        for(int i=0; i<haystack.length(); i++){
            for(int j=0; ; j++){
                if(i+j==haystack.length()) return -1;
                if(haystack.charAt(i+j) != needle.charAt(j)) break;
                if(j==needle.length()-1) return i;
            }
        }
        return -1;
    }
}