Extra Questions.txt

              			Some Extra Questions

------------------------------------------------------------------------------------
1. Tower of Hanoi ->https://www.youtube.com/watch?v=QDBrZFROuA0
-> Make the recursion Tree and do the dry run , and do inorder traversal 
public static void toh(int n, int t1id, int t2id, int t3id){
        if(n==0){
            return;
        }
        //(*) ->Means following all instructions of tower of hanoi
        toh(n-1,t1id,t3id,t2id); //will print the instructions to move n-1 disks from t1 to t3 using t2(*)
        System.out.println(n+"["+t1id+" -> "+t2id+"]");
        toh(n-1,t3id,t2id,t1id);
    }
-------------------------------------------------------------------------------------
2. Do All variations of buy and sell stock

-> https://www.youtube.com/watch?v=MyqDgMy-Kew

a) Buy & Sell Stock -> part 1 and 2 in dp and arrays

b) Buy and sell stock with transaction fee (LeetCode 714)
->  public int maxProfit(int[] prices, int fee) {
        if(prices.length==0){
            return 0;
        }
        // at any ith day we have 2 options
        // if you don't own a stock-> 2 options either buy or not
        // if you own a stock -> 2 options either sell or not
        
        // as soon as i buy ->  - (prices[i]+fee);
        // as soon as i sell -> + prices[i] 
    
        int[][]dp=new int[prices.length][2];
        for(int[]dpp:dp){
            Arrays.fill(dpp,-1);
        }
        
        //since initally i don't own a stock so passing 0 for owning means not owning
        return BuyNSellStockWithFee(0,prices,fee,0,dp);
    }
    public int BuyNSellStockWithFee(int idx, int[]prices,int fee,int own,int[][]dp){
        if(idx==prices.length)return 0;
        
        if(dp[idx][own]!=-1){
            return dp[idx][own];
        }
        
        if(own==1){
            int op1 = prices[idx]+BuyNSellStockWithFee(idx+1,prices,fee,0,dp); //sell
            int op2 = BuyNSellStockWithFee(idx+1,prices,fee,1,dp); //not sell
            return dp[idx][own]=Math.max(op1,op2);
        }else{
            int op1 = -(prices[idx]+fee)+BuyNSellStockWithFee(idx+1,prices,fee,1,dp); //buy
            int op2 = BuyNSellStockWithFee(idx+1,prices,fee,0,dp); //not buy
            return dp[idx][own]=Math.max(op1,op2);
        }
    }

c) Buy and Sell Stock with Cooldown ( LeetCode 309)

(for Buy and sell stock 3 & 4 you can refer kartik arora solution which is very intuitive as well)

d) Buy and Sell Stock III (in dp section)

e) Buy and Sell Stock IV (k transactions allowed) (in dp section)
->
class Solution {
    public int maxProfit(int[] prices) {
        //intuition : 
        // we will have 3 states i) index ii) own or now own iii) cooldown or not cooldown
        // cooldown only give problem while buying not with selling.
        
        // else the explaination remains same as buy and sell stock with transaction fee.
        
        int[][][]dp=new int[prices.length][2][2];
        
        for(int [][]dpp:dp){
            for(int[]dppp:dpp){
                Arrays.fill(dppp,-1);
            }
        }
        //since intially we don't have the cooldown
        return BuyNSellStockCooldown(0,0,0,prices,dp);
    }
    
    public int BuyNSellStockCooldown(int idx, int own ,int cooldown,int[]prices,int[][][]dp){
        if(idx==prices.length)return 0;
        
        
        if(dp[idx][own][cooldown]!=-1){
            return dp[idx][own][cooldown];
        }
        
        if(own==0){
            int op1 = (cooldown==1)?0: -(prices[idx]) + BuyNSellStockCooldown(idx+1,1,0,prices,dp);
            int op2 = BuyNSellStockCooldown(idx+1,0,0,prices,dp);
            return dp[idx][own][cooldown]=Math.max(op1,op2);
        }else{
            int op1 = prices[idx] + BuyNSellStockCooldown(idx+1,0,1,prices,dp); //as soon as i sell there will be cooldown.
            int op2= BuyNSellStockCooldown(idx+1,1,0,prices,dp);
            return dp[idx][own][cooldown]=Math.max(op1,op2);
        }
    }
}
-------------------------------------------------------------------------------------
3. Permutations (leetcode 46)
->Time complexity->(n!*n)
->Space complexity->(2n)

Using extra space->
 public void solve( List<List<Integer>>ans,List<Integer>ds,boolean[]freq,int[]nums){
        if(ds.size()==nums.length)
        {
            ans.add(new ArrayList<>(ds));
            return;
        }
        
        for(int i=0;i<nums.length;i++){
            if(!freq[i]){
                freq[i]=true;
                ds.add(nums[i]);
                solve(ans,ds,freq,nums);
                ds.remove(ds.size()-1);
                freq[i]=false;
            }
        }
    }
Space optimised->
 public void solve(List<List<Integer>>ans,int idx,int[]nums){
    
        if(idx==nums.length){
            //copy the altered array.
            List<Integer>ds=new ArrayList<>();
            for(int i=0;i<nums.length;i++){
                ds.add(nums[i]);
            }
            ans.add(new ArrayList<>(ds));
            return;
        }
        //swap every index with every other ahead index
        for(int i=idx;i<nums.length;i++){
            swap(i,idx,nums);
            solve(ans,idx+1,nums);
            swap(i,idx,nums);
        }    
    }


-------------------------------------------------------------------------------------
4. Subarray Product less than K (leetcode 713)
-> //for every iteration,we try to get the longest subarray with product < k ending with nums[j]; 
 public int numSubarrayProductLessThanK(int[] nums, int k) {
        long pro=1l;
        int ans=0;

        int i=0,j=0;
        
        while(j<nums.length ){
            pro = pro * nums[j];
            
            while(i<=j && pro>=k){
                pro/=nums[i];
                i++;
            }
            ans+=(j-i+1);  // dry run you will get the flow that how it is calculating 
            j++;
        }
        return ans;
    }


-> Similar approach problem -> Number of Smooth Descent Periods of a Stock (Leetcode 2110)
-------------------------------------------------------------------------------------
5. Contiguous Array ( Leetcode 525 )
M1)
 public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        int zero = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) zero++;
            else zero--;
            if (zero == 0) max = i + 1;
            if (!map.containsKey(zero)) map.put(zero, i);
            else max = Math.max(max, i - map.get(zero));
        }
        return max;
    }

M2)
-> Just add 1 in case of 0 and -1 in case of 1 and find the largest subarray with sum 0
-> i mean the below solution.
-------------------------------------------------------------------------------------
6. Largest Subarray with sum 0 
 public static int LargestSubarrayWithSum0(int[]arr,int n){
        HashMap<Integer,Integer>map=new HashMap<>();
        int max=0;
        int sum=0;
        
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            if(sum==0){
                max=i+1;
            }else{
                if(map.get(sum)!=null){
                    max=Math.max(max,i-map.get(sum));
                }else{
                    map.put(sum,i);
                }
            }
        }
        return max;
    }

-------------------------------------------------------------------------------------
7. largest Subarray with sum no larger than k

private int maxSumSubArray(int[] a , int k){

    int max = Integer.MIN_VALUE;
    int preSum = 0;
    TreeSet<Integer> ts = new TreeSet();
    ts.add(0);

    for(int i=0;i<a.length;i++){
        preSum += a[i];
        Integer gap = ts.ceiling(preSum - k);
        if(gap != null) max = Math.max(max, preSum - gap);
        ts.add(preSum);
    }
    return max;
}

# Longest subarray with sum k
->
static int lenOfLongSubarr(int[] arr, int n, int k)
      {
             // HashMap to store (sum, index) tuples
             HashMap<Integer, Integer> map = new HashMap<>();
             int sum = 0, maxLen = 0;
 
             // traverse the given array
             for (int i = 0; i < n; i++) {
                 
                  // accumulate sum
                  sum += arr[i];
                 
                  // when subarray starts from index '0'
                  if (sum == k)
                      maxLen = i + 1;
 
                  // make an entry for 'sum' if it is
                  // not present in 'map'
                  if (!map.containsKey(sum)) {
                      map.put(sum, i);
                  }
 
                  // check if 'sum-k' is present in 'map'
                  // or not
                  if (map.containsKey(sum - k)) {
                       
                      // update maxLength
                      if (maxLen < (i - map.get(sum - k)))
                          maxLen = i - map.get(sum - k);
                  }
             }
              
             return maxLen;            
      }
-------------------------------------------------------------------------------------
8. Subarray Sum Equals K (pepcoding)
 public int subarraySum(int[] nums, int k) {
        int sum = 0, result = 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (preSum.containsKey(sum - k)) {
                result += preSum.get(sum - k);
            }
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }
        
        return result;
    }
Binary Subarrays with Sum (Leetcode 930)
->  public int numSubarraysWithSum(int[] nums, int k) {

 // atMostK(nums,k)<- this will give subarray sum <=k | atMostK(nums,k-1) <= this will give subarray sum <=k-1       // the diff atMostK(nums,k) - atmostK(nums,k-1) <- this will give subarray sum exactly  == k.

        return SubarraySumAtMostK(nums,k) - SubarraySumAtMostK(nums,k-1);     
     }
    public int SubarraySumAtMostK(int[]nums,int k){
        int sum=0;
        int i=0;
        int j=0;
        int ans=0;
        
        while(j<nums.length){
            sum+=nums[j];
            while(i<=j && sum>k){
                sum-=nums[i++];
            }
            ans+=(j-i+1);
            j++;
        }
        return ans;
    }
-------------------------------------------------------------------------------------
9. Word Break (pepcoding)->https://www.youtube.com/watch?v=2NaaM_z_Jig

-------------------------------------------------------------------------------------
10. Minimum Size Subarray Sum (Leetcode 209)

 public int minSubArrayLen(int x, int[] arr) {
          // Initialize current sum and minimum length
        int curr_sum = 0;
        int n = arr.length;
        int ans = n + 1;
        // Initialize starting and ending indexes
        int start = 0, end = 0;
        boolean fl = false;
        while (end < n) {
            // Keep adding array elements while current sum
            // is smaller than or equal to x
            while (curr_sum < x && end < n)
                curr_sum += arr[end++];
            // If current sum becomes greater than x.
            while (curr_sum >= x && start < n) {
                fl=true;
                // Update minimum length if needed
                ans=Math.min(ans,end-start);
                // remove starting elements
                curr_sum -= arr[start++];
            }
        }
        if(!fl)return 0;
        return ans;
    }
-------------------------------------------------------------------------------------
11. Predict the winner (LeetCode 486)
    
-> Just like optimal Strategy game in Dp notes.    
    int p1Score = predictWinner(nums,0,n-1,dp);
    return (p1Score>=total-p1Score);
    
    
    public int predictWinner(int[]nums,int i,int j, int[][]dp){
       
        if(i>j){
            return 0;
        }
        
        if(i==j)return nums[i];
               
        if(dp[i][j]!=-1)return dp[i][j];
    
        int case1 = nums[i] + Math.min(predictWinner(nums,i+1,j-1,dp),predictWinner(nums,i+2,j,dp));
        int case2 = nums[j] + Math.min(predictWinner(nums,i+1,j-1,dp),predictWinner(nums,i,j-2,dp)); 
        
        return dp[i][j] = Math.max(case1,case2);    
    }
-------------------------------------------------------------------------------------
12. Frog Jump (LeetCode 403)

-> Array is sorted here in stricly increasing order
 public boolean canCross(int[] stones) {
        
        int n = stones.length;
        
        HashMap<Integer,HashSet<Integer>>map = new HashMap<>();
        
        
        for(int i=0;i<n;i++){
            map.put(stones[i],new HashSet<>());
        }
        //since from 0 we can take 1 jump only
        map.get(stones[0]).add(1);
        
        for(int i=0;i<n;i++){
            int currStone = stones[i];
            
            HashSet<Integer> jumps = map.get(currStone);
            
            for(int jump: jumps){
                int pos = currStone + jump;
                
                if(pos == stones[n-1])return true;
                
                if(map.containsKey(pos)){
                    if(jump-1>0)map.get(pos).add(jump-1);
                    map.get(pos).add(jump);
                    map.get(pos).add(jump+1);
                }
                
            }          
        }
        return false;
    }
-------------------------------------------------------------------------------------
13. Longest Arithmetic Subsequence of Given Difference (Leetcode 1218)
->
 public int longestSubsequence(int[] arr, int diff) {
        int[]dp = new int[arr.length];
        
        HashMap<Integer,Integer>map = new HashMap<>();
               
        int max=0;
        for(int i=0;i<arr.length;i++){
            if(map.containsKey(arr[i]-diff)){
                int k = map.get(arr[i]-diff);
                dp[i]=1+dp[k];
            }else{
                dp[i]=1;
            }
            max = Math.max(max,dp[i]);
            map.put(arr[i],i);
        }
        return max;
    }
-> 
public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer, Integer> dp = new HashMap<>();
        int longest = 0;
        for(int i=0; i<arr.length; i++) {
            dp.put(arr[i], dp.getOrDefault(arr[i] - difference, 0) + 1);
            longest = Math.max(longest, dp.get(arr[i]));
        }
        return longest;
    }
-------------------------------------------------------------------------------------
14. All Paths From Source to Target (Leetcode 797)

-> list.add(0); then call below function
 public void dfs(List<List<Integer>>adj,int node,int n,boolean[]vis,List<Integer>list,List<List<Integer>>ans){
        if(node==n-1){
            ans.add(new ArrayList<>(list));
            return;
        }
        
        for(int an:adj.get(node)){
            if(!vis[an]){
                list.add(an);
                vis[an]=true;
                dfs(adj,an,n,vis,list,ans);
                 vis[an]=false;
                list.remove(list.size()-1);
            }
        }
    }
-------------------------------------------------------------------------------------
15. Maximum Binary Tree (Leetcode-654)
M1) Recursion 

M2) Using stack
-> O(N)
-> for eg: 3,2,1,6,0,5

i) 3 in the stack
ii) 3,2 in the stack (3.right = 2)
iii) 3,2,1 in the stack (2.right = 1)
iv) 6 pop out all the make (6.left = 3), 6 in the stack
v) 6,0 in the stack (6.right = 0)
vi) 5 pop out 0 and make (5.left = 0), 6,5 in the stack
vii) stack no empty hence (6.right = 5)
viii) stack first element is the root.

public TreeNode constructMaximumBinaryTree(int[] nums) {
        
        Deque<TreeNode>st = new LinkedList<>();
        
        for(int i=0;i<nums.length;i++){
            TreeNode curr = new TreeNode(nums[i]);
            
            while(!st.isEmpty() && st.peek().val<nums[i]){
                curr.left = st.pop(); // here the curr big node will have its left as second big node in left.
            } 
            
            if(!st.isEmpty()){
// through this any node which is smaller then peek and in right will be attached to right of peek
                // for eg: 3.right = 2, 2.right = 1.
                st.peek().right = curr; 
            }
            
            st.push(curr);
        }
    
        return (st.isEmpty())?null:st.removeLast();
    }
-------------------------------------------------------------------------------------
16. Path In Zigzag Labelled Binary Tree (Leetcode 1104.)
-------------------------------------------------------------------------------------
17. Validate Binary Tree Nodes (Leetcode 1361)
-> 
M1) O(N) S(N)
-> Firstly check root of the binary tree using both left and right arrays.
-> Now apply bfs using root, if node.left exists and its already visited then return false, same goes with right.
-> Only take a count variable and increase it, at last if count == n, then return true else false.

public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        boolean[] isNotRoot = new boolean[n];
        for(int i: leftChild){
            if(i != -1){isNotRoot[i] = true;}
        }
        for(int i :rightChild){
            if(i != -1){isNotRoot[i] = true;}
        }
        int root = -1;
        for(int i = 0; i < n; i++){
            if(!isNotRoot[i]){
                if(root != -1){ return false; } //since root can't be more than 1.
                root = i;
            }
        }
        if(root == -1){ return false; }
        
        Queue<Integer> queue = new LinkedList();
        queue.add(root);
        boolean[] seen = new boolean[n];
        seen[root] = true;
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int curr = queue.remove();
                count++;
                if(leftChild[curr] != -1){
                    if(seen[leftChild[curr]]){ return false; }
                    seen[leftChild[curr]] = true;
                    queue.add(leftChild[curr]);
                }
                if(rightChild[curr] != -1){
                    if(seen[rightChild[curr]]){ return false; }
                     seen[rightChild[curr]] = true;
                    queue.add(rightChild[curr]);
                }
            }
        }
        return count == n;
    }
M2) It uses union and find (refer to discuss section for this approach)
-------------------------------------------------------------------------------------
18. Biggest cycle in Directed Graph.
-------------------------------------------------------------------------------------
19. Ford-Fulkerson Algorithm for Maximum Flow Problem
	
-------------------------------------------------------------------------------------
20. Longest path in an undirected tree.
-> Apply 2 DFS/BFS two times 
1. choose any node apply dfs/bfs to find the longest distance let this node be y, but return it with pair (node,distance)
-> you will do this by putting pair(node,dis) in queue, take distance array and find distance of all. return the longest distance with node.
2. Now from y apply dfs/bfs to find the longest path. which is the diamter of the tree.
-> Send src node as the result of first dfs/bfs and apply same just like the first one. 
-> this returned node is the farthest and its distance is the longest.(basically diameter) 
-------------------------------------------------------------------------------------
21. Number of Ways to arrive at destination ()

-> Dijkstra + Dp
 public int countPaths(int n, int[][] roads) {
        
        List<List<City>>adj = new ArrayList<>();
        
        for(int i=0;i<n;i++){
            adj.add(new ArrayList<>());
        }
        
        for(int i=0;i<roads.length;i++){
            int u = roads[i][0];
            int v = roads[i][1];
            int t = roads[i][2];
            adj.get(u).add(new City(v,t));
            adj.get(v).add(new City(u,t));
        }
        
        int[]ways = new int[n];
        int[]dis = new int[n];

        Arrays.fill(dis,Integer.MAX_VALUE);
        ways[0]= 1;
        dis[0] = 0;
        
        PriorityQueue<City>pq = new PriorityQueue<>((a,b)->(a.time-b.time));
        
        pq.add(new City(0,0));//src, dis
        
        while(!pq.isEmpty()){
            City rc = pq.poll();
            
            if(rc.time>dis[rc.city])continue;  // skip because we already got our low distance in prev iteration
            
            for(City ac:adj.get(rc.city)){
                if(dis[rc.city]+ac.time<dis[ac.city]){
                    
                    dis[ac.city] = dis[rc.city]+ac.time;
                    ways[ac.city] = ways[rc.city];
                    pq.add(new City(ac.city,dis[ac.city]));
                    
                }else if(dis[rc.city]+ac.time==dis[ac.city]){  // if distance remains same means, we got another path hence adding.
                    ways[ac.city] = (ways[ac.city]+ways[rc.city])%m;
                }
            }
            
        }
        
        return ways[n-1];
    }
-------------------------------------------------------------------------------------
22. Cycle sort
-------------------------------------------------------------------------------------
23. Cherry Pickup (Leetcode 741)

// we are starting both journies form (0,0) itself and not like one from 0,0 and than return journey from (n-1,n-1)
    // and this is because the possible path combination from (0,0) to (n-1,n-1) is same as (n-1,n-1) to (0,0) even if there
    // are thorns (hurdles)


public int cherryPickup(int[][] grid) {
        int[][][] dp = new int[grid.length][grid.length][grid.length];

        return Math.max(0, helper(grid, dp, 0, 0, 0));  // return 0 if there is no path from 0,0 to n-1,n-1
    }

    // Instead of going once from 0,0 to n-1,n-1 and then back, we simply go twice from 0,0 to n-1,n-1 because every path from n-1,n-1 to 0,0 can be interpreted as a path from 0,0 to n-1,n-1
    // Note that the one person can never cross the past path of the other person (they can only meet at the same position) so we don't need to worry about one person picking up an already picked up cherry from the past
    // What does a state represent? dp[r1][c1][c2] represents the max number of cherries that can be collected by 2 people going from r1,c1 and r2,c2 to n-1,n-1
    // Transitions between states? we collect cherries on current positions of the two people (r1,c1 and r2,c2), then we go through all possible next states and choose the best one (max number of cherries) as the next state (we do this by adding the number of cherries of the best next state to the number of cherries we picked up on the current two positions of the people). In the end, the state dp[0][0][0] will contain the max number of cherries that can be picked up by going from 0,0 to n-1,n-1 and back.

    private int helper(int[][] grid, int[][][] dp, int r1, int c1, int  c2) {

        // we can deduce r2 because r1 + c1 == r2 + c2, since with each move either r or c of a person gets incremented by exactly one (Manhattan distance to origin stays equal)
        // this way we reduce the 4D dp problem to a 3D one (we save space by reducing the number of things we store in a state)
        int r2 = r1 + c1 - c2;

        // check if current state is out of bounds or on thorns
        if (r1 >= grid.length || c1 >= grid.length || r2 >= grid.length || c2 >= grid.length || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return Integer.MIN_VALUE;   // current state should not be included in the solution
        }

        // check if we have already computed a solution for this state
        if (dp[r1][c1][c2] != 0) return dp[r1][c1][c2];

        // check if we reached the end state (note that if r1,c1 reached the end, this implies that r2,c2 also reached the end)
        if (r1 == grid.length - 1 && c1 == grid.length - 1) {
            return grid[r1][c1];
        }

        // compute and return answer for current state
        int result = grid[r1][c1];

        // in case the second person is on the same position, don't pick up the same cherry twice. Note that r1 == r2 <--> c1 == c2 (eg. they can't be on the same row without also being on the same column) 
        if (r1 != r2) {
            result += grid[r2][c2];
        }

        // pick best possible next state
        int bestNextState = Math.max(helper(grid, dp, r1 + 1, c1, c2),  // down, down 
                                    helper(grid, dp, r1, c1 + 1, c2 + 1));  // right, right    
        bestNextState = Math.max(bestNextState, helper(grid, dp, r1 + 1, c1, c2 + 1));   // down, right
        bestNextState = Math.max(bestNextState, helper(grid, dp, r1, c1 + 1, c2));   // right, down

        result += bestNextState;
        dp[r1][c1][c2] = result;    // store current state such that it can be re-used

        return result;
    }
-------------------------------------------------------------------------------------
24. Split Array Largest Sum (Leetcode 410) Premium**
-------------------------------------------------------------------------------------
25. Divide Chocolate (Leetcode 1231) Premium**
-------------------------------------------------------------------------------------
26. Combinations (LeetCode 77)
->  public static List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> combs = new ArrayList<List<Integer>>();
		combine(combs, new ArrayList<Integer>(), 1, n, k);
		return combs;
	}
	public static void combine(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) {
		if(k==0) {
			combs.add(new ArrayList<Integer>(comb));
			return;
		}
		for(int i=start;i<=n;i++) {
			comb.add(i);
			combine(combs, comb, i+1, n, k-1);
			comb.remove(comb.size()-1);
		}
	}
 
 -> Or can use pick/notPick strategy.

-------------------------------------------------------------------------------------
27. House Robber 3 -> https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem

->  we are just checking whether we would rob root or not.

public int rob(TreeNode root) {
    return robSub(root, new HashMap<>());
}

private int robSub(TreeNode root, Map<TreeNode, Integer> map) {
    if (root == null) return 0;
    if (map.containsKey(root)) return map.get(root);
    
    int val = 0;
    
    if (root.left != null) {
        val += robSub(root.left.left, map) + robSub(root.left.right, map);
    }
    
    if (root.right != null) {
        val += robSub(root.right.left, map) + robSub(root.right.right, map);
    }
    
    val = Math.max(val + root.val, robSub(root.left, map) + robSub(root.right, map));
    map.put(root, val);
    
    return val;
}

-> More optimised
O(n) 

public int rob(TreeNode root) {
    int[] res = robSub(root);
    return Math.max(res[0], res[1]);
}

private int[] robSub(TreeNode root) {
    if (root == null) return new int[2];
    
    int[] left = robSub(root.left);
    int[] right = robSub(root.right);
    int[] res = new int[2];

    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];
    
    return res;
}
-------------------------------------------------------------------------------------
28. Permutation in String (Leetcode : 567)

-> Sliding window approach that can be used in various other questions also.

public boolean checkInclusion(String s1, String s2) {
        
        if(s1.length()>s2.length()) return false;
        
        HashMap<Character,Integer>map = new HashMap<>();
        
        int psize = s1.length();
        int size = s2.length();
        
        for(int i=0;i<psize;i++){
            char ch = s1.charAt(i); 
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        
        int begin = 0, end = 0;
        
        int counter = map.size(); //taking map size because string can also have duplicates.
        
        while(end<size){
            char c = s2.charAt(end);
            if(map.containsKey(c)){
                map.put(c,map.get(c)-1);
                if(map.get(c)==0)counter--;
            }
            
            end++;
            
            while(counter==0){
                char temp = s2.charAt(begin);
                if(map.containsKey(temp)){
                    map.put(temp,map.get(temp)+1);
                    if(map.get(temp)>0)counter++;
                }
                
                if(end-begin == psize){
                    return true;
                }
                begin++;
            } 
        }
        
        return false;
    }
-------------------------------------------------------------------------------------
29. Subset II (Leetcode 90)
->
public List<List<Integer>> subsetsWithDup(int[] nums) {
      List<List<Integer>>ans=new ArrayList<>();        
        Arrays.sort(nums);
        
        powerSet(nums,0,new ArrayList<>(),ans);
        return ans;
    }
    public void powerSet(int[]nums,int idx,List<Integer>list,List<List<Integer>>ans){
        ans.add(new ArrayList<>(list));

        for(int i=idx;i<nums.length;i++){
            if(i!=idx && nums[i]==nums[i-1]) // for i = idx (first item of that subset)
                continue; 
             list.add(nums[i]);
            powerSet(nums,i+1,list,ans);
             list.remove(list.size()-1);
        }
        return;
    }
-------------------------------------------------------------------------------------
30. Burst Ballons 
  // we have n! ways to burst the ballons 
    // for eg) {2 3 5} -> a) 2 3 5 , b) 2 5 3 , c) 3 5 2 , d) 3 2 5 , e) 5 2 3 , f) 5 3 2    => 3! = 6 ways
 /*   
    Intuition -> https://www.youtube.com/watch?v=YzvF8CqPafI
    
    1. We know that if only one ballon remains then the coins which we will get is  1*nums[i]*1;
    2. So we can say that we already know the ans for last ballon which get bursted.
    3. Hence we say that for each i we are considering that all the ballons in its left and right already get bursted means 
    it is the last ballon to get burst then what will be the max coins which we can collect.
    4. We are saying this because we know that there is no relation with the already bursted ballons.
   
   dp[i][j] stores that we you burst a range (i,j){ in a definite order } out of the whole array leaving 
   other left and right elements as it is then what is the max coins you can collect.
   
   [a1,a2,a3,a4,(ai,ai1,ai2,ai3,....aj),an-2,an-1,an] <- so here suppose you have ai->aj range.
   Now for this we say that we are bursting 'ai' and (ai1->aj) is already bursted so coins we will get is (a4*ai*an-2);
   when we burst 'ai3', we consider that it is the last ballon to be bursted in the range (ai->aj)<- already bursted.
   so in this case we get coins =>(a4*ai3*an-2);   
 */   

public int maxCoins(int[] nums) {
        return BurstBallons(nums,0,nums.length-1,new int[nums.length][nums.length]);
    }
    public int BurstBallons(int[]nums,int start,int end,int[][]dp){
        if(start>end) return 0;
        
        if(dp[start][end]>0) return dp[start][end];
        
        int ans = 0;
        for(int i=start;i<=end;i++){
            int left=(start>0)?nums[start-1]:1;
            int right=(end<nums.length-1)?nums[end+1]:1;
            
            int sum=left*nums[i]*right + BurstBallons(nums,start,i-1,dp) + BurstBallons(nums,i+1,end,dp);
            ans=Math.max(sum,ans);
        }
        
        return dp[start][end] = ans;    
    }
-------------------------------------------------------------------------------------
31. Rotate Array (in place)
-> Complexity should be O(N).
   
The basic idea is that, for example, nums = [1,2,3,4,5,6,7] and k = 3, first we reverse [1,2,3,4], it becomes[4,3,2,1]; then we reverse[5,6,7], it becomes[7,6,5], finally we reverse the array as a whole, it becomes[4,3,2,1,7,6,5] ---> [5,6,7,1,2,3,4].

Reverse is done by using two pointers, one point at the head and the other point at the tail, after switch these two, these two pointers move one position towards the middle.
    
    public void rotate(int[] nums, int k) {
        
        int n = nums.length;
        
        k = k % n;
        
       reverse(nums,0,n-k-1);
       reverse(nums,n-k,n-1);
       reverse(nums,0,n-1); 
    }
    public void reverse(int[]nums,int l,int h){
        while(l<h){
            
            int temp = nums[l];
            nums[l]=nums[h];
            nums[h]=temp;

            l++;
            h--;
        }
    }
-------------------------------------------------------------------------------------
32. Closest Leaf to a given node in a binary tree
O(N)-S(H)

 public static int INF = 1000000;

    // Function that returns the distance of the closest leaf in the sub tree.
    public static int closestLeafNodeInSubtree(BinaryTreeNode<Integer> root) {
        if (root == null) {
            return INF;
        }

        if (root.left == null && root.right == null){
            // Node is a leaf node.
            return 0;
        }

        int distLeft = closestLeafNodeInSubtree(root.left);
        int distRight = closestLeafNodeInSubtree(root.right);

        return (1 + Math.min(distLeft, distRight));
    }

    private static int ans;

    // Helper function to calculate the closest leaf distance of the node.
    public static int findClosestLeafNodeDistanceHelper(BinaryTreeNode<Integer> root, int x){
        if (root == null){
            return INF;
        }

        // If the required node is found, calculate the distance of the closest leaf node.
        if (root.data == x){
            ans = closestLeafNodeInSubtree(root);
            return 0;
        }

        int distLeft = findClosestLeafNodeDistanceHelper(root.left, x);
        if (distLeft != INF) {
            // Node X is present in left subtree.
            int dist = (distLeft + 2) + closestLeafNodeInSubtree(root.right);
            ans = Math.min(ans, dist);
            return (1 + distLeft);
        }

        int distRight = findClosestLeafNodeDistanceHelper(root.right, x);
        if (distRight != INF) {
            // Node X is present in right subtree.
            int dist = (distRight + 2) + closestLeafNodeInSubtree(root.left);
            ans = Math.min(ans, dist);
            return (1 + distRight);
        }

        // Node X not found in the subtree.
        return INF;
    }

-------------------------------------------------------------------------------------
33. Split BST

public TreeNode[] splitBST(TreeNode root, int V) {
        if (root == null)
            return new TreeNode[]{null, null};
        if (root.val == V) {
            TreeNode right = root.right;
            root.right = null;
            return new TreeNode[]{root, right};
        }
        else if (root.val > V) {
            TreeNode[] nodes = splitBST(root.left, V);
            TreeNode left = nodes[0];
            TreeNode right = nodes[1];
            root.left = right;
            return new TreeNode[]{left,root};
        } else {
            TreeNode[] nodes = splitBST(root.right, V);
            TreeNode left = nodes[0];
            TreeNode right = nodes[1];
            root.right=left;      //since we have gone to root right having values more than root.val either we get left array having values smaller than equal to v or right having greater than V but overall all nodes have values greater than curr node that's why we did this.
            return new TreeNode[]{root, right};
        }
    }
-------------------------------------------------------------------------------------
34. Given a binary search tree and a range [L, R], delete all elements which are not in the range.
(Trim a Binary Search Tree- (LC-669))

O(N)
 private static Node removeOutsideRange(Node root,
                                           int min, int max)
    {
        // BASE CASE
        if(root == null)
        {
            return null;
        }
         
        // FIRST FIX THE LEFT AND
        // RIGHT SUBTREE OF ROOT
        root.left = removeOutsideRange(root.left,
                                       min, max);
        root.right = removeOutsideRange(root.right,
                                        min, max);
         
        // NOW FIX THE ROOT. THERE ARE
        // TWO POSSIBLE CASES FOR THE ROOT
        // 1. a) Root's key is smaller than
        // min value(root is not in range)
        if(root.key < min)
        {
            Node rchild = root.right;
            root = null;
            return rchild;
        }
         
        // 1. b) Root's key is greater than
        // max value (Root is not in range)
        if(root.key > max)
        {
            Node lchild = root.left;
            root = null;
            return lchild;
        }
         
        // 2. Root in range
        return root;
    }
-------------------------------------------------------------------------------------
35. Kth Ancestor of a binary tree

-> https://www.youtube.com/watch?v=PE-kQVZxvWA&t=1895s

  // O(logn) <- for query S(nlogn)
    
   
    int[][] jump;
    int maxPow;

    public TreeAncestor(int n, int[] parent) {
        // log_base_2(n)
        maxPow = (int) (Math.log(n) / Math.log(2)) + 1;
        jump = new int[maxPow][n];
        jump[0] = parent;
        for (int p = 1; p < maxPow; p++) {
            for (int j = 0; j < n; j++) {
                int pre = jump[p - 1][j];
                jump[p][j] = pre == -1 ? -1 : jump[p - 1][pre];
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        int maxPow = this.maxPow;
        while (k > 0 && node > -1) {
            if (k >= 1 << maxPow) {
                node = jump[maxPow][node];
                k -= 1 << maxPow;
            } else
                maxPow -= 1;
        }
        return node;
    }
Similar problem -> 

#) Return the sum of all nodes whose Kth ancestor is even.


-------------------------------------------------------------------------------------
36. A tree is considered special if the sums of all the nodes at each level are in an Arithmetic Progression (AP).
Given the root note of a binary tree. Return an array representing the minimum number that can be added at each level to make that tree special.

We need to solve it in O(N) time and O(1) space.
Bonus : We can't store the sums at each level.

Example -
Input 1:

          3
        /   \
       2     7
        \
	 15

Output: [0, 0, 0] since the sums were already in AP. {3, 9, 15}

Input 2:

          1
        /   \
      11     5
      / \     \
     2   15    10
     \
      50

Output: [0, 0, 4, -4].


Approach:

 	  1 - 1
        /   \
      11     5 - 16
      / \     \ 
      2  15    10 - 27
       \
        50           -50

1. At each level i (total levels here l = 4) am storing the sum, and also through complete traversal i am finding the total sum of the Tree, Here it is 94

2. Now, generalizing the term as An = a + (n-1)d => a = An - (n-1)d.

3. Sum formula  = level/2 * (2a + (level - 1)d) =>

4. Converted Sum formula  => level/2 * (2an + (level - 2*currlevel + 1)d) 

5. At each level we just equate the total sum leaving d as it is and then find the value of d (in case of decimal then two values will be there floor and ceil)for both the values find the sum which is the closest to the actual total sum take that as d in this way we get the d which gives closest sum.

6. So minimum diff between the sum which we get through formula vs the total sum, the d which gives the min that would be our final d

7. At last we have a, d, currlevel just find An th term (equals to sum of that level) and see the actual sum which is present in the tree then take the difference.

Exact sum = [1,16,27,50] , our sum through our a and d = [1,15,31,46], so the output will be [0,0,4,-4].
 
Total Sum =94
Each level sum = [1,16,27,50].
 
All level calculations in order to find the perfect d.
Level 1 =  2*( 2 + 3*d) = 4+ 6d  = 94
			d = 14 ~ 88
			d = 15 ~ 94
Level 2 = 2*(32 + d) = 94
		d = 15 ~ 94 

Level 3 = 2*(54 - d) = 94
     		d = 3 ~102
		d = 4 ~100

Level 4 = 2(100 - 3d) = 94
	d = 17 ~ 98
	d = 18 ~ 92


Through all the levels i got my d as 15 which gives the closest (here exact) sum of the AP.
-------------------------------------------------------------------------------------
38. Dungeon Game (LeetCode 174)

class Solution {
    // For this approach refer the below discuss article and dry run the code (for 2x2 matrix) for a clear understanding.
  //  https://leetcode.com/problems/dungeon-game/discuss/745340/post-Dedicated-to-beginners-of-DP-or-have-no-clue-how-to-start
    
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        
        int[][]dp = new int[m][n];
        
        for(int[]dpp:dp){
            Arrays.fill(dpp,-1);
        }
        
        // 1 is the min energy that must be given because if at any cell king energy becomes <=0 then he dies.
        return  minEnergy(dungeon,0,0,m,n,dp);
    }
    
    public int minEnergy(int[][]cell,int i,int j, int m,int n,int[][]dp){
        if(i==m || j==n)return 100000000;
        
        if(i==m-1 && j==n-1){
            return (cell[i][j]>0)?1:-(cell[i][j])+1;
        }
        
        if(dp[i][j]!=-1)return dp[i][j];
        
        int minEnergyRequired = 0;
        
        int goRight = minEnergy(cell,i,j+1,m,n,dp);
        int goDown = minEnergy(cell,i+1,j,m,n,dp);
        
        minEnergyRequired = Math.min(goRight,goDown) - cell[i][j];
        
        return (dp[i][j] = (minEnergyRequired<=0)?1:minEnergyRequired);
    }
}
-------------------------------------------------------------------------------------
39. Simplify Path (LeetCode 71)
-> Stack based approach
 public String simplifyPath(String path) {
    
        Deque<String>deq = new ArrayDeque<>();
        Set<String> skip = new HashSet<>(Arrays.asList("",".",".."));
        
        for(String str: path.split("/")){
           if(!deq.isEmpty() && str.equals("..")){
               deq.poll();
           }else if(!skip.contains(str)){
               deq.push(str);
           } 
        }
        
        if(deq.isEmpty())return "/";
        
        StringBuilder sb = new StringBuilder();
        while(!deq.isEmpty()){
            sb.append("/").append(deq.pollLast());
        }
        
        return sb.toString();
    }
-------------------------------------------------------------------------------------
40. Maximum Side length of a Square with sum less than or equal to threshold. (leetcode 1292)

M1) O(m*n)

 public int maxSideLength(int[][] mat, int threshold) {
      	// print both the arrays (sum & mat) and also dry run to understand how this prefix sum is
		// being made.
		// sum[i][j] represents the sum of all the elements which makes the rectangle
		// having coordinates -> (0,0),(0,j),(i,0),(i,j);

		int m = mat.length;
		int n = mat[0].length;
		int[][] sum = new int[m + 1][n + 1];

		int res = 0;
		int len = 1;

		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				 // -sum[i-1][j-1] to remove the overlapping part.
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];

		// +sum[i-len][j-len] to add the part which got deleted two times due to overlapping;
		if (i >= len && j >= len && sum[i][j] - sum[i - len][j] - sum[i][j - len] 
						+ sum[i - len][j - len] <= threshold){  
					res = len;
					len++;
				}

			}
		}
		return res;
   	 }

M2) O(m*n*log(min(m,n)))
-> Binary Search and prefix sum.
-> Firstly just like above make a prefix array but not check in the that loop itself.
-> for that take lo = 0, hi = min(m,n) and then apply binary search and in the black box of binary search
check for the condition which has been checked in the above approach in the latter part of the loop.
-> if possible then lo=mid+1 else hi=mid-1;

-------------------------------------------------------------------------------------
41. Avoid Flood in the City (Leetcode 1488)
->
    // Read this approach if any doubt- >https://leetcode.com/problems/avoid-flood-in-the-city/discuss/716206/Java-Well-explained-O(n2)
    
    public int[] avoidFlood(int[] rains) {
       //this map will store the rain corresponds to the prev last index of its occurence
        HashMap<Integer,Integer>map = new HashMap<>();
       
//Dont try to find the zero in treeset as floor(i) for the curr rain which has been previously visited, in this way you
// are ignoring this case -> [0,1,1] here when 1 comes for the first time you just put it in the set and second time when you first 
// when you perform thr function for it to find the prev zero that won't work as it is not a valid case. 
// Instead find the location ahead of the previous occurence of the current rain in the zero treeset as described in the below soln.
       
       
        //this stores the location of zeros in sorted order
        TreeSet<Integer>zeros = new TreeSet<>();
        int n = rains.length;
        int[]res = new int[n];
        
        for(int i=0;i<n;i++){
            if(rains[i]==0){
                zeros.add(i);
                res[i]=1;  //in case this zero could not used.
            }else{
                if(map.containsKey(rains[i])){
                    // find the location of zero that can be used to empty rains[i]
                    Integer next = zeros.ceiling(map.get(rains[i]));
                    //if next is null so you cant dry the lake means there will be flood.
                    if(next==null){
                        return new int[0];
                    }
                    zeros.remove(next); //since this 0 has been used now.
                    res[next]=rains[i];
                }
                res[i]=-1; //according to the problem
                map.put(rains[i],i);
            }
        }
        return res;
    } 
-------------------------------------------------------------------------------------
42. Distinct Subsequences (Leetcode 115)
->  public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        
        int[][]dp = new int[m][n];
        for(int[]dpp:dp){
            Arrays.fill(dpp,-1);
        }
        return distinctSubsequences(s,t,0,0,m,n,dp);
    }
    public int distinctSubsequences(String s,String t, int i,int j,int m,int n,int[][]dp){
        if(j==n){
            return 1;
        }
        if(i==m){
            if(j==n){
                return 1;
            }
            return 0;
        }
        
        if(dp[i][j]!=-1){
            return dp[i][j];
        }        
        
        char c1 = s.charAt(i);
        char c2 = t.charAt(j);
        
        int op1=0,op2=0,op3=0;
        if(c1==c2){
            op1 = distinctSubsequences(s,t,i+1,j+1,m,n,dp);
            op2 = distinctSubsequences(s,t,i+1,j,m,n,dp);
        }else{
            op3 = distinctSubsequences(s,t,i+1,j,m,n,dp);
        }
        return dp[i][j] = op1+op2+op3;
    }
-------------------------------------------------------------------------------------
43. Minimum Difference in sums after removal of elements (Leetcode 2163)
-> Basically the goal is the get the min sum of n/3 elements for the first part and max sum of n/3 elements in the
second part to minimize the difference and the ans will be the min difference of elements lies between (n/3->2*n/3)

public long minimumDifference(int[] nums) {
        int n=nums.length;  //length of nums
        int len3=n/3;       // 1/3 length
        long res=Long.MAX_VALUE; // final result;
        //Try to make first part as min as possible;
        //first[m] store the value, the min value of the size=len3, from[0,1,..., m];  
        long[] first=new long[n]; 
        //Try to make second part as max as possible;
        //second[m] store the value, the max value of the size=len3, from[m,...,n-1];  
        long[] second=new long[n];
        
//--------------------for first part compute -------------------------------------
        //Build max heap for first part;
        PriorityQueue<Integer> max=new PriorityQueue<Integer>(Comparator.reverseOrder());
        
        long sum=0;

        // Initialize with the first 1/3 n part.
        for(int i=0;i<len3;i++){
            sum+=nums[i];
            max.add(nums[i]);
        }
        //For the second part between 1/3 ~ 2/3. When we move to next index.
        //we keep the sum as total 1/3n size: each time poll the max one and add the new one;
        //And we keep tracking the exchange by long[] first;
        //
        for(int i=len3;i<=2*len3;i++){
            first[i]=sum;     //add sum from  1/3
            max.add(nums[i]); //put new one in queue;
            sum+=nums[i];     //sum + new one;
            sum-=max.poll();  //sum - max one;
        }
//--------------------for second part compute -----------------------
        sum=0;
        //Build min heap for first part;
        PriorityQueue<Integer> min=new PriorityQueue<Integer>();
        // Initialize with the last 1/3 n part.
        for(int i=0;i<len3;i++){
            sum+=nums[n-1-i];
            min.add(nums[n-1-i]);
        }
        //For the second part between 2/3~1/3 When we move to next index:
        // we keep update the sum with(+ new element, - min element), and update second;
        for(int i=len3;i<=2*len3;i++){
            second[n-i]=sum;
            min.add(nums[n-1-i]);
            sum+=nums[n-1-i];
            sum-=min.poll();
        }
//-----------------compute the final result------------

        //find the max value in second part [ i,..., n-1];
        //find the min value in first part [0,....,i];
        // find the result;
        for(int i=len3;i<=2*len3;i++){
            res=Math.min(res,first[i]-second[i]);
        }
        
        return res;
    }
-------------------------------------------------------------------------------------
44. Replace the substring for balanced String (leetcode 1234)
Approach Reference -> https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/409017/JAVA-Sliding-Window-Solution-with-Explanation

So Basically we are storing the freq of each character Q,W,E,R and then applying sliding window.
How Sliding window? -> String will be balanced when each of the above characters have exactly n/4 freq.
-> So we just move our right pointer and when we move, we just check that whether the each (freq<=n/4).
-> if yes then it means that we are at our valid substring we can make our ans. 
-> But if not satisfied then keep on decrementing. 
-> let the string be "WQWRWEQW" the first satisfied condition occurs when we have WQW in the window. here it can be replaced by RQE or its any permutation.
-> Since this is valid substring and we can make our ans as min(ans,j-i+1).
-> the window again shrinked by incrementing the freq from left indices.

-> By this approach the problem boils down to minimum length substring containing a certain number of each character.  and the certain number is (all character having freq <=n/4)

    // It is a tricky question just dry run to understand it better for the case "WQWRWEQW"-> 3 is the ans.
    public int balancedString(String s) {        
        
        int[] count = new int[128];
        int n = s.length(), res = n, left = 0, k = n / 4;
        for (int j = 0; j < n; j++) {
            count[s.charAt(j)]++;
        }
        for (int right = 0; right < n; right++) {
            count[s.charAt(right)]--;
            while (left < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
                res = Math.min(res, right - left + 1);
                count[s.charAt(left++)]++;
            }
        }
        return res;
    }
-------------------------------------------------------------------------------------
45. Longest Substring without Repeating Characters (Leetcode 3)
-> Sliding window approach

public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        
        int i=0,j=0;
        Set<Character>set = new HashSet<>();
        
        int res=0;
        
        while(j<n){
            char ch = s.charAt(j);
            if(!set.contains(ch)){
                set.add(ch);
                res = Math.max(res,j-i+1);
                j++;
            }else{
                while(set.contains(ch) && i<j){
                    set.remove(s.charAt(i));
                    i++;
                }
            }
        }
        return res;
    }
-------------------------------------------------------------------------------------
46. Longest Continuous Subarray with Absolute Diff less then Equal to Limit
-> Basically "Absolute difference between min and max elements of subarray"

-> Why are we shrinking when we get difference greater than limit?
=> Because the max Deque now contains max element in ith-jth window now if any element comes if smaller then the difference will not decrease(means the peekFirst will not change) but if bigger then difference will increase.
Similarly for the min Deque the peekFirst of this can also be changed when the curr element is even smaller than the peekFirst & if it happens then the min becomes more min resulting the difference will increase. 
That's why we are shrinking.


 public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int i =0,j=0;
        
        Deque<Integer>max = new LinkedList<>();
        Deque<Integer>min = new LinkedList<>();

        int res=0;
        
        while(j<n){
            
            while(!max.isEmpty() && nums[j]>max.peekLast()){
                max.pollLast();
            }
            while(!min.isEmpty() && nums[j]<min.peekLast()){
                min.pollLast();
            }
            
            min.addLast(nums[j]);
            max.addLast(nums[j]);
            
            while(max.peekFirst()-min.peekFirst()>limit){
              if(max.peekFirst()==nums[i])max.pollFirst();
              if(min.peekFirst()==nums[i])min.pollFirst();
              i++;
            }
            res = Math.max(res,j-i+1);            
            j++;
        }
        
        return res;
    }
-------------------------------------------------------------------------------------
47. Frequency of the most frequent element (Leetcode-1838)

M1) Sliding window approach 
Sort the input array.

the key is to find out the valid condition:
k + sum >= size * max  <- just take a dry run to understand this part.
which is
k + sum >= (j - i + 1) * A[j]

public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        
        int n = nums.length;
        int i=0,j=0;
        int res = 0 ;
        long sum = 0;
                
        while(j<n){
            sum+=nums[j];
            while(sum+k < (j-i+1)*nums[j]){
                sum-=nums[i];
                i++;
            }
            res = Math.max(res,j-i+1);
            j++;
        }
        return res;
    }


M3) Binary Search <- little bit complex
-> https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1175181/JavaPython-Prefix-Sum-and-Binary-Search-O(NlogN)
-------------------------------------------------------------------------------------
48. Reduce array size to the half (Leetcode-1338)

M1) Use priorityQueue and map, and remove all the occurence of the most freq and then pop from priorityQueue and do this for all until the count becomes greater than equal to array size/2.
the elements we be added int the set or we can maintain another count.

 public int minSetSize(int[] arr) {
        HashMap<Integer,Integer>map = new HashMap<>();
        
        for(int i=0;i<arr.length;i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        
        PriorityQueue<Integer>hp = new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
        hp.addAll(map.keySet());
        
        int count=0;
        int size=arr.length/2;
        
        Set<Integer>set = new HashSet<>();
        while(count<size){
            int key = hp.poll();
            set.add(key);
            count+=map.get(key);
            map.remove(key);
        }
        return set.size();
    }


M2) Using Kind of Bucket

public int minSetSize(int[] arr) {
	Map<Integer, Integer> map = new HashMap<>();
	ArrayList<Integer>[] list = new ArrayList[arr.length + 1];
	
	for (int num : arr) {
		map.put(num, map.getOrDefault(num, 0) + 1);
	}

	for (int num : map.keySet()) {
		int count = map.get(num);
		if (list[count] == null) {
			list[count] = new ArrayList<Integer>();
		}
		list[count].add(num);  
	}
	
	int steps = 0, res = 0;
	for (int i = arr.length; i > 0; i--) {
		List<Integer> cur = list[i];
		if (cur == null || cur.size() == 0) continue;
		for (int num : cur) {
			steps += i;	// at this freq there can be multiple elements that's why adding i
			res++;
			if (steps >= arr.length / 2)
				return res;
		}
	}
	return arr.length;
}
-------------------------------------------------------------------------------------
49. Remove K Digits (Leetcode 402)
->
public String removeKdigits(String num, int k) {
    Deque<Integer> st = new LinkedList<>();

		for (int i = 0; i < num.length(); i++) {
			int val = num.charAt(i) - '0';
			while (!st.isEmpty() && st.peekLast() > val && k > 0) {
				st.pollLast();
				k--;
			}
			st.addLast(val);
		}
        while(!st.isEmpty() && k>0){
            st.pollLast();
            k--;
        }
        
		StringBuilder sb = new StringBuilder();
		while (!st.isEmpty()) {
			int val = st.pollFirst();
			if (val == 0 && sb.length() == 0)
				continue;
			sb.append(val);
		}
        if(sb.length()==0)return "0";
		return sb.toString();
    }
-------------------------------------------------------------------------------------
50. Minimize Deviation in Array (LC-1675)

-> Time Complexity :- BigO(NlogNlogM) where N is the highest value in the array
-> Space Complexity :- BigO(N)

Intuition: Here we need to increase the min and decrease the max.
-> if min was odd it got increased to its double value. if it was even then its already at its maximum.
-> Now we want to decrease the max value, it have become odd after dividing by 2. 
-> At some point when we get our peak(highest) value and if it is not even that we will stop dividing because at this point we have decreased max values
at their lowest point.

public int minimumDeviation(int[] nums) {
        // First create a priority Queue
        // and implemented a custom comperator, which help us in making this priority queue act like a max heap
        // concept of max heap states that, highest value should lie at the front of the queue & lowest value at the back of the queue
        PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a); // so we apply the custom comperator over here
        
        int min=Integer.MAX_VALUE; // creating minimum variable
        for(int i:nums){ // add these values in priority queue
            if(i%2==1) i*=2; // if value is odd mult. by 2 & make it even
            min=Math.min(min,i); // find the minimum
            pq.add(i);
        } // now we have the value in the priority queue, where we have convert all the odd's into even
        
        // let's find the maximum of all the value
        int diff=Integer.MAX_VALUE; 

        while(pq.peek()%2==0){ 
            int max=pq.remove(); // max will be at top of the queue
            diff=Math.min(diff,max-min); // find the difference
            min=Math.min(max/2,min);//minimum can change because, new value we are getting by half max can be lower then current minimum
            pq.add(max/2); // add that in the queue
        }
        
        return Math.min(diff,pq.peek()-min);
    }
-------------------------------------------------------------------------------------
51. Generate Parenthesis (LC-22)
->
 public void generateParenthesis(List<String>ans,String str,int open,int close,int n){
        
        if(open>n || close>open)return;
        
        if(open==close){
            if(open==n){
                ans.add(str);
                return;    
            }
        }
            
        generateParenthesis(ans,str+"(",open+1,close,n);
        generateParenthesis(ans,str+")",open,close+1,n);
    }
-------------------------------------------------------------------------------------
52. Shortest Path visting all nodes (LC-847)

-> In this problem we have to find the length of shortest path that visits evey node.
(you may revisit nodes multiple times, you may reuse edges).

-> 3 points to cover
1) We can't use normal BFS here. (because it doesn't visit visited nodes)
2) We don't want to get stuck in cycle.
3) We have to start with each node in order to check which yields to shortest path.

-> So here basically we are storing a pair of (node, its bit) in the Queue to traverse (BFS)
-> Here bit refers the path the current node has visited.
-> So initially we are storing evey node acc to point 3 above.
-> Since at starting it only visits the current path so only curr bit will be set.
-> We are taking a Set of String in order to track of the visited path by a node (not a visited node we are focusing, instead we are more focused on visited path here acc to problem).
-> If visited path (node-bit_Path) then continue else visit it and put in queue to traverse.
-> In order to know that have we visited all the nodes, will be checked using the mask suppose there are 3 nodes so, at any point if we get a path. "111" which is 7 that means we have visited all nodes.


public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int mask = (1<<n)-1; //represents path covering each node.
        
        Queue<int[]>q = new LinkedList<>();
        Set<String>visPath = new HashSet<>();
        
        for(int i=0;i<n;i++){
            q.offer(new int[]{i,1<<i});  //node-curr_bit. eg if n = 1 , bit = 010 (0 based indexing)
            visPath.add(i+":"+(1<<i));
        }
        
        int count = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0;i<size;i++){
                int[]rnode = q.poll();
                if(rnode[1]==mask)return count;  //at any time we get the path which covers all nodes.
                
                for(int node:graph[rnode[0]]){
                    int next = rnode[1] | (1<<node);
                    if(visPath.contains(node+":"+next))continue;
                    visPath.add(node+":"+next);
                    q.offer(new int[]{node,next});
                }
            }
            count++;
        }
        return count;
    }
-------------------------------------------------------------------------------------
53. Swim in Rising Water (LC-778)
-> DFS + Binary Search (can be solved using dikstra + BFS/DFS also)

-> O(n*n*logn)
   
public int swimInWater(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int n = grid.length;
        int start = grid[0][0];
        int end = n * n - 1;
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        
       int ans=0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            int[][] visited = new int[n][n];
            if (possible(grid, mid, 0, 0, dx, dy, visited)) {
                ans = mid;
                end = mid-1;
            } else {
                start = mid + 1;
            }
        }
        return ans;
    }
    private boolean possible(int[][] grid, int cur, int x, int y, int[] dx, int[] dy, int[][] visited) {
        visited[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            if (newX >= 0 && newY >= 0 && newX < grid.length && newY < grid[0].length && visited[newX][newY] == 0 && cur >= grid[newX][newY]) {
                if (newX == grid.length - 1 && newY == grid[0].length - 1) {
                    return true;
                }
                if (possible(grid, cur, newX, newY, dx, dy, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

Similar Problem -> Path with Minimum Effort (LC-1631)
-> Exact same approach but the difference is just 
instead of (cur>=grid[newX][newY]) -> here we will use (cur>=Math.abs(grid[newX][newY]-grid[x][y]);
-------------------------------------------------------------------------------------
54. Arithmetic Slices (LC-413)

  public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if(n<3)return 0;
        
        int pdiff = nums[1]-nums[0];
        
        int count=0;
        int sum=0;
        for(int i=2;i<n;i++){
             int diff = nums[i]-nums[i-1];
           
                if(diff==pdiff){
                    count++;
                   sum+=count;
                }else{
                    count=0;
                }
            pdiff=diff;
        }
        return sum;
    }
-------------------------------------------------------------------------------------
55. 132 Pattern (LC-456)

   public boolean find132pattern(int[] nums) {
// we are basically finding greatest element traversing from right.
// and when we get the potential greatest element, the element which was on top of stack at last, is the 
// element which is smaller than the greatest element, now we check that if nums[i]<smaller element.
// if yes that means it is the smallest element.

     Stack<Integer>st = new Stack<>();
       int s2 = Integer.MIN_VALUE;
        
        for(int i=nums.length-1;i>=0;i--){
            if(nums[i]<s2)return true;  //checking if any number is smaller than 2nd which could be 1st ele
            
            while(!st.isEmpty() && nums[i]>st.peek()){
                s2=st.pop();
            }
            // after end of this loop we will get our potential greatest element.
            st.push(nums[i]);
        }
        return false;
    }
-------------------------------------------------------------------------------------
56. Champagne Tower (LC-799)
-> Used concept of pascals triangle 

  public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] quantity = new double[query_row+1][query_glass+2];
        
        quantity[0][0]=poured;
        
        for(int i=0;i<query_row;i++){
            for(int j=0;j<=query_glass;j++){
                double rem = Math.max(quantity[i][j]-1,0.0);
                quantity[i+1][j] += rem/2.0;
                quantity[i+1][j+1] += rem/2.0;
            }
        }
        return Math.min(quantity[query_row][query_glass],1.0); //because it champagne did not reach to last then it will give, 
        // and if it reaches at last but value is more than 1 then it pours down from the glass and ultimately volume of the wine becomes 1 only.
    }
-------------------------------------------------------------------------------------
57. Delete and Earn 

M1) House robber Approach
-> https://leetcode.com/problems/delete-and-earn/discuss/109891/Sharing-my-Simple-Straight-Forward-Java-O(n)-Solution-Explanation-Included

 public int deleteAndEarn(int[] nums) {
        int[] sum = new int[10002]; 
        
        for(int i = 0; i < nums.length; i++){
            sum[nums[i]] += nums[i]; 
        }
        
        for(int i = 2; i < sum.length; i++){
            sum[i] = Math.max(sum[i-1], sum[i-2] + sum[i]);
        }
        return sum[10001];
    }

 M2) Top Down Dp
 (take/noTake)
 
  public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        
        int[]dp = new int[nums.length];
        Arrays.fill(dp,-1);
        return maxPoints(nums,0,dp);
    }
    public int maxPoints(int[]nums,int idx,int[]dp){
        if(idx==nums.length)return 0;
        
        if(dp[idx]!=-1)return dp[idx];
        
        int ele = nums[idx];
        int skip = idx+1;
        int earn = nums[idx];
        
        //collecting all same/duplicates elements 
        while(skip<nums.length && nums[skip]==nums[idx]){
            earn+=nums[idx];
            skip++;
        }
        
        //skipping the nums[i]+1 elements;
        
        while(skip<nums.length && nums[skip]==nums[idx]+1){
            skip++;
        }
        //take
        earn+=maxPoints(nums,skip,dp);
        //no take
        int notEarn = maxPoints(nums,idx+1,dp);
        
        return dp[idx]=Math.max(earn,notEarn);
    
    }   
-------------------------------------------------------------------------------------
58. Count all Valid Pickup and Delivery options (LC-1359)
Explanation: https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/discuss/516951/C%2B%2BJava-Simple-Math-Formula-with-Explanation

Place P2 D2 to 1 result from case n=1: (__ P1 __ D1 __), there are 3 spaces to place to

The result will be:
(P2 D2 P1 D1) (P2 P1 D2 D1) (P2 P1 D1 D2)
(P1 P2 D2 D1) (P1 P2 D1 D2)
(P1 D1 P2 D2)

-> Mathematical problem
 public int countOrders(int n) {
        long ans=1;
        long mod = (long)(1e9+7);
        
        for(int i=2;i<=n;i++){
            long spaces = (i-1)*2+1; // (__ P1 __ D1 __)
            ans*=spaces*(spaces+1)/2;
            ans%=mod;
        }    
        
        return (int)ans;
    }
-------------------------------------------------------------------------------------
59. Longest Arithmetic Subsequence (LC-1027)

-> Similar problem in this file problem-13 but with a given difference

public int longestArithSeqLength(int[] nums) {
        
// dp[index][diff] equals to the length of arithmetic sequence at index with difference diff.
        int res = 2; 
        int n = nums.length;
        HashMap<Integer,Integer>[] dp = new HashMap[n];
        
        for(int i=0;i<n;i++){
            dp[i]=new HashMap<>();
            for(int j=0;j<i;j++){
                int diff = nums[i]-nums[j];
                
                //just as we do in LIS. 
                dp[i].put(diff,dp[j].getOrDefault(diff,1)+1);
                
                res = Math.max(res,dp[i].get(diff));
            }
        }
        return res;
    }

-------------------------------------------------------------------------------------
60. Sort the Matrix Diagonally
Time O(MNlogD), where D is the length of diagonal with D = min(M,N).
Space O(MN)
-> Intuition:
-> A[i][j] on the same diagonal have same value of (i - j).
-> For each diagonal, put its elements together, sort, and set them back.

public int[][] diagonalSort(int[][] mat) {
        HashMap<Integer,PriorityQueue<Integer>> d = new HashMap<>();
        
        for(int i=0;i<mat.length;i++){
            for(int j=0;j<mat[i].length;j++){
                d.putIfAbsent(i-j,new PriorityQueue<>());
                d.get(i-j).add(mat[i][j]);
            }
        }
        
        for(int i=0;i<mat.length;i++){
            for(int j=0;j<mat[i].length;j++){
                mat[i][j]=d.get(i-j).poll(); 
                //this way getting minimum element each time using PriorityQueue
            }
        }
        return mat;
    }
-------------------------------------------------------------------------------------
61. Car Fleet (LC-853)

Logic: 
Sort cars by the start positions pos
Loop on each car from the end to the beginning
Calculate its time needed to arrive the target
cur records the current biggest time (the slowest)

If another car needs less or equal time than cur,
it can catch up this car fleet.

If another car needs more time,
it will be the new slowest car,
and becomes the new lead of a car fleet.


Complexity:
O(NlogN) Quick sort the cars by position. (Other sort can be applied)
O(N) One pass for all cars from the end to start (another direction also works).

O(N) Space for sorted cars.
O(1) space is possible if we sort pos inplace. 

->
 public int carFleet(int target, int[] pos, int[] speed) {
        int N = pos.length, res = 0;
        double[][] cars = new double[N][2];
        for (int i = 0; i < N; ++i)
            cars[i] = new double[] {pos[i], (double)(target - pos[i]) / speed[i]};
        Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));
        double cur = 0;
        for (int i = N - 1; i >= 0 ; --i) {
            if (cars[i][1] > cur) { // means car cannot reach target in less or equal time than its ahead car, which makes a new fleet.
                cur = cars[i][1];
                res++;
            }
        }
        return res;
    }   
-------------------------------------------------------------------------------------
62. Brick Wall (LC-554)

->The idea is straightforward, since each brick length is positive, we can record all the edge index in the wall and figure out which edge index is the most common. We cut through that edge index, it will cross number of rows - most common edge count rows

 public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap();
        
        int count = 0;
        for (List<Integer> row : wall) {
            int sum = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                sum += row.get(i);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
                count = Math.max(count, map.get(sum));
            }
        }
        
        return wall.size() - count;
    }
-------------------------------------------------------------------------------------
63. Length of Longest Fibonacci Subsequence (LC-873)
-> Here dp[i][j] represents the length of longest sequence which ends with A[i] and A[j].

 public int lenLongestFibSubseq(int[] arr) {
       
        int n = arr.length;
        int[][]dp = new int[n][n];
        HashMap<Integer,Integer>map = new HashMap<>();
        
        int max = 0;
        
        for(int i=0;i<n;i++){
            
            map.put(arr[i],i);
            
            for(int j=0;j<i;j++){
                Integer k = map.get(arr[i]-arr[j]);
                // the number arr[i]-arr[j] should be smaller than arr[j] because arr[j] is second number and 
                // if k is found then arr[k] will be first number.
                if(arr[i]-arr[j]<arr[j] && k!=null){
                    dp[i][j] = dp[j][k]+1; 
                    max = Math.max(max,dp[i][j]);
                }else{
                    dp[i][j] = 2;
                }
            }
        }
        
        return (max>2)?max:0;
    }

-------------------------------------------------------------------------------------
64. Score of parenthesis

-> My Approach
 public int scoreOfParentheses(String s) {
        Stack<String>st = new Stack<>();
        
        char[]crr = s.toCharArray();
        for(int i=0;i<crr.length;i++){
            if(crr[i]=='('){
                st.push("(");
            }else{
                if(st.peek()=="("){
                    st.pop();
                    st.push("1");
                    continue;
                }
                
                int num = 0;
                while(!st.isEmpty() && st.peek()!="("){
                    num+=Integer.parseInt(st.pop());
                }
                st.pop();
                st.push(2*num+"");
            }
        }
        int res = 0;
        
        while(!st.isEmpty()){
            res+=Integer.parseInt(st.pop());
        }
        return res;
    }

M1) Using Stack
->
cur record the score at the current layer level.

If we meet '(',
we push the current score to stack,
enter the next inner layer level,
and reset cur = 0.

If we meet ')',
the cur score will be doubled and will be at least 1.
We exit the current layer level,
and set cur += stack.pop() + cur

Complexity: O(N) time and O(N) space

    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack<>();
        int cur = 0;
        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(cur);
                cur = 0;
            } else {
                cur = stack.pop() + Math.max(cur * 2, 1);
            }
        }
        return cur;
    }

 M2) S(1)
->

 A deeper understanding of the idea above. (also for people who found approach 2 hard to get)

It just occurs to me the input can be treated as a tree. Every () is a tree node. ()() can be treated as two sibling nodes while (()) can be treated as a parent and a child node. Each leaf node has value 1 while non-leaf node has double the value of all of its direct children's value. All we have to do is to calculate the root node value via post-order traverse. And this is exactly what the approach 1 did as it always get the value of deeper layers before gets its' own value! For example, the S = '(()(()()))' can be treated as the tree below.

                            (10)            layer 0
                            ／ \
                          (1)  (4)          layer 1
                               /  \
                             (1)  (1)       layer 2
Basically, the approach 2 is using the same idea. As you can see, the value of the root node is the sum of each leaf node value to the power of it's depth.
There are three leaf nodes in the tree. One leaf in layer 1 and two leafs in layer 2. So the final answer is 2^1 + 2^2 + 2^2 = 10.
By the way, approach 2 runs faster than approach 1 theoretically as it dose not calculate the intermediate nodes value.

/---------Another Explanation------------------/
When you see parentheses in problem forlumation you should think about stack and indeed, there is stack solution for this problem. This solution will be optimal in time, but in place we can do better! Let us look at the following string:
(((()))(()(()))) and try tu understand what will be the score of such string.
First of all it can be written as 2 * ((()))(()(())), which can be written as 2*((())) + 2*(()(())) = 2*2*(()) + 2*2*() + 2*2*(()) = 2*2*2 + 2*2 + 2*2*2 = 20 and it helps us to notice that what acutally matters is how many () we meet in our string, and how deep they are located. So, let us traverse through our string, keep bal: balance, or depth of current place, that is how many brackets we need to close to get correct expression, and also if we see (), we update ans += 1<< bal.

Code: 
public int scoreOfParentheses(String S) {
    int score = 0;
    int depth = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            depth++;
        } else {
            depth--;
        }

        if (s.charAt(i) == ')' && s.charAt(i - 1) == '(') {
            score += Math.pow(2, depth);
        }
    }

    return score;
}
-------------------------------------------------------------------------------------
65. Queue Reconstuction by Height (LC-406)
M1) O(n^2)
-> using comparator and linkedlist

public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,new Comparator<>(){
           @Override
            public int compare(int[]a,int[]b){
                if(a[0]==b[0]){
                    return a[1]-b[1]; 
                }else{
                    return b[0]-a[0];
                }
            } 
        });
        
        
        LinkedList<int[]>list = new LinkedList<>();
        
        for(int[]a:people){
            list.add(a[1],a);
        }
        int i = 0;
        int[][]res = new int[people.length][2];
        
        for(int[]v:list){
            res[i++] = v;
        }
        
        return res;
    }


M2) O(nlogn) using modified mergeSort
-> https://leetcode.com/problems/queue-reconstruction-by-height/discuss/143403/O(nlogn)-modified-merge-sort-solution-with-detailed-explanation
M3) Using Binary Index Tree
-------------------------------------------------------------------------------------
66. Longest Arithmetic Progression path in a given Binary Tree
-> https://www.geeksforgeeks.org/longest-arithmetic-progression-path-in-given-binary-tree/

-> Approach: The catch here is that a tree node can only support two AP’s, one with the left child and the other one with the right child. Now, to solve this problem, follow the below steps:

Create a variable ans to store the length of the longest path.
Start a depth-first search from the root node, and for each node, find the maximum length path of AP’s till left child and right child.
Now find the difference between the current node and its left child, say leftDiff and the difference between the current node and its right child, say rightDiff.
Now find the longest path with difference leftDiff in the left child, say maxLen1 and longest path with difference rightDiff in the right child, say maxLen2.
If leftDiff = (-1)*rightDiff, then both the branches of the current node form an AP, so change ans to the maximum out of the previous value of ans and maxLen1+maxLen2+1.
Else,  change ans to the maximum out of the previous value of ans, (maxLen1+1) and (maxLen2+1), because only one of the two paths can be selected.
Now return maxLen1 and maxLen2 along with the difference of the AP from the current node to the parent node.
Print ans after the function stops.

    static class pair{
        int diff;
        int maxlen;
        public pair(int d,int m){
            this.diff = d;
            this.maxlen = m;
        }
    }

    static int ans = 0;
    
    public static pair[] maxApPath(Node node){
        pair[]lp = {new pair(Integer.MAX_VALUE,0),new pair(Integer.MAX_VALUE,0)};
        pair[]rp = {new pair(Integer.MAX_VALUE,0),new pair(Integer.MAX_VALUE,0)};


        int leftDiff = Integer.MAX_VALUE;
        int rightDiff = Integer.MAX_VALUE;

        if(node.left!=null){
            lp = maxApPath(node.left);
            leftDiff = node.data - node.left.data;
        }
        
        if(node.right!=null){
            rp = maxApPath(node.right);
            rightDiff = node.data - node.right.data;
        }

        int leftMaxLen = 0;
        int rightMaxLen = 0;

//it may be possible that node's left has same difference in its left as well as right, so we take maxAplen from both of the lengths.
        // node's left's left 
        if(lp[0].diff==leftDiff || lp[0].diff==Integer.MAX_VALUE){
            leftMaxLen = lp[0].maxlen;
        }

        //node's left's right
        if(lp[1].diff==leftDiff || lp[1].diff==Integer.MAX_VALUE){
            leftMaxLen = Math.max(leftMaxLen,lp[1].maxlen);
        }


        if(rp[0].diff==rightDiff || rp[0].diff==Integer.MAX_VALUE){
            rightMaxLen = rp[0].maxlen;
        }

        if(rp[1].diff==rightDiff || rp[1].diff==Integer.MAX_VALUE){
            rightMaxLen = Math.max(rightMaxLen,rp[1].maxlen);
        }

        //below line means curr node can be part of both left and right ap
        if(leftDiff==(-1)*rightDiff){
            ans = Math.max(ans,leftMaxLen + rightMaxLen + 1);
        }else{
            ans = Math.max(ans,Math.max(leftMaxLen+1,rightMaxLen+1));
        }

        return new pair[]{new pair(leftDiff,leftMaxLen+1),new pair(rightDiff,rightMaxLen+1)};
    }

-------------------------------------------------------------------------------------
67. Minimum Cost Tree from Leaves (LC-1130)
M1) Partition Dp
->O(N^3)

//     {minSum,maxLeaf}
    public int[] maxCountTree(int[]arr,int si,int ei,int[][][]dp){
        if(si==ei){
            return new int[]{0,arr[si]};
        }
        
        if(dp[si][ei][0]!=0)return dp[si][ei];
    
        int ans = Integer.MAX_VALUE;
        int maxLeaf = 0;
        
        for(int k=si;k<ei;k++){
            int[] left = maxCountTree(arr,si,k,dp);
            int[] right = maxCountTree(arr,k+1,ei,dp);
            
            maxLeaf = Math.max(maxLeaf,Math.max(left[1],right[1]));
            
            int overAll = left[1]*right[1] + left[0] + right[0];
            ans = Math.min(ans,overAll);
        }
        return dp[si][ei]=new int[]{ans,maxLeaf};
    }
M2) Using Monotonic Stack O(N)

/*
When we build a node in the tree, we compared the two numbers a and b.
In this process,
the smaller one is removed and we won't use it anymore,
and the bigger one actually stays.

The problem can translated as following:
Given an array A, choose two neighbors in the array a and b,
we can remove the smaller one min(a,b) and the cost is a * b.
What is the minimum cost to remove the whole array until only one left?

To remove a number a, it needs a cost a * b, where b >= a.
So a has to be removed by a bigger number.
We want minimize this cost, so we need to minimize b.

b has two candidates, the first bigger number on the left,
the first bigger number on the right.

The cost to remove a is a * min(left, right).
*/    
    public int mctFromLeafValues(int[] arr) {  
        // if we take out stack's top (call it mid) then the current stack's top is next greater element in left,
        // and curr array's element which is greater than the mid is the next greater element in right.
        
        int res=0;
        Stack<Integer>st = new Stack<>();
        st.push(Integer.MAX_VALUE);
        
        for(int a:arr){
            while(st.peek()<=a){
                int mid = st.pop();
                res+= mid * Math.min(st.peek(),a);
            }
            st.push(a);
        }
        
        while(st.size()>2){
            res+=(st.pop()*st.peek());
        }
        
        return res;
    }    
-------------------------------------------------------------------------------------
68. Minimum Weighted Subgraph With the Required Paths (LC-2203)
-> Use Dijkstra here (3 times)
Intuition:  We ony get minimum weight subgraph when the two paths from src1 and src2 will coincide at one node, and the remaining part to dest will be the same for both paths.
So, we find the shortest path from src1 to all other nodes. and same for src2.
we then find shortest path from dest to all other nodes, this can be done by reversing the edges of the graph.

-> src1 to ith node + src2 to ith node + ith node to dest node
here we just find that common node such that it leads to minWeighted Graph.

Finally the min ans will be =>  ans = Math.min(ans,da[i]+db[i]+dd[i]); 
we do this for all i and in the loop we also check that their of them is at Long.MAX_VALUE at any index and if it is then continue;
-> because above condition checks that the path exists from these nodes to the other.

M2) 1-Time Dijkstra -> https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/discuss/1844479/Simultaneous-Dijkstra-beats-100-(only-1-dijkstra)
-------------------------------------------------------------------------------------
69. Parition Lables (LC-763)
->

 public List<Integer> partitionLabels(String S) {
          if(S == null || S.length() == 0){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        int[] map = new int[26];  // record the last index of the each char

        for(int i = 0; i < S.length(); i++){
            map[S.charAt(i)-'a'] = i;
        }
        // record the end index of the current sub string
        int last = 0;
        int start = 0;
        for(int i = 0; i < S.length(); i++){
            last = Math.max(last, map[S.charAt(i)-'a']);
            if(last == i){  //it means the max end has been reached in the curr substring hence it can be a partition
                list.add(last - start + 1);
                start = last + 1;
            }
        }
        return list;
    }
-------------------------------------------------------------------------------------
70. Longest String Chain (LC-1048)
-> You can write LIS code also here (n^2).
-> and instead of checking increasing just check whether there is one difference in the character or not using below function

public boolean checkingfunction(char[]c1, char[] c2){
        if(c1.length != c2.length+1) return false;
        int first=0;
        int second=0;
        //c1 is greater or 
        while(first<c1.length){
            if(c1[first]==c2[second]){
                first++;
                second++;
            }else{
                first++;
            }
        }

        return first==c1.length && second==c2.length;
}

->
public int longestStrChain(String[] words) {
        HashMap<String,Integer>dp = new HashMap<>();
        Arrays.sort(words,(a,b)->(a.length()-b.length()));
        
        int ans=0;
        
        for(String word:words){
            int best = 0;
            
            for(int i=0;i<word.length();i++){
                String prev = word.substring(0,i) + word.substring(i+1);
                best = Math.max(best,dp.getOrDefault(prev,0)+1);
            }
            dp.put(word,best);
            ans = Math.max(ans,best);
        }
        return ans;
    }
-------------------------------------------------------------------------------------
71. Maximum Values of K Coins from Piles (LC-2218)
-> 
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[][]dp = new int[piles.size()+1][k+1];
        
        for(int[]dpp:dp)Arrays.fill(dpp,-1);
        
        return maxValueOfCoins(piles,0,k,dp);
    }
    
    public int maxValueOfCoins(List<List<Integer>>piles,int pi,int k,int[][]dp){
        if(k==0 || pi == piles.size()){
            return 0;
        }
        
        if(dp[pi][k]!=-1){
            return dp[pi][k];
        }
        // either you no take or you take (either some elements or its maxlimit elements which can be taken upto k)
        int notTake = maxValueOfCoins(piles,pi+1,k,dp);
        
        int take=0,collect=0;
        
        for(int i=0;i<Math.min(k,piles.get(pi).size());i++){
            collect+=piles.get(pi).get(i);
            take = Math.max(take,collect+maxValueOfCoins(piles,pi+1,k-i-1,dp));
        }
        return dp[pi][k] = Math.max(notTake,take);
    }
-------------------------------------------------------------------------------------
72. Find Palindrome With Fixed Length (LC-2217)
-> 
M1) 
 public long[] kthPalindrome(int[] queries, int intLength) {
        long[]limit = new long[16];
        limit[1] = 9;
        limit[2] = 9;
        // just verify this using _ _ _ _ _ (means by putting just like in permutation)and you will get to know the intuition
        for(int i=3;i<16;i++){
            long t = 9;
            for(int j = 2;j<=(i+1)/2;j++){
                t*=10;
            }
            limit[i]=t;
        }
        
        long[]ans = new long[queries.length];
        for(int i=0;i<ans.length;i++){
            if(queries[i]<=limit[intLength]){
                ans[i]=nthPalindrome(queries[i],intLength);
            }else{
                ans[i]=-1;
            }
        }
        return ans;
    }
    static long nthPalindrome(int n, int k){

        int temp = (k & 1)!=0 ? (k / 2) : (k/2 - 1);
        int palindrome = (int)Math.pow(10, temp);
        palindrome += n - 1;

        String ans =  palindrome+""; 
   
 
        if ((k & 1)>0)
            palindrome /= 10;
 
        while (palindrome>0)
        {   ans+=(palindrome % 10);
            palindrome /= 10;
        }
        
        return Long.parseLong(ans);
    }

 M2)
 /*
First Palindrome of length 4 = "10"+"01"
First Palindrome of length 3 = "10"+"_1" (without first character 0)
First half can range from 10 (which is 10^1) to 99 (which is 10^2-1)
*/
    public long[] kthPalindrome(int[] queries, int intLength) {
        long[] result = new long[queries.length];
        int i = 0;
        for(int num: queries){
            long half = (intLength+1)/2;//half for 3 =2, half for 4 = 2
            long start = (long)Math.pow(10,half-1);
            long end = (long)Math.pow(10,half)-1;
            if(num<=(end-start+1)){ //check if query is within range
                String firstHalfOfPalindrome = ((start)+ (num-1))+"";
                String secondHalf = (new StringBuffer(firstHalfOfPalindrome)).reverse().toString();
                result[i++] = Long.parseLong(firstHalfOfPalindrome+secondHalf.substring(intLength%2)); // since half is calculated as 1 extra for odd numbers, remove the first char for odd length in substring - 1001 vs 10+(0)1 
            }else{
                result[i++]=-1;
            }
        }
        return result;
    }   
-------------------------------------------------------------------------------------
73. Largest palindromic number by permuting digits
-> Take a HashMap and collect all numbers;
-> To become valid palindrom :
a) Either all numbers have even frequency.
b) Or only one number has odd frequency
-> Now after checking for validity of palidrome number, just take an array of [ size  = dig(num) ]
-> Now when greedily go through every single digit from 9->0 (using loop)
-> Take front and rear pointers -> and put digits.
    largest[front] = (char)(i + 48);
    largest[l - front - 1] = (char)(i + 48);
-> If Even frequency digit occurs then do above thing, but if odd frequency digit occur then for 1 occurence do [ arr[len/2]=num ], and for rest occurences just do like above.
-------------------------------------------------------------------------------------
74. Minimum Number of Removals to Make Mountain Array (LC-1671)
-> Same as Longest Bitonic subsequence
ans => n-lbs(arr);

In Longest Bitonic Subsequence (either increasing or decreasing or increasing then decreasing)
-> dp1 array will store the Lis from left side
-> dp2 array will store the Lis from right side
-> for longest bitonic subsequence find Max(dp1[idx]+dp2[idx]-1);

->
public int minimumMountainRemovals(int[] nums) {
        int n=nums.length;
        int []left=new int [n]; // maximum increasing subsequence in the left of an element.
        int []right=new int [n]; // maximum increasing subsequence in the left of an element.
        Arrays.fill(left,1);
        Arrays.fill(right,1);
        
        // calculating maximum increasing subsequence for the left of an index.
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]&&left[i]<left[j]+1)
                    left[i]=left[j]+1;
            }
        }
        
        // calculating maximum increasing subsequence for the right of an index.
        for(int i=n-2;i>=0;i--){
            for(int j=n-1;j>i;j--){
                if(nums[j]<nums[i]&&right[i]<right[j]+1)
                    right[i]=right[j]+1;
            }
        }
        
        // calculating the maximum number of elements that can be involved in a mountain array.
        int max=0;
        for(int i=1;i<n-1;i++){
           /*
               If the below conditional statement is not given, then strictly increasing or strictly 
               decreasing sequences will also be considered. It will hence fail in,
               Test case: [10, 9, 8, 7, 6, 5, 4, 5, 4].
                    ---Thanks to @chejianchao for suggesting the test case.
                We need to make sure both the LIS on the left and right, ending at index i, 
                has length > 1. 
           */
            if(right[i]>1&&left[i]>1) // if element nums[i] is a valid peak, 
                max=Math.max(max,left[i]+right[i]-1);
        }
        
        // we need to delete the rest of the elements.
        return n-max;
    }

Similar problem 
-> Longest Mountain in Array (LC-845)
 public int longestMountain(int[] A) {
        int n=A.length;
        if(n<3)return 0;
        
        int left=0;int right;int max=0;
        
        while(left<n-2){
            //skip decending and equal array
            while(left<n-1 && A[left]>=A[left+1]){
                left++;
            }
            right=left+1;
            //mountain up
            while(right<n-1 && A[right]<A[right+1]){
                right++;
            }
            //mountain down
            while(right<n-1 && A[right]>A[right+1]){
                right++;
                //update the max value
                max=Math.max(max,right-left+1);
            }
            left=right;
        }
        return max;
    }
-------------------------------------------------------------------------------------
75. Subarray with k different integers (LC-992)

public int subarraysWithKDistinct(int[] nums, int k) {
        return atmost(nums,k) - atmost(nums,k-1);
    }
    public int atmost(int[]nums,int k){
        HashMap<Integer,Integer>map = new HashMap<>();
        int i=0,j=0;
        
        int result=0;
        while(j<nums.length){
            int val = nums[j];
            map.put(val,map.getOrDefault(val,0)+1);
            j++;
            while(map.size()>k && i<j){
                int temp = map.get(nums[i]);
                if(temp==1){
                    map.remove(nums[i]);
                }else{
                    map.put(nums[i],map.get(nums[i])-1);
                }
                i++;
            }
            result += j-i+1;
        }
        return result;
    }
-------------------------------------------------------------------------------------
76. Substring with atleast k distinct characters
-> 
 static void atleastkDistinctChars(String s, int k){
    
    // Stores the size of the string
    int n = s.length();
  
    // Initialize a HashMap
    Map<Character, Integer> mp = new HashMap<>();
  
    // Stores the start and end
    // indices of sliding window
    int begin = 0, end = 0;
  
    // Stores the required result
    int ans = 0;
  
    // Iterate while the end
    // pointer is less than n
    while (end < n) {
  
        // Include the character at
        // the end of the window
        char c = s.charAt(end);
        mp.put(c,mp.getOrDefault(c,0)+1);
  
        // Increment end pointer by 1
        end++;
  
        // Iterate until count of distinct
        // characters becomes less than K
        while (mp.size() >= k) {
  
            // Remove the character from
            // the beginning of window
            char pre = s.charAt(begin);
            mp.put(pre,mp.getOrDefault(pre,0)-1);
  
            // If its frequency is 0,
            // remove it from the map
            if (mp.get(pre)==0){
                mp.remove(pre);
            }
  
            // Update the answer
            ans += s.length() - end + 1;
            begin++;
        }
    }
  
    // Print the result
    System.out.println(ans);
}
-------------------------------------------------------------------------------------
77. Longest Substring with at least k repeating characters. (LC-395)
-> Sliding window (must read the intuition)

Basically iterate through the number of possible unique letters 1 to 26. Lets call our target amount of unique letters u. We search all windows of letters where the number of unique letters <= u. This is the number of any unique letters, not the number of unique letters that occur k or more times.
We count the number of current unique letters, and the number of letters that have a count of k or more using a sliding window.

We expand, if our number of unique letters is less than or equal to u, we need to add a letter, so we increment the right pointer, and add the count of the right letter by 1. If the count is equal to 1 we know this is a new letter so we increment unique, and if it is equal to k we increment k or more since it just became k or more. Note that the reason we choose this route if it's equal is that we need to keep expanding the letters if its at the target u because we can still have a chance at getting more kOrMore letters and u==unique. For example, aaabb if we stop at "a" since unique == u (1=1) we won't ever get to "aaa" which is the answer.

We shorten, if our number of unique letters is more than u , we need to remove a letter, so we decrement the left pointer, and decrease the count of the left letter by 1. If the count is equal to 0 we decrement the number of unique letters since all instances of this letter are gone, if it's equal to k-1 it is now not k or more so we decrement kOrMore.

This interval is a valid candidate if the number of unique letters is u and all the unique letters have kOrMore counts (unique==kOrMore). So we take the maximum of valid candidates.

Code:
 public int longestSubstring(String s, int k) {
       
       int n = s.length();
       int max = 0;
       int[] cnt = new int[26];
        
        for(int u=1;u<=26;u++){
            
            Arrays.fill(cnt,0);
            int unique = 0;
            int kOrMore = 0;
            int left = 0;
            int right = 0;
            
            while(right<n){
                if(unique<=u){
                    char ch = s.charAt(right);
                    cnt[ch-'a']++;
                    if(cnt[ch-'a']==1)unique++;
                    
                    if(cnt[ch-'a']==k)kOrMore++;
                    right++;
                }else{
                    char ch = s.charAt(left);
                    if(cnt[ch-'a']==1)unique--;
                    
                    if(cnt[ch-'a']==k)kOrMore--;
                    
                    cnt[ch-'a']--;
                    left++;
                }
                if(unique==u && unique==kOrMore){
                    max = Math.max(max,right-left);
                }
            }
        }
        return max;
    }
-------------------------------------------------------------------------------------
78. Longest k unique/distinct character substring
->
 public int longestkSubstr(String s, int k) {
        HashMap < Character, Integer > map = new HashMap < > ();
        int n = s.length();

        int j = 0;
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);

            while (map.size() > k) {
                char start = s.charAt(j);
                map.put(start, map.get(start) - 1);
                if (map.get(start) == 0) {
                    map.remove(start);
                }
                j++;
            }

            if (map.size() == k) {
                maxLength = Math.max(maxLength, i - j + 1);
            }
        }

        return maxLength == 0 ? -1 : maxLength;
    }
-------------------------------------------------------------------------------------
79. Longest Substring with atmost K distinct characters.

public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int len = 0;
        int maxLen = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c,0) + 1);
            len++;

            while (map.size() > k) {
                char sChar = s.charAt(start);
                map.put(sChar, map.get(sChar) - 1);
                if (map.get(sChar) == 0) {
                    map.remove(sChar);
                }
                len--;
                start++;
            }
            maxLen = Math.max(maxLen, len);
        }
        return maxLen;
    }
-------------------------------------------------------------------------------------
80. Smallest String With Swaps (LC-1202)

This problem you will only understand better when you dry run the below testcase
s = "dcabbruqioxp"
pairs = [[0,3],[1,2],[5,8],[6,0],[7,7],[9,10],[2,4]]

ans -> "babdciuqroxp"

-> You will get to know that for the above test case
Different connected components acc to indexes will be

-> after sorting
0,3,6 -> d, b, u => after sorting b,d,u
1,2,4
5,8
7
9,10
11

-> Intuition:
1. So the basic idea is treat indexes as nodes and pairs as edges.
2. Make undirected/bidirectional graph.
3. Find all connected components using dfs/bfs
4. For each connected component you will find just collect all the indexes and characters as well, and later sort them to get smaller
lexicographical string.
5. All the connected components will be independent of each other.(means the changes we do in the char array of that string with these indexes suppose 0,3,6 <- it will not remove any character, only there will happen swaps among them to find the smaller string).
6. Hence each component we can treat as a string and we sort the order
7. In each connected component we find that we can swap any node with any other node this gives us hint that we should find the smaller order among them, hence we can sort them to find the smaller order hence smaller lexico string.

Time: E + VLogV
    
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    
        
        List<Integer>[]graph = new List[s.length()];
        
        for(int i=0;i<graph.length;i++)graph[i] = new ArrayList<>();
        
        for(int i=0;i<pairs.size();i++){
            graph[pairs.get(i).get(0)].add(pairs.get(i).get(1));
            graph[pairs.get(i).get(1)].add(pairs.get(i).get(0));
        }
    
        char[] srr = s.toCharArray();
        
        boolean[]vis = new boolean[s.length()];
        
        for(int i=0;i<srr.length;i++){
            if(!vis[i]){
                List<Integer>ind = new ArrayList<>();
                List<Character>cr = new ArrayList<>();
               
                DFS(graph,srr,i,ind,cr,vis);
                
                Collections.sort(ind);
                Collections.sort(cr);
                
                for(int j=0;j<ind.size();j++){
                    srr[ind.get(j)]=cr.get(j);
                }
            }
        }    
        
        return new String(srr);
    }
    
    public void DFS(List<Integer>[]graph, char[]srr, int start, List<Integer>ind, List<Character>cr, boolean[]vis){
        vis[start]=true;
        
        ind.add(start);
        cr.add(srr[start]);
        
        for(int child:graph[start]){
            if(!vis[child]){
                DFS(graph,srr,child,ind,cr,vis);
            }
        }
    }

---------------------------------------------------------------------------------------------    
81. Evaluate Division (LC-399)

M1) Using DFS


    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        
        Map<String,Map<String,Double>>graph = buildGraph(equations,values);
        
        int n = queries.size();
        double[]res = new double[n];
        
        for(int i=0;i<n;i++){
            res[i] = getAnswer(graph, queries.get(i).get(0), queries.get(i).get(1), new HashSet<>());
        }
        return res;
    }
    
    public Map<String,Map<String,Double>> buildGraph(List<List<String>>equations, double[]values){
        
        Map<String,Map<String,Double>> graph = new HashMap<>();
        
        int n = values.length;
        
        for(int i=0;i<n;i++){
            
            double w_ab = values[i];
            double w_ba = 1.0/values[i];
            
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            
            graph.computeIfAbsent(a,x->new HashMap<>()).put(b,w_ab);
            graph.computeIfAbsent(b,x->new HashMap<>()).put(a,w_ba);
        }
        
        return graph; 
    }
    
    public double getAnswer(Map<String,Map<String,Double>>graph, String src, String des, Set<String>vis){
        
        if(!graph.containsKey(src))return -1.0;
        
        if(graph.get(src).containsKey(des))return graph.get(src).get(des);
        
        vis.add(src);
        
        for(Map.Entry<String,Double> ent : graph.get(src).entrySet()){
            if(!vis.contains(ent.getKey())){
                vis.add(ent.getKey());
                double product = getAnswer(graph,ent.getKey(),des,vis);
                
                if(product!=-1.0){
                    return product * ent.getValue();
                }
            }
        }
        
        return -1.0;
    }

M2) Using Union & Find Method
---------------------------------------------------------------------------------------------    
82. Shortest Unsorted Continous Subarray (LC-581)
-> 
  public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        
        if(n==0 || n==1)return 0;
        
        int beg = -1;
        int end = -2; //taking this value so that in case of sorted array the final answer will return 0;
        
    //iterate from beginning of array, find the last element which is smaller than the last seen max from 
    //its left side and mark it as end
        int max = Integer.MIN_VALUE;
        
        for(int i=0;i<n;i++){
            max = Math.max(max,nums[i]);
            if(max>nums[i]){
                end = i;
            }
        }
        
    //iterate from end of array, find the last element which is bigger than the last seen min from 
    //its right side and mark it as begin

        int min = Integer.MAX_VALUE;
        
        for(int i=n-1;i>=0;i--){
            min = Math.min(min,nums[i]);
            if(nums[i]>min){
                beg = i;
            }
        }
        
        return end-beg+1;
    }

---------------------------------------------------------------------------------------------
83. Missing number (LC-268)
-> in O(N), S(1)  

 public int missingNumber(int[] nums) {
        // solution-1 : n*(n+1)/2 - sum of array <= but it can give overflow in case of n being big number
       
       //solution-2 : xor approach a^b^b = a, so we will try to xor every number in the array and with its index also.
       
       
       int xor=0, i=0;
       
       for(i=0;i<nums.length;i++){
           xor = xor ^ i ^ nums[i];
       }
       return xor ^ i; //here i become the last number as we know that numbers are in range from [0-n]
    }    

---------------------------------------------------------------------------------------------    

---------------------------------------------------------------------------------------------    

---------------------------------------------------------------------------------------------    

---------------------------------------------------------------------------------------------    

---------------------------------------------------------------------------------------------    

---------------------------------------------------------------------------------------------    

---------------------------------------------------------------------------------------------    

---------------------------------------------------------------------------------------------