<file_sep>/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * interface Robot {
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     public bool Move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     public void TurnLeft();
 *     public void TurnRight();
 *
 *     // Clean the current cell.
 *     public void Clean();
 * }
 */

class Solution {
    Robot r;
    HashSet<ValueTuple<int,int>> visited;
    
    public void CleanRoom(Robot robot) {
        r = robot;
        visited = new HashSet<ValueTuple<int,int>>();
      
        BackTrack((0, 0), Direction.Up);
    }
    
    private void BackTrack(ValueTuple<int, int> pos, Direction d){
        visited.Add(pos);
        r.Clean();
        
        for(var i = 0; i < 4; i++){
            var newPos = GetPos(pos, d);
            if(!visited.Contains(newPos) && r.Move()){
                BackTrack(newPos, d);                   
            }
            
            r.TurnRight();
            d = (Direction)(((int)d + 1)%4);
        }
        
        GoBack();            
    }
    
      public void GoBack() {
        r.TurnRight();
        r.TurnRight();
        r.Move();
        r.TurnRight();
        r.TurnRight();
      }
    
    private ValueTuple<int, int> GetPos(ValueTuple<int, int> pos, Direction d){
        (var row, var col) = pos; 
       switch(d){
           case Direction.Up:
               return (row-1, col);
           case Direction.Right:
               return (row, col+1);
           case Direction.Down:
               return (row+1, col);
           case Direction.Left:
               return (row, col-1);
       } 
        
        return pos;
    }
    
    private enum Direction{
        Up,
        Right,
        Down,
        Left
    }
}<file_sep>public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var subsets = new List<IList<int>>();
        subsets.Add(new List<int>());

        // cascading - copy previous subsets 2^N 
        // []
        // []       [1]
        // [] [2]   [1, 2]
        for(int i = 0; i < nums.Length; i++){
            for(int j = subsets.Count-1; j >= 0; j--){
                var set = new List<int>(subsets[j]);
                set.Add(nums[i]);
                subsets.Add(set);
            }
        }

        return subsets;
    }


    // OR backtrack

    public IList<IList<int>> Subsets(int[] nums) {
        var res = new List<IList<int>>();
        for(int setSize = 0; setSize <= nums.Length; setSize++)
            BackTrack(nums, 0, setSize, new List<int>(), res);
        return res;
    }

    void BackTrack(int[] nums, int start, int setSize, List<int> currentSet, IList<IList<int>> res){
        if(currentSet.Count == setSize){
            res.Add(new List<int>(currentSet));
            return;
        }

        for(int i = start; i < nums.Length; i++){
            currentSet.Add(nums[i]);
            BackTrack(nums, i+1, setSize, currentSet, res);
            currentSet.RemoveAt(currentSet.Count-1);
        }
    }
}<file_sep>public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        var n = intervals.Length;
        var res = new List<int[]>();
        var ptr = 0;
        
        while (ptr < n && intervals[ptr][1] < newInterval[0]){
            res.Add(intervals[ptr++]);
        }
        
        var i = new int[]{newInterval[0], newInterval[1]};
        res.Add(i);
        
        while (ptr < n){
            var next = intervals[ptr++];
            if (i[1] >= next[0]){
                i[0] = Math.Min(i[0], next[0]);
                i[1] = Math.Max(i[1], next[1]);
            } else {
                res.Add(next);
            }
        }
        
        return res.ToArray();
    }
}<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if(lists == null || lists.Length == 0)
            return null;
        var n = lists.Length;
        if (n == 1)
            return lists[0];
        
        var step = 1;
        if(n % 2 != 0){
            lists[0] = MergeTwo(lists[0], lists[n-1]);
            n--;
        }
        
        while(step < n){
            for(var i = 0; i < n-step; i += step*2){
                lists[i] = MergeTwo(lists[i], lists[i+step]);
            }
            step *= 2;
        }
        
        return lists[0];
    }
    
    private ListNode MergeTwo(ListNode l1, ListNode l2){
        var dummy = new ListNode();
        var head = dummy;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        
        var l = l1 == null ? l2 : l1;
        if(l != null)
            head.next = l;
        
        return dummy.next;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        if(n==0)
            return new List<TreeNode>();
        
        return GenerateTrees(1, n);
    }
    
    public IList<TreeNode> GenerateTrees(int start, int end) {
        var trees = new List<TreeNode>();
        
        if (start > end){
            trees.Add(null);
            return trees;
        }      
        
        for(int i = start; i <=end; i++){
            var lTrees = GenerateTrees(start, i-1);
            var rTrees = GenerateTrees(i+1, end);
            
            foreach(var l in lTrees)
                foreach(var r in rTrees){
                    trees.Add(new TreeNode(i, l, r));
                }
        }
        
        return trees;
    }
}<file_sep>// morris  traversal
public class Solution {
    public void RecoverTree(TreeNode root) {
        TreeNode prev = null;
        TreeNode firstNode = null;
        TreeNode secondNode = null;

        void check(TreeNode node){
            if(prev != null && node.val < prev.val){
                if(firstNode == null)
                    firstNode = prev;
                
                secondNode = node;
            }

            prev = node;
        }

        var cur = root;

        while(cur != null){
            if(cur.left == null){
                check(cur);
                cur = cur.right;
            } else {
                var pred = cur.left;
                while(pred.right != cur && pred.right != null)
                    pred = pred.right;

                if(pred.right == null){ // not visited
                    pred.right = cur;
                    // visit pre-order
                    cur = cur.left;
                } else { // visited
                    pred.right = null;
                    check(cur); // in-order
                    cur = cur.right;
                }
            }
        }

        var t = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = t;
    }
}

public class Solution {
    public void RecoverTree(TreeNode root) {
        var st = new Stack<TreeNode>();
        
        void traverseLeft(TreeNode node){
            while(node != null){
                st.Push(node);
                node = node.left;
            }
        }

        traverseLeft(root);
        TreeNode prev = null;
        TreeNode firstNode = null;
        TreeNode secondNode = null;

        while(st.Any()){
            var node = st.Pop();

            if(prev != null && node.val < prev.val){
                if(firstNode == null)
                    firstNode = prev;
                
                secondNode = node;
            }

            prev = node;
            traverseLeft(node.right);
        }

        var t = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = t;
    }
}<file_sep>public class Solution {
    public string Multiply(string num1, string num2) {
        var n = num1.Length;
        var m = num2.Length;
        
        
        var res = new int[n+m];
        
        for(var i=n-1; i>=0; i--){
            for(var j = m-1; j>=0; j--){
                var mult = (num1[i]-'0') * (num2[j]-'0');
                var p1 = i+j;
                var p2 = p1+1;
                
                var sum = res[p2] + mult;
                
                res[p2] = sum % 10;
                res[p1] += sum / 10;                
            }
        }
        
        var pos = 0;
        
        while(res[pos] == 0){
            if (pos == res.Length-1)
                return "0";
            
            pos++;
        }
        
        
        
        return new String(res[pos..].Select(c => (char)(c+'0')).ToArray());

    }

}<file_sep>public class Solution {
    public int MinCost(int[][] grid) {
        var rows = grid.Length;
        var cols = grid[0].Length;
        
        if(rows == 0 && cols == 0)
            return 0;
        
        var dirs = new (int,int)[]{(0,1),(0,-1),(1,0),(-1,0)};
        
        var map = new SortedDictionary<int, Queue<(int, int)>>();
        var dist = new int?[rows, cols];
        map.Add(0, new Queue<(int, int)>());
        map[0].Enqueue((0,0));
        dist[0,0] = 0;
        
        while(map.Any()){
            var node = map.First();
            var cost = node.Key;
            var (row, col) = node.Value.Dequeue();
            
            if(!node.Value.Any())
                map.Remove(cost);
            
            for(int i = 0; i < 4; i++){
                var (rd,cd) = dirs[i];
                var r = row+rd;
                var c = col+cd;
                var newCost = cost + (i == grid[row][col]-1 ? 0 : 1);
                
                if(r >= 0 && r < rows && c >= 0 && c < cols && (dist[r,c] == null || dist[r,c] > newCost)){
                    dist[r,c] = newCost;
                    if(!map.ContainsKey(newCost))
                        map.Add(newCost, new Queue<(int, int)>());
                    map[newCost].Enqueue((r,c));
                }
            }
        }

        return dist[rows-1, cols-1].Value;
    }
} <file_sep>public class Solution {
    public int MaxSumTwoNoOverlap(int[] A, int L, int M) {
        var n = A.Length;
        var maxSoFar = new int[n,2];
        
        var res = -1;
        
        
        var sumL = 0;
        var maxL = int.MinValue;
        var sumM = 0;
        var maxM = int.MinValue;
        for(int hi = 0; hi <n; hi++){
                        
            sumL += A[hi];
            sumM += A[hi];
            
            if(hi-L >= -1){
                if (hi-L > -1)
                    sumL -= A[hi-L];
                
                maxL = Math.Max(maxL, sumL);
                maxSoFar[hi,0] = maxL;
                
                if (hi-L > -1)
                    res = Math.Max(res, sumL + maxSoFar[hi-L, 1]);
            }
            
            
            if(hi-M >= -1){
                if (hi-M > -1)
                    sumM -= A[hi-M];
                
                maxM = Math.Max(maxM, sumM);
                maxSoFar[hi,1] = maxM;
                
                if (hi-M > -1)
                    res = Math.Max(res, sumM + maxSoFar[hi-M, 0]);
            }
            
            //Console.WriteLine(maxL + " " + maxM);
        }
        
        return res;
    }
}<file_sep>public class Solution {
    public bool Exist(char[][] board, string word) {
        if(word == null || word == "")
            return false;

        var rows = board.Length;
        var cols = board[0].Length;
        var delta = new []{(0,1),(1,0),(0,-1),(-1,0)};

        for(int r = 0; r < rows; r++){
            for(int c = 0; c < cols; c++){
                if(DFS(r, c, 0, new HashSet<(int, int)>()))
                    return true;
            }
        }

        bool DFS(int row, int col, int pos, HashSet<(int, int)> visited){
            if(pos >= word.Length)
                return true;

            if(row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word[pos] || visited.Contains((row, col)))
                return false;

            visited.Add((row, col));
            var found = false;

            foreach(var (rd, cd) in delta){
                if(found = DFS(row + rd, col + cd, pos+1, visited))
                    break;
            }

            visited.Remove((row, col));

            return found;
        }

        return false;
    }
}<file_sep>public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        var graph = new Dictionary<string, HashSet<string>>();
        var wl = wordList;
        var len = wl[0].Length;
        
        bool isNext(string a, string b){
            var count = 0;
            for(var c = 0; c < len && count < 2; c++){
                if(a[c] != b[c])
                    count++;
            }
            return count==1;
        }

        var hasEnd = false;
        
        for(var i = -1; i< wl.Count; i++){
            var word = i == -1 ? beginWord : wl[i];
            var node = graph[word] = new HashSet<string>();

            hasEnd = hasEnd || word == endWord;
            
            for(var j = 0; j < wl.Count; j++){
                if(isNext(word,wl[j]))
                    node.Add(wl[j]);
            }
        }

        if(!hasEnd || beginWord == endWord)
            return 0;
        
        var min = int.MaxValue;
        var step = 1;
        var q = new Queue<string>();
        var visited = new HashSet<string>{beginWord};
        q.Enqueue(beginWord);
        
        while(q.Count > 0 ){
            for(var i = q.Count; i > 0; i--){
                var w = q.Dequeue();

                if(w == endWord){
                    min = Math.Min(min, step);
                    continue;
                }

                foreach(var child in graph[w]){
                    if(!visited.Contains(child)){
                        q.Enqueue(child);
                        visited.Add(child);
                    }
                }
            }
            step++;
        }
        
        return min == int.MaxValue ? 0 : min;
    }
}<file_sep>public class Solution {
    public int CombinationSum4(int[] nums, int target) {
        var n = nums.Length;

        int dfs(int sum, Dictionary<int, int> memo){
            if(sum > target)
                return 0;
            if(sum == target)
                return 1;

            int res = 0;
            if(memo.TryGetValue(sum, out res))
                return res;

            foreach(var num in nums)
                res += dfs(sum+num, memo);

            memo[sum] = res;
            return res;
        }

        return dfs(0, new Dictionary<int,int>());
    }
}<file_sep>public class Solution {
    public int ClimbStairs(int n) {
        
        //var steps = new int[n];
        var prev1 = 2;
        var prev2 = 1;
        
        
        for(int i = 2; i < n; i++){
            var curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return n > 1 ? prev1 : prev2;
    }
}<file_sep>public class Solution {
    /*
    o,1 2,0 3,4
    0 1 2 3 4
    1 1 1 3 4 
    */

    public int CountComponents(int n, int[][] edges) {
        var dsu = new DSU(n);
        foreach(var edge in edges){
            dsu.Union(edge[0], edge[1]); // 2 0
        }

        /*
        var res = 0;
        for(int i = 0; i < n; i++){
            if(dsu.nodes[i] == i)
                res++;
        }
        */

        return dsu.n;
    }

    public class DSU{
        public int n;
        public int[] nodes;

        public DSU(int n){
            this.n = n;
            nodes = Enumerable.Range(0, n).ToArray();
        }

        public void Union(int a, int b){
            // 2
            // 1
            var pa = Find(a);
            var pb = Find(b);
            if(pa != pb){
                nodes[pa] = pb;
                n--;
            }
        }

        public int Find(int a){
            if(nodes[a] != a)
                nodes[a] = Find(nodes[a]); // 1

            return nodes[a];
        }
    }
}<file_sep>public class Solution {
    public bool IsMonotonic(int[] A) {
        var isIncreasing = 0;
        for(int i = 1; i < A.Length; i++){
            if(isIncreasing == 0){
                isIncreasing = A[i] - A[i-1];
            } else {
                if(isIncreasing * (A[i] - A[i-1]) < 0) 
                    return false;
            }
        }

        return true;
    }
}<file_sep>using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Solution {
class Solution {
    static void Main(string[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        
        /*
        1, 3, b
        2, 3, c
        
        3,null, a - 

        
        5,2, d
        
        1,3
        2,3
        
        count: 3, 1 ,2 5
        
        
        
        count: (2, a), (1,b), (3, a+b)
        
        map: (2, 3), (1, 3), (3, 3)
        
        
        
        {
            paretid, 
            id,
            count
        }
        
        (3,3, ) (3,1) (3,2)*/
    }
    
    public (int,int)[] TopBrands(int k, (int, int?, int)[] brandInfos){
        var dsu = new DSU();
        
        foreach(var info in brandInfos){
            dsu.Union(info);
        }
        
        var counts = new Dictionary<int, int>();
        
        foreach(var kv in dsu.Counts){
            if (kv.Key = dsu.Find(kv.Key))
                counts[kv.Key] = kv.Value;
        }
        
        var minHeap = new Heap<(int, int)>((a, b)=> a.Count - b.Count);
        
        /*foreaach(var kv in Counts){
            if(minHeap.Count >= k && minHeap.Top.Count < kv.Value)
                minHeap.RemoveTop();
                
            if(minHeap.Count < k)
                minHeap.Push(kv)
        }*/
        
        
        return minHeap.ToArray();
    }
}

// Xa, 
// 1,2,3,4,5,6

// 1 
// 2,3,4 


class DSU{
    
    public Dictionary<int, int> map = new Dictionary<int, int>();
    public Dictionary<int, count> counts = new Dictionary<int, int>();
    
    public void Union(int id, int? parentId, int count){
        
        if(parentId == null){
            map[id] = id;
            counts[id] = count;
        } else {
            // todo when parent weas not found
            var p1 = Find(parentId);
            var p2 = Find(id);
            map[p1] = p2;
            count[p1] += count;
        }
    }
    
    public int Find(int id){
        if(!map.ContainsKey(id)){
            map[id] = id;
            counts[id] = 0;
        }
        
        if(map[id] == id)
            return id;
            
        return Find(map[id]);
    }
    
    
    
}

}



<file_sep>public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        var count = tasks.Length;
        var frq = new int[26];

        var max = 0;
        var maxCount = 1;
        for(int i = 0; i < count; i++){
            var idx = tasks[i]-'A';
            frq[idx]++; 

            if(frq[idx] > max){
                max = frq[idx];
                maxCount = 1;
            } else if(frq[idx] == max){
                maxCount++;
            }
        }
        
        var minStepsToScheduleMax = (max-1)*(n+1);

        /*
        n+1 cols
        xxxxxx max-1 rows
        xxxxxx
        xxxxxx
        x appendix number of max frqs
        */
        
        return Math.Max(count, minStepsToScheduleMax+maxCount);
    }
}<file_sep>/*
// Definition for a Node.
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}
*/

public class Solution {
    public Node LowestCommonAncestor(Node p, Node q) {
        var path = new HashSet<Node>();
        while(p != null){
            path.Add(p);
            p = p.parent;
        }

        while(q != null){
            if(path.Contains(p))
                return p;
            
            p = p.parent;
        }

        return null;
    }
}<file_sep>public class Solution {
    public bool CanConvert(string str1, string str2) {
        var n = str1.Length;
        var dsu = new DSU();
        var loops = 0;
       
        for(var i = 0; i < n; i++){
            var a = str1[i];
            var b = str2[i];
            if(a == b)
                continue;
            
             if(dsu.HasAnotherChild(a, b))
                return false;
            
            if(!dsu.Union(a, b))
                loops++;
        }
        
        var jokers = 26 - (new HashSet<char>(str2).Count);
        return jokers >= loops;
    }
    
    class DSU{
        public Dictionary<char, Node> map = new Dictionary<char, Node>();
        
        public bool HasAnotherChild(char a, char b){
            return map.ContainsKey(a) && map[a].Child != null && map[a].Child.Val != b;
        }
        
        public bool Union(char a, char b){
            Node nodeA = FindOrCreate(a);
            Node nodeB = FindOrCreate(b);
            
            if(nodeB.Parent == nodeA)
                return true;

            Node parentA = nodeA;
            Node parentB = nodeB;
            
            while(parentA.Parent != parentA)
                parentA = parentA.Parent;
            
            while(parentB.Parent != parentB)
                parentB = parentB.Parent;
            
            if(parentA == parentB)
                return false;
            
            nodeB.Parent = nodeA;
            nodeA.Child = nodeB;
            
            return true;
        }
        
        private Node FindOrCreate(char c){
            if(map.ContainsKey(c))
                return map[c];
            else{
                var n = new Node(c);
                map[c] = n;
                return n;
            }
        }
    }
    
    class Node{
        public char Val;
        public Node Parent;
        public Node Child;
        
        public Node(char val){
            Val = val;
            Parent = this;
        }
    }
}<file_sep>public class Solution {
    public int MaximalSquare(char[][] matrix) {
        var r = matrix.Length;
        if (r==0)
            return 0;
        var c = matrix[0].Length;


        
        var dp = new int[r+1, c+1];
        
        var maxSquare = 0;
        
        for(int i=1; i<=r; i++){
            for(int j =1; j<=c; j++){
                
                if(matrix[i-1][j-1] == '1'){
                   dp[i,j]=Math.Min(Math.Min(dp[i-1,j],dp[i,j-1]), dp[i-1,j-1])+1;
                
                    if (dp[i,j] > maxSquare)
                        maxSquare = dp[i,j];
                }
                
                
            }
        }
        
        return maxSquare*maxSquare;
    }
}<file_sep>public class Solution {
    public int MaxSubArray(int[] nums) {
        var localSum = 0;
        var maxSum = int.MinValue;
        foreach(var n in nums){
            localSum += n;
            maxSum = Math.Max(localSum, maxSum);
            localSum = Math.Max(0, localSum);
        }
        return maxSum;
    }
}<file_sep>public class LFUCache {
    Dictionary<int, LinkedListNode<CacheNode>> nodeMap;
    Dictionary<int, LinkedList<CacheNode>> countMap;
    int capacity;
    int length;
    int minCount;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        nodeMap = new Dictionary<int, LinkedListNode<CacheNode>>();
        countMap = new Dictionary<int, LinkedList<CacheNode>>();
    }
    
    public int Get(int key) {
        if(nodeMap.TryGetValue(key, out var node)){
            Update(node);
            return node.Value.Val;
        }

        return -1;
    }
    
    public void Put(int key, int value) {
        if(capacity == 0)
            return;

        // override key
        if(nodeMap.TryGetValue(key, out var node)){
            node.Value.Val = value;
            Update(node);
        } else { // new key
            length++;
            
            // invalidate
            if(length > capacity){
                nodeMap.Remove(countMap[minCount].First.Value.Key);
                countMap[minCount].RemoveFirst();
                length--;
            }

            // new cache node
            nodeMap[key] = AddCacheNode(new CacheNode(key, value));
            minCount = 1;
        }
    }

    private void Update(LinkedListNode<CacheNode> node){
        var cacheNode = node.Value;
        
        // moving last node of min count
        if(node.List.Count == 1 && cacheNode.Count == minCount)
            minCount++;
        node.List.Remove(node);

        cacheNode.Count++;
        nodeMap[cacheNode.Key] = AddCacheNode(cacheNode);
    }

    // add node to count map
    private LinkedListNode<CacheNode> AddCacheNode(CacheNode cacheNode){
        if(!countMap.ContainsKey(cacheNode.Count))
            countMap[cacheNode.Count] = new LinkedList<CacheNode>();
        
        countMap[cacheNode.Count].AddLast(cacheNode);
        return countMap[cacheNode.Count].Last;
    }

    class CacheNode{
        public int Key;
        public int Val;
        public int Count;

        public CacheNode(int key, int val){
            Key = key;
            Val = val;
            Count = 1;
        }
    }
}<file_sep>public class Solution {
    public bool CheckSubarraySum(int[] nums, int k) {
        var map = new Dictionary<int, int>{{0, -1}};
        var sum = 0;
        for(int i = 0; i< nums.Length; i++){
            sum += nums[i];

            if(k != 0){
                var mod = (sum % k);

                if(map.ContainsKey(mod)){
                    if(i - map[mod] >= 2)
                        return true;
                }
                else{
                    map.Add(mod, i);
                }
            } else {
                if(i > 0 && nums[i] == 0 && nums[i-1] == nums[i])
                    return true;
            }
        }

        return false;
    }
}<file_sep>public class Solution {
    public int FindMaxForm(string[] strs, int m, int n) {
        var len = strs.Length;
        var memo = new int?[len, m, n];
        var res = int.MinValue;

        int DFS(int pos, int mCurr, int nCurr){
            if(pos >= len)
                return 0;

            if(memo[pos, mCurr, nCurr] != null)
                return memo[pos].Value;

            var str = strs[pos];

            var mt = 0;
            var nt = 0;

            foreach(var c in str){
                if(c == '0')
                    mt++;
                else
                    nt++;
            }

            count = DFS(pos+1, mCurr, nCurr);

            if(mCurr+mt <= m && nCurr+nt <=n){
                count = Math.Max(count, DFS(pos+1, mCurr+mt, nCurr+nt)+1);
            }

            memo[pos, mCurr, nCurr] = count;
            return count;
        }

        DFS(0, 0, 0);
        return memo[0, 0, 0];
    }
}<file_sep>public class Solution {
    public IList<string> RemoveComments(string[] source) {
        var res = new List<string>();
        var inBlock = false;
        StringBuilder sb = null;
        
        foreach(var l in source){
            if(!inBlock)
                sb = new StringBuilder();
            var n = l.Length;
            var starIndex = -1;
            
            for(int i=0; i < n; i++){
                if(!inBlock){
                    if(l[i] == '/' && i < n-1){
                        if(l[i+1]=='/')
                            break;
                        else if(l[i+1]=='*'){
                            inBlock = true;
                            starIndex = i+1;
                        } else {
                            sb.Append(l[i]);
                        }
                    } else {
                        sb.Append(l[i]);
                    }
                } else if(i > 0 && l[i] == '/' && l[i-1] == '*' && i-1 != starIndex) { // /*/ - not valid end of block
                    inBlock = false;
                }
            }
            
            if(!inBlock && sb.Length > 0)
                res.Add(sb.ToString());
        }
        
        return res;
    }
}<file_sep>public class Solution {
    public bool IsSubtree(TreeNode s, TreeNode t) {
        var sTree = Preorder(s);
        var tTree = Preorder(t);

        return sTree.IndexOf(tTree) != -1;
    }

    string Preorder(TreeNode node){
        return node == null 
            ? "n" 
            : string.Concat("#", node.val, Preorder(node.left), Preorder(node.right));
    }
}<file_sep>public class Solution {
    public IList<IList<int>> Generate(int numRows) {
        var res = new List<IList<int>>();
        for(int i = 0; i < numRows; i++){
            var row = new List<int>();
            res.Add(row);

            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    row.Add(1);
                } else{
                    row.Add(res[i-1][j-1]+res[i-1][j]);
                }
            }
        }
        return res;
    }
}<file_sep>public class Solution {
    public int MaxProduct(int[] nums) {
        int max = int.MinValue;
    
        int product=1;

        foreach(int num in nums){
            product *= num;
            max = Math.Max(product,max);
            if(product == 0)product = 1;

        }

        product = 1;
        for(int i=nums.Length-1;i>=0;i--){
            product *= nums[i];
            max = Math.Max(product,max);
            if(product ==0) product = 1;
        }

        return max;
    }
}<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
            return GetSum(l1, l2, 0);
    }
    
    public ListNode GetSum(ListNode l1, ListNode l2, int carry){
        if (l1 == null && l2 == null)
            return carry > 0 ? new ListNode(carry) : null;
        
        var sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
        var res = new ListNode(sum % 10);
        res.next = GetSum(l1?.next, l2?.next, sum / 10);
        
        return res;        
    }
    

}<file_sep>public class Solution {
    public int NumSquares(int n) {
        var dp = Enumerable.Repeat(int.MaxValue, n+1).ToArray();
        dp[0] = 0;
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j*j <= i; j++){
                dp[i] = Math.Min(dp[i], dp[i - j*j] + 1);
            }
        }
        
        return dp[n];
    }
}<file_sep>public class TicTacToe {
    int[] rows;
    int[] cols;
    int d1;
    int d2;
    int n;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
        this.n = n;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int Move(int row, int col, int player) {
        var p = player == 1 ? 1 : -1;
        rows[row] += p;
        cols[col] += p;

        if(row == col)
            d1 += p;
        if(row + col == n-1)
            d2 += p;

        return (Math.Abs(rows[row]) == n || Math.Abs(cols[col]) == n || Math.Abs(d1) == n || Math.Abs(d2) == n) ? player : 0;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.Move(row,col,player);
 */<file_sep>public class Solution {
    public int[][] GenerateMatrix(int n) {
        var val = 1;
        var res = new int[n][];

        for(int i = 0; i < n; i++)
            res[i] = new int[n];

        var top = 0;
        var bottom = n-1;
        var left = 0;
        var right = n-1;
        
        while(val <= n*n){
            for(int c = left; c <= right; c++)
                res[top][c] = val++;
            top++;

            for(int r = top; r <= bottom; r++)
                res[r][right] = val++;
            right--;

            for(int c = right; c >= left; c--)
                res[bottom][c] = val++;
            bottom--;

            for(int r = bottom; r >= top; r--)
                res[r][left] = val++;
            left++;
        }
        
        return res;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int GoodNodes(TreeNode root) {
        var res = 0;
        GoodNodes(root, int.MinValue, ref res);
        return res;
    }

    void GoodNodes(TreeNode node, int max, ref int res){
        if(node == null)
            return;

        if(node.val >= max){
            res++;
            max = node.val;
        }

        GoodNodes(node.left, max, ref res);
        GoodNodes(node.right, max, ref res);
    }
}<file_sep>// 76, 3
public class Solution {
    public IList<int> FindAnagrams(string s, string p) {
        var res = new List<int>();
        if(s.Length == 0 || p.Length > s.Length)
            return res;

        var frq = new Dictionary<char, int>();
        foreach(var c in p)
            frq[c] = frq.ContainsKey(c) ? frq[c] + 1 : 1;

        var count = p.Length;
        var lo = 0;
        var hi = 0;

        while(hi < s.Length){
            var c = s[hi++];

            if(frq.ContainsKey(c)){
                frq[c]--;
                if(frq[c] >= 0)
                    count--; 
            }
            
            if(count == 0)
                res.Add(lo);

            if(hi-lo == p.Length){
                c = s[lo++];
                if(frq.ContainsKey(c)){
                    frq[c]++;
                    if(frq[c] > 0)
                        count++;
                }
            }
        }
        
        return res;
    }

}<file_sep>public class MinStack {

    

    private Stack<int> dataStack;

    private Stack<int> minStack;



    /** initialize your data structure here. */

    public MinStack() {

        dataStack = new Stack<int>();

        minStack = new Stack<int>();

    }

    

    public void Push(int x) {

        dataStack.Push(x);

        if (x <= getMin())

            minStack.Push(x);

    }

    

    public void Pop() {

        var x = dataStack.Pop();

        if (x == getMin())

            minStack.Pop();

    }

    

    public int Top() {

        return dataStack.Peek();

    }

    

    public int GetMin() {

        return minStack.Peek();

    }

    

    private int getMin()

    {

        return minStack.Count == 0 ? int.MaxValue : minStack.Peek();

    }

}

<file_sep>public class Solution {
    public int FindKthPositive(int[] arr, int k) {
        var lo = 0;
        var hi = arr.Length-1;
        while(lo <= hi){
            var mid = lo+(hi-lo)/2;
            if(arr[mid]-(mid+1) >= k)
                hi = mid-1;
            else
                lo = mid+1;
        }
        return lo + k;
    }
}<file_sep>public class Solution {

    // 1994
    // MCMXCIV
    public string IntToRoman(int num) { // 
        var values = new []{1000,900,500,400,100,90,50,40,10,9,5,4,1};
        var romans = new []{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        var sb = new StringBuilder(); 

        for(int i = 0; i < values.Length; i++){
            while(num >= values[i]){
                sb.Append(romans[i]);
                num -= values[i];
            }
        }

        return sb.ToString();
    }    
    
    public string IntToRoman(int num) { // 
        var sb = new StringBuilder(); // MCMXC
        var romans = new []{'M','D','C','L','X','V','I'};
        
        var limit = 10000; // 100
        var idx = -2; // 2 c
        while(limit > 1){
            var divisor = limit/10; // 10

            if(num >= limit-divisor){ // 90
                sb.Append(romans[idx+2]);
                sb.Append(romans[idx]);
                num -= limit-divisor; // 4
            }

            if(num >= limit/2){  // 500
                sb.Append(romans[idx+1]);
                num -= limit/2;
            }

            if(num >= limit/2 - divisor){
                sb.Append(romans[idx+2]);
                sb.Append(romans[idx+1]);
                num -= limit/2 - divisor;
            }

            if(num >= divisor){
                var count = num / divisor;
                for(int i = 0; i < count; i++)
                    sb.Append(romans[idx+2]);
                num -= divisor*count;
            }

            limit = divisor;
            idx += 2;
            
        }

        return sb.ToString();
    }
}<file_sep>public class Solution {
    public int ConnectSticks(int[] sticks) {
        var heap = new SortedDictionary<int,int>();
        var count = 0;

        foreach(var stick in sticks){
            add(stick);
        }

        void add(int v){
            count++;
            if(heap.ContainsKey(v))
                heap[v]++;
            else
                heap[v] = 1;
        }

        int remove(){
            count--;
            var v = heap.First().Key;
            heap[v]--;
            if(heap[v] == 0)
                heap.Remove(v);
            return v;
        }

        var res = 0;
        while(count > 1){
            var a = remove();
            var b = remove();
            add(a+b);

            res += a+b;
        }

        return res;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxPathSum(TreeNode root) {
        
        var maxSum = int.MinValue;
        MaxPathSum(root, ref maxSum);
        
        return maxSum;
    }
    
    public int MaxPathSum(TreeNode root, ref int maxSum) {
        if (root == null)
            return 0;
        
        var maxL = Math.Max(MaxPathSum(root.left, ref maxSum), 0);
        var maxR = Math.Max(MaxPathSum(root.right, ref maxSum), 0);
        
        maxSum = Math.Max(maxSum, maxL+maxR+root.val);
        
        return Math.Max(maxL, maxR)+root.val;
    }
}<file_sep>public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        
        var leftIdx = Search(nums, target, 0, nums.Length, true);
        
        if(leftIdx >= nums.Length || nums[leftIdx] != target)
            return new[] {-1,-1};
        

        return new[] {leftIdx, Search(nums, target, leftIdx, nums.Length, false)-1};
    }
        
    private int Search(int[] nums, int target, int lo, int hi, bool left){
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] > target || (left && target == nums[mid])) {
                hi = mid;
            }
            else {
                lo = mid+1;
            }
        }

        return hi;
    }
}<file_sep>public class Solution {
    public int LengthOfLongestSubstringTwoDistinct(string s) {
        if(s == null || s.Length <= 2)
            return s?.Length ?? 0;
        
        var lo = 0;
        var hi = 0;
        var max = 0;
        
        var map = new Dictionary<char, int>();
        
        while(hi < s.Length){
            var c = s[hi++];
            
            if(map.Count < 2 || map.ContainsKey(c)){
                if(hi-lo > max)
                    max = hi - lo;              
            } else{
                var prevVal = Math.Min(map.First().Value, map.Last().Value);
                lo = prevVal;
                map.Remove(s[prevVal-1]);                
            }
            
            map[c] = hi;

        }
        
        return max;
    }
}<file_sep>public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        var rows = matrix.Length;
        if(rows == 0)
            return false;
        var cols = matrix[0].Length;
        var n = rows * cols;

        var lo = 0;
        var hi = n-1;
        while(lo <= hi){
            var mid = lo + (hi-lo)/2;
            var val = matrix[mid/cols][mid%cols];
            if(target == val)
                return true;
            
            if(val > target)
                hi = mid-1;
            else
                lo = mid+1;
        }

        return false;
    }
}<file_sep>public class Solution {
    public string BreakPalindrome(string palindrome) {
        if(palindrome == null || palindrome.Length <=1)
            return "";

        var sb = palindrome.ToCharArray();

        for(int i = 0; i < sb.Length/2; i++){
            if(sb[i] != 'a'){
                sb[i] = 'a';
                return new string(sb);
            }
        }

        sb[sb.Length-1] = 'b';
        return new string(sb);
    }
}<file_sep>public class Solution {
    public string MinRemoveToMakeValid(string s) {
        var n = s.Length;
        var st = new Stack<int>();
        var sb = new StringBuilder(s);

        for(int i = 0; i < n; i++){
            var c = sb[i];
            if(c == '('){
                st.Push(i);
            } else if(c == ')'){
                if(!st.Any())
                    sb[i] = '*';
                else
                    st.Pop();
            }
        }

        while(st.Any()){
            sb[st.Pop()] = '*';
        }

        sb.Replace("*", "");
        return sb.ToString();
    }
}<file_sep>public class Solution {
    public int CountSubstrings(string s) {
			var palindroms = 0;
			var fraim = 0;

			while (fraim <= s.Length)
			{
				for (int i = fraim; i < s.Length; i++)
				{
					var end = i;
					var start = i - fraim;

					while (start <= end && s[start] == s[end])
					{
						start++;
						end--;
					}

					if (start >= end)
						palindroms++;
				}

				fraim++;
			}

			return palindroms;
		}
}<file_sep>public class Solution {
    public string StringShift(string s, int[][] shift) {
        var leftShifts = 0;
        var rightShifts = 0;
        
        foreach(var sh in shift){
            if(sh[0] == 0)
                leftShifts+=sh[1];
            else
                rightShifts+=sh[1];
            
        }
        
        if(rightShifts == leftShifts){
            return s;
        }
        
        var chars = string.Concat(s,s).ToCharArray();
        var totalShifts = 0;
        
        if(rightShifts > leftShifts){
            totalShifts = (rightShifts - leftShifts)%s.Length;            
            return new String(chars, chars.Length/2-totalShifts, s.Length);
        }
        
        totalShifts = (leftShifts - rightShifts)%s.Length;
        return new String(chars, totalShifts, s.Length);
        
    }
}<file_sep>public class Solution {
    public int Calculate(string s) {
        var n = s.Length;
        var nums = new Stack<int>();
        var ops = new Stack<char>();

        var precedence = new Dictionary<char, int>{
            {'+', 0},
            {'-', 0},
            {'*', 1},
            {'/', 1},
            {'(', -1}
        };

        void calc(){
            switch(ops.Pop()){
                case '*': nums.Push(nums.Pop()*nums.Pop()); break;
                case '/': nums.Push((int)(1.0/nums.Pop()*nums.Pop())); break;
                case '+': nums.Push(nums.Pop()+nums.Pop()); break;
                case '-': nums.Push(-1*nums.Pop()+nums.Pop()); break;
            }
        }
        
        for(int i = 0; i < n; i++){
            var c = s[i];
            if(c >= '0' && c <= '9'){
                var num = c - '0';
                while(i+1 < n && s[i+1] >= '0' && s[i+1] <= '9'){
                    num *= 10;
                    num += s[i+1] - '0';
                    i++;
                }
                //Console.WriteLine(num);
                nums.Push(num);
            } else if(c == '('){
                ops.Push(c);
            } else if(c == ')'){
                while(ops.Peek() != '(')
                    calc();
                ops.Pop();
            } else if (c != ' '){
                while(ops.Any() && precedence[ops.Peek()] >= precedence[c])
                    calc();
                ops.Push(c);
            }
        }

        while(ops.Any())
            calc();

        return nums.Pop();
    }
}<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode PlusOne(ListNode head) {
        
        var dummy = new ListNode(0, head);
        var nonNine = dummy;
        
        while(head != null){
            if(head.val < 9)
                nonNine = head;
            
            head = head.next;
        }
        
        nonNine.val++;
        
        while(nonNine.next != null){
            nonNine.next.val = 0;
            nonNine = nonNine.next;
        }
        
        return dummy.val > 0 ? dummy : dummy.next;
        
        //var carry = PlusOneInternal(head);       
        //return carry > 0 ? new ListNode(carry, head) : head;
    }
    
    public int PlusOneInternal(ListNode node) {
       
        var carry = node.next == null ? 1 : PlusOneInternal(node.next);
        
        var d = node.val + carry;
        node.val = d % 10;
        return d / 10;
    }
}<file_sep>public class Solution {
    public bool IsRobotBounded(string instructions) {
        var x = 0;
        var y = 0;
        var d = 0;
        var dirs = new []{(0, 1),(1,0),(0,-1),(-1,0)};

        foreach(var c in instructions){
            switch(c){
                case 'R':
                    d = (d+1) % 4; 
                break;
                case 'L':
                    d = (d+3) % 4;
                break;
                case 'G':
                    var (xd, yd) = dirs[d];
                    x += xd;
                    y += yd;
                break;
            }
        }

        return (x == 0 && y == 0) || d != 0;
    }
}<file_sep>public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        int calcLen(ListNode l){
            var len = 0;
            while(l != null){
                len++;
                l = l.next;
            }

            return len;
        }

        var len1 = calcLen(l1);
        var len2 = calcLen(l2);
        var res = new ListNode();

        int add(ListNode head, int dif, ListNode l1, ListNode l2){
            if(l1 == null)
                return 0;

            var sum = l1.val;
            head.next = new ListNode();

            if(dif <= 0){
                sum += l2.val;
                l2 = l2.next;
            }

            sum += add(head.next, --dif, l1.next, l2);
            head.next.val = sum%10;
            return sum/10;
        }
        
        var dif = Math.Abs(len1-len2);
        res.val = len1 > len2 ? add(res, dif, l1, l2) : add(res, dif, l2,l1);
        return res.val == 0 ? res.next : res; 
    }
}<file_sep>	public class Solution
	{
		public int MinPathSum(int[][] grid)
		{
			if (grid.Length == 0)
				return 0;

			var h = grid.Length;
			var w = grid[0].Length;

            var dp = new int[h][];

            for(var i = 0; i < h; i++)
            {
                dp[i] = new int[w];
                for(var j = 0; j < w; j++)
                {
                    dp[i][j] = grid[i][j];
                    if (i>0 && j>0){
                        dp[i][j] += Math.Min(dp[i-1][j],dp[i][j-1]);
                    } else if(i > 0){
                        dp[i][j] += dp[i-1][j];
                    } else if(j > 0){
                        dp[i][j] += dp[i][j-1];
                    }

                }
            }
                return dp[h-1][w-1];
            }
            
        }

<file_sep>public class TopVotedCandidate {
    int[] winners;
    int[] times;
    int N;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        N = times.Length;
        winners = new int[N];
        var scores = new Dictionary<int, int>();
        var leader = -1;
        
        for(var i = 0; i < N; i++){
            var candidate = persons[i];
            if(scores.ContainsKey(candidate))
                scores[candidate] += 1;
            else
                scores[candidate] = 1;
            
            if(leader == -1 || scores[candidate] >= scores[leader]){
                leader = candidate;
            }
            
            winners[i] = leader;
        }
    }
    
    public int Q(int t) {
        var lo = 0;
        var hi = N-1;
        while(lo < hi){
            var mid = lo + (hi-lo)/2;
            if(times[mid] > t)
                hi = mid;
            else
                lo = mid+1;
        }
        
        return times[hi] > t ? winners[hi-1] : winners[hi];
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.Q(t);
 */<file_sep>public class Solution {
    public int SubarraySum(int[] nums, int k) {
        var runingSum = new Dictionary<int,int>();

        var sum = 0;
        var result = 0;
        
        for(var i = 0; i < nums.Length; i++){
            sum += nums[i];            
            if (sum == k)
                result++;
            
            if (runingSum.TryGetValue(sum-k, out var count)){
                result += count;
            }  
            
            if (runingSum.ContainsKey(sum)){
                runingSum[sum]++;
            } else{
                runingSum[sum] = 1;
            }         
        }
 

        return result;
    }
}<file_sep>public class Solution {
    public int FindMaxConsecutiveOnes(int[] nums) {
        var n = nums.Length;
        var len = 0;
        var flipped = 0;
        var res = 0;
        for(int i=0; i<n; i++){
            flipped = nums[i] == 1 ? flipped+1 : len+1;
            len = nums[i] == 1 ? len+1 : 0;
            res = Math.Max(res, flipped);
        }
        return res;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        var res = new List<int>();

        if(root == null)
            return res;

        var q = new Queue<TreeNode>();
        q.Enqueue(root);

        while(q.Any()){
            var n = q.Count;
            for(int i = 0; i < n; i++){
                var node = q.Dequeue();
                
                if(node.right != null)
                    q.Enqueue(node.right);
                else if(node.left != null)
                    q.Enqueue(node.left);
                
                if(i == n-1)
                    res.Add(node.val);
            }
        }

        return res;
    }
}<file_sep>/*
// Definition for a Node.
public class Node {
    public int val;
    public IList<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new List<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new List<Node>();
    }

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

public class Solution {
    public Node CloneGraph(Node node) {
        if(node == null)
            return null;

        var visited = new Dictionary<Node, Node>();
        var q = new Queue<Node>();

        void Clone(Node n){
            if(n == null || visited.ContainsKey(n))
                return;

            q.Enqueue(n);
            var clone = new Node(n.val);
            visited[n] = clone;
        }

        Clone(node);

        while(q.Any()){
            var n = q.Dequeue();
            var clone = visited[n];
            foreach(var nei in n.neighbors){
                Clone(nei);
                clone.neighbors.Add(visited[nei]);
            }
        }

        return visited[node];
    }
}<file_sep>public class Solution {
    public int LongestStrChain(string[] words) {
        var a = new Dictionary<string, int>();
        var len = new HashSet<int>();
        var max = 1;
        
        foreach(var w in words.OrderBy(wd => wd.Length)){
            if(a.ContainsKey(w))
                continue;
            
            var n = w.Length;
            len.Add(n);
            
            if(n==1 || !len.Contains(n-1)){
                a[w] = 1;
                continue;
            }

            var sb = new StringBuilder(w);
            for(int i = 0; i < n; i++){
                var t = sb[i];
                sb.Remove(i,1);
                var p = sb.ToString();
                sb.Insert(i, t);

                if(a.ContainsKey(p)){
                    a[w] = a[p] + 1;
                    max = Math.Max(max, a[w]);
                    break;
                }
            }
            
            if(!a.ContainsKey(w))
                a[w] = 1;

        }
        
        return max;
    }
}<file_sep>public class Solution {
    int[] nums;
    Random r = new Random();

    public Solution(int[] nums) {
        this.nums =  nums;
    }
    
    public int Pick(int target) {
        var idx = 0;
        var count = 0;
        for(int i = 0; i < nums.Length; i++){
            if(nums[i] == target){
                if(r.Next(0, ++count))
                    idx = i;
            }
        }
        return idx;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.Pick(target);
 */


/*
public class Solution {
    Dictionary<int, List<int>> map = new Dictionary<int, List<int>>();
    Random r = new Random();

    public Solution(int[] nums) {
        for(int i = 0; i < nums.Length; i++){
            if(!map.ContainsKey(nums[i]))
                map[nums[i]] = new List<int>();

            map[nums[i]].Add(i);
        }
    }
    
    public int Pick(int target) {
        var list = map[target];
        var idx = r.Next(0, list.Count);
        return list[idx];
    }
}
*/
<file_sep>public class Solution {
    public bool CanTransform(string start, string end) {
        var n = start.Length;
        if (n != end.Length)
            return false;
        
        if(start.Count(c => c == 'R') != end.Count(c => c == 'R'))
            return false;
        if(start.Count(c => c == 'L') != end.Count(c => c == 'L'))
            return false;
        
        var s = 0;
        var e = 0;
        
        while(s < n){
            while(s < n && start[s] == 'X')
                s++;
            while(e < n && end[e] == 'X')
                e++;
            
            if(s == n || e == n)
                return e == s;
            
            if(start[s] != end[e] )
                return false;
            
            s++;
            e++;
        }
        
        return true;
    }
}<file_sep>public class Solution {
    public IList<string> FindMissingRanges(int[] nums, int lower, int upper) {       

        var res = new List<string>();
        var ptr = 0;
        
        if(nums.Length == 0){
            res.Add(CreateRange(lower, upper));
            return res;
        }
        
        while(lower <= upper && ptr < nums.Length){
            
            if(lower == nums[ptr]){
                lower++;
                ptr++;
            } else {
                res.Add(CreateRange(lower, nums[ptr]-1));
                lower = nums[ptr]; 
            }     
           
        }
        
        if (lower <= upper && ptr == nums.Length){
            res.Add(CreateRange(nums[nums.Length-1]+1, upper));
        }
        
        return res;
    }
    
    private string CreateRange(int lo, int hi){
        return hi == lo ? hi.ToString() : $"{lo}->{hi}";
    }
}<file_sep>public class Solution {
    public string ModifyString(string s) {
        var sb = s.ToCharArray();
        var a = (int)'a';
        
        for(int i = 0; i < sb.Length; i++){
            if(sb[i] == '?'){
                var c = a;
                while(i > 0 && c == sb[i-1] || i < sb.Length-1 && c == sb[i+1])
                    c++;
                
                sb[i] = (char)c;
            }
        }

        return new string(sb);
    }
}<file_sep>public class WordDictionary {
    Node trie = new Node();
    HashSet<string> set = new HashSet<string>();

    public WordDictionary() {
    }
    
    public void AddWord(string word) {
        var node = trie;
        foreach(var c in word){
            var idx = c - 'a';
            if(node.Children[idx] == null)
                node.Children[idx] = new Node();
            node = node.Children[idx];
        }
        node.IsWord = true;
        set.Add(word);
    }
    
    public bool Search(string word) {
        return set.Contains(word) || TryFind(trie, word, 0);
    }

    public bool TryFind(Node node, string w, int idx){
        if(node == null)
            return false;
        
        if(idx == w.Length)
            return node.IsWord;

        if(w[idx] != '.')
            return TryFind(node.Children[w[idx]-'a'], w, idx+1);

        foreach(var child in node.Children.Where(c => c != null)){
            if(TryFind(child, w, idx + 1))
                return true;
        }

        return false;
    }
}

public class Node{
    public Node[] Children = new Node[26];
    public bool IsWord;
}
<file_sep>public class Solution {
    public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
        /*var res = DFS(nums, k, 0, 3, new int[nums.Length, 4][]);
        return res.Skip(1).ToArray();*/

        var sums = new int[nums.Length - k + 1];
        var sum = 0;
        for(int i = 0; i < nums.Length; i++){
            sum += nums[i];
            if(i - k >= 0)
                sum -= nums[i-k];

            // have K in window. start counting
            if(i - k + 1 >= 0)
                sums[i - k + 1] = sum;
        }

        var n = sums.Length;
        var bestSoFar = new int[n,2];

        var best = 0;
        for(int i = 0; i < n; i++){
            if(sums[i] > sums[best])
                best = i;
            bestSoFar[i,0] = best;
        }

        best = n-1;
        for(int i = n-1; i >= 0; i--){
            if(sums[i] >= sums[best])
                best = i;
            bestSoFar[i,1] = best;
        }

        var res = new int[3];
        sum = 0;
        for(int i = k; i < n - k; i++){
            var l = bestSoFar[i-k, 0];
            var r = bestSoFar[i+k, 1];
            var curSum = sums[l] + sums[i] + sums[r];
            if(curSum > sum){
                sum = curSum;
                res[0] = l;
                res[1] = i;
                res[2] = r;
            }
        }

        return res;
    }

    /*public int[] DFS(int[] nums, int k, int start, int left, int[,][] memo){
        if(memo[start, left] != null)
            return memo[start, left];

        var localSum = 0;
        var maxLocalSum = int.MinValue;
        var maxSum = int.MinValue;
        var res = new int[4];
        for(int i = start; i < nums.Length-(k*(left-1)); i++){
            localSum += nums[i];
            if(i - k >= start)
                localSum -= nums[i-k];
            
            // have K in window. start counting
            if(i-(k-1) >= start){
                maxLocalSum = Math.Max(maxLocalSum, localSum);
                var sum = maxLocalSum;
                if(left > 1){
                    var dfs = DFS(nums, k, i+1, left-1, memo);
                    sum += dfs[0];
                    if(sum > maxSum) 
                        res = dfs;
                }

                if(sum > maxSum) {
                    maxSum = sum;
                    res[0] = maxSum;
                    res[4-left] = i-(k-1);
                }
            }
        }

        memo[start, left] = res;
        return res;
    }*/
}<file_sep>public class Solution {
    public bool IsIsomorphic(string s, string t) {
        var map = new Dictionary<char,char>();
        var taken = new Dictionary<char,char>();
        var n = s.Length;
        
        for(int i = 0; i < n; i++){
            var from = s[i];
            var to = t[i];
            
            if(map.ContainsKey(from) && to != map[from])
                return false;
            if(taken.ContainsKey(to) && from != taken[to])
                return false;
            
            map[from] = to;
            taken[to] = from;
        }
        
        return true;
    }
}<file_sep>public class Solution {
    public int ConfusingNumberII(int N) {
        var map = new long[]{0,1,6,8,9};
        
        var count = 0;
        
        void Calc(long curr){
            if(curr > 0){
                var rotated = 0L;
                var orig = curr;
                while(orig > 0){
                    var last = orig%10;
                    orig /= 10;
                    
                    rotated *= 10;
                    rotated += last == 9 ? 6 : last == 6 ? 9 : last;
                }
                
                if(rotated != curr)
                    count++;
            }
            
            foreach(var kv in map){
                var num = curr*10+kv;
                if(num <= N && num > 0)
                    Calc(num);
            }
        }
        
        Calc(0);
        return count;
    }
}<file_sep>public class Solution {
    public int MaximumSwap(int num) {
        var nums = num.ToString().ToCharArray();
        var lastPos = new int[10];

        for(int i = 0; i < nums.Length; i++)
            lastPos[nums[i]-'0'] = i;

        for(int i = 0; i < nums.Length; i++){
            for(var n = 9; n > nums[i]-'0'; n--){
                if(lastPos[n] > i){
                    var t = nums[i];
                    nums[i] = nums[lastPos[n]];
                    nums[lastPos[n]] = t;

                    return int.Parse(new string(nums));
                }
            }
        }

        return num;
    }
}<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        
        if (head == null || head.next == null)
            return null;
            
        ListNode start = new ListNode(0);
        start.next = head;
        var ahead = start;
        var behind = start;       
        
        
        while(n-- >= 0)
        {
            ahead = ahead.next;
        }
        
        while(ahead != null){
            ahead = ahead.next;
            behind = behind.next;
        }
        
        
        behind.next = behind.next.next;
        
        return start.next;
    }
}<file_sep>public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        if(nums1.Length > nums2.Length)
            return Intersection(nums2, nums1);
        
        var set = new HashSet<int>(nums2);
        var res = new HashSet<int>();
        foreach(var n in nums1)
            if(set.Contains(n))
                res.Add(n);

        return res.ToArray();
    }
}<file_sep>/*
// Definition for a Node.
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
*/

public class Solution {
    public Node Connect(Node root) {
        void link(Node next, ref Node cur, ref Node first){
            if(first == null)
                first = cur ?? next;
            
            if(cur == null){
                cur = next;
            }else if(next != null){
                cur.next = next;
                cur = next;
            }            
        }

        var left = root;

        while(left != null){
            var head = left;
            var cur = head.left;
            left = null;

            while(head != null){
                link(head.right, ref cur, ref left);

                if(head.next != null)
                    link(head.next.left, ref cur, ref left);

                head = head.next;
            }
        }

        return root;
    }
}<file_sep>public class Solution {
    public IList<int> PartitionLabels(string s) {
        var n = s.Length;
        var lastIdx = new int[26];
        for(int i = 0; i < n ; i++){
            lastIdx[s[i] - 'a'] = i;
        }
        var res = new List<int>();

        var start = -1;
        var end = 0;
        for(int i = 0; i < n; i++){
            end = Math.Max(end, lastIdx[s[i]-'a']);
            if(i == end){
                res.Add(end-start);
                start = end;
            }
        }

        return res;
    }
}<file_sep>public class Solution {
    public string NumberToWords(int num) {
        if(num == 0)
            return "Zero";

        var ones = new string[] {"One","Two","Three","Four","Five","Six","Seven","Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        var tens = new string[] {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

        IEnumerable<string> ReadTens(){
            var n1 = num % 10;
            var n2 = num % 100;

            if(n2 == 0)
                yield break;
            else if(n2 < 20)
                yield return ones[n2-1];
            else{
                if(n1 != 0)
                    yield return ones[n1-1];
                yield return tens[n2/10-2];
            }
        }

        var exp = new string[] {"Thousand", "Million", "Billion"};
        var count = 0;

        var res = new Stack<string>();

        while(num > 0){
            if(num % 1000 == 0){
                count++;
                num /= 1000;
                continue;
            }

            if(count > 0)
                res.Push(exp[count-1]);
            count++;

            foreach(var str in ReadTens())
                res.Push(str);
            
            num /= 100;

            var n = num % 10;
            if(n > 0){
                res.Push("Hundred");
                res.Push(ones[n-1]);
            }

            num /= 10;
        }

        return string.Join(" ", res);
    }
}<file_sep>public class Solution {
    public int MaxProfit(int[] prices) {
          int total = 0;
    for (int i=0; i< prices.Length-1; i++) {
        if (prices[i+1]>prices[i]) total += prices[i+1]-prices[i];
    }
    
    return total;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<TreeNode> DelNodes(TreeNode root, int[] to_delete) {
        var res = new List<TreeNode>();
        var d = new HashSet<int>(to_delete);
        
        DeleteNodes(root, res, d, null, false);
        
        if(!d.Contains(root.val))
            res.Add(root);
        
        return res;
    }
    
    private void DeleteNodes(TreeNode n, List<TreeNode> res, HashSet<int> d, TreeNode parent, bool left){
        if(n == null)
            return;
        
        if(d.Contains(n.val)){
            if(parent != null){
                if(left)
                    parent.left = null;
                else
                    parent.right = null;
            }
            
            if(n.left != null && !d.Contains(n.left.val))
                res.Add(n.left);
            
            if(n.right != null && !d.Contains(n.right.val))
                res.Add(n.right);
        }
        
        DeleteNodes(n.left, res, d, n, true);
        DeleteNodes(n.right, res, d, n, false);
    }
}<file_sep>public class Solution {
    public int RangeSumBST(TreeNode root, int low, int high) {
        if(root == null)
            return 0;

        if(root.val < low)
            return RangeSumBST(root.right, low, high);
        if(root.val > high)
            return RangeSumBST(root.left, low, high);

        return root.val + RangeSumBST(root.right, low, high) + RangeSumBST(root.left, low, high);
    }
}<file_sep>public class Solution {
    public string AddStrings(string num1, string num2) {
        var l1 = num1.Length;
        var l2 = num2.Length;

        if(l1 < l2)
            return AddStrings(num2, num1);

        var res = new Stack<char>();
        var remainder = 0;
        for(int i = l1-1; i >= 0; i--){
            var n1 = num1[i]-'0';

            var idx = i + l2 - l1;
            var n2 = idx >= 0 ? num2[idx]-'0' : 0;

            var sum = n1+n2+remainder;
            remainder = sum/10;
            sum %= 10;
            
            res.Push((char)(sum + '0'));
        }
        
        if(remainder > 0)
            res.Push((char)(remainder+'0'));
        return new String(res.ToArray());
    }
}<file_sep>public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        var res = 0;
        var rows = triangle.Count;

        for(int r = rows-2; r >= 0; r--){
            for(int c = 0; c < triangle[r].Count; c++){
                triangle[r][c] += Math.Min(triangle[r+1][c], triangle[r+1][c+1]);
            }
        } 

        return triangle[0][0];
    }
}<file_sep>public class Solution {
    public string MinWindow(string S, string T) {
        if(S == T)
            return S;
        
        // optimization
        if(T.Length == 1){
            for (int i = 0; i < S.Length; i++)
		    {
                if(S[i] == T[0])
                    return T;
            }
            
            return "";
        }
        
        int c = 0;

		int start = -1;
		int len = -1;

		for (int i = 0; i < S.Length; i++)
		{
		    // go from left to right , to find the end index
			if (S[i] == T[c])
			{
				c++;
			}

            // found a match
			if (c == T.Length)
			{
			     //go from right to left , to find the  start index
				int d = i;
				while(c > 0)
				{
					if (T[c - 1] == S[d])
					{
						c--;
					}

					d--;
				}

				if (len == -1 || i - d < len)
				{
					len = i - d;
					start = d + 1;
				}
                
				//reset the new search index to the old start position
                i = d + 1;
			}
		}

		if (len == -1) return "";
		return S.Substring(start , len);
    }
}<file_sep>public class Solution {
    public bool ValidMountainArray(int[] arr) {
        var n = arr.Length;
        if(n<3)
            return false;

        var down = false;
        for(var i=0; i < n-1; i++){
            var cur = arr[i];
            var next = arr[i+1];
            if(next > cur){
                if(down)
                    return false;
            } else if(next < cur){
                if(!down){
                    if(i==0)
                        return false;
                    down = true;
                }
            } else{
                return false;
            }
        }

        return down;
    }
}<file_sep>public class Solution {
    public int[] FindRedundantConnection(int[][] edges) {
        int[] res = null;
        var dsu = new DSU(edges.Length);

        foreach(var edge in edges){
            if(dsu.Union(edge[0], edge[1]))
                res = edge;
        }

        return res;
    }

    class DSU{
        int[] arr;

        public DSU(int n){
            arr = Enumerable<int>.Range(0, n).ToArray();
        }

        public bool Union(int a, int b){
            var parenta = Find(a);
            var parentb = Find(b);

            arr[parenta] = parentb;

            return parenta == parentb;
        }

        public int Find(int a){
            if(arr[a] != a)
                arr[a] = Find(arr[a]); // path compression

            return arr[a];
        }
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return Convert(nums, 0, nums.Length-1);
    }

    public TreeNode Convert(int[] nums, int start, int end){// 0 1 // 3 4 
        if(end < start)
            return null;
        if(start == end) // f
            return new TreeNode(nums[start]);

        var mid = start + (end-start)/2; // 3
        var node = new TreeNode(nums[mid]); // 5
        node.Left = Convert(nums, start, mid-1); // 3 2
        node.Right = Convert(nums, mid+1, end); // 4 4
        return node; // 0
    }
}<file_sep>public class Solution {
    public bool IsMatch(string s, string p) {
        //return DFS(s, p, 0, 0, new int?[s.Length+1, p.Length+1]);

        var dp = new int[s.Length+1, p.Length+1];
        dp[s.Length,p.Length] = true;

        for (int posS = s.Length; posS >= 0; posS--){
            for (int posP = p.Length - 1; posP >= 0; posP--){
                var symbolMatch = posS < s.Length && (s[posS] == p[posP] || p[posP] == '.');
                var isAsterisk = posP < p.Length-1 && p[posP+1] == '*';

                var res = false;
                if(isAsterisk){
                    // skip * and move on OR continue with current *
                    dp[posS, posP] = dp[posS, posP+2] || symbolMatch && dp[posS+1, posP];
                } else {
                    dp[posS, posP] = symbolMatch && dp[posS+1, posP+1]; // simple case
                }  

            }
        }

        return dp[0,0];
    }

    
    public bool DFS(string s, string p, int posS, int posP, int?[,] memo) {
        if(posP == p.Length)
            return posS == s.Length;

        if(memo[posS, posP] != null)
            return memo[posS, posP].Value;

        var symbolMatch = posS < s.Length && (s[posS] == p[posP] || p[posP] == '.');
        var isAsterisk = posP < p.Length-1 && p[posP+1] == '*';

        var res = false;
        if(isAsterisk){
            res = DFS(s, p, posS, posP+2); // skip * and move on
            res = res || symbolMatch && DFS(s, p, posS+1, posP); // continue with current *
        } else {
            res = symbolMatch && DFS(s, p, posS+1, posP+1); // simple case
        }

        memo[posS, posP] = res;
        return res;
    }
    
}

/*
"c"
"c*f"
*/<file_sep>public class Solution {
    public int MinCost(string s, int[] cost) {
        var n = cost.Length;
        var sum = cost[0];
        var max = cost[0];

        for(int i = 1; i < n; i++){
            if(s[i] != s[i-1]){ // when repetitive seq is ended remove max from sum
                sum -= max;
                max = 0;
            }
            // calc sum and max for repeating
            sum += cost[i];
            max = Math.Max(max, cost[i]);
        }

        return sum-max;
    }
}<file_sep>public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        var g = new List<int>[numCourses];
        var indegree = new int[numCourses];
        
        foreach(var p in prerequisites){
            var key = p[1];
            if(g[key] == null)
                g[key] = new List<int>();
            
            g[key].Add(p[0]);
            indegree[p[0]]++;
        }

        var q = new Queue<int>();
        var res = new int[numCourses];
        for(var i = 0; i < indegree.Length; i++)
            if(indegree[i] == 0){
                q.Enqueue(i);
                res.Add(i);
            }
        
        while(q.Any()){
            var course = q.Dequeue();
            var children = g[course];
            if(children == null)
                continue;

            foreach(var child in children){
                indegree[child]--;
                if(indegree[child] == 0){
                    q.Enqueue(child);
                    res.Add(child);
                }
            }
        }
        
        return res;
    }
}

public class Solution {
    private HashSet<int> visited = new HashSet<int>();
    private Stack<int> order = new Stack<int>();
    private HashSet<int>[] g;
    
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        g = new HashSet<int>[numCourses];
        
        foreach(var p in prerequisites){
            var key = p[1];
            if(g[key] == null)
                g[key] = new HashSet<int>();
            
            g[key].Add(p[0]);
        }
        
        for(int i = 0; i < numCourses; i++){
            if (!BFS(i, new HashSet<int>()))
                return new int[0];
        }
        
        return order.ToArray();
    }
    
    private bool BFS(int node, HashSet<int> visiting){
        if(visited.Contains(node))
            return true;
        if(visiting.Contains(node))
            return false;
        
        visiting.Add(node);

        if(g[node] != null)
            foreach(var child in g[node]){
                if (!BFS(child, visiting))
                    return false;
            }
        
        visited.Add(node);
        order.Push(node);
        return true;
    }
}<file_sep>public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        var n = nums.Length;
        var res = new int[n];
        res[0] = nums[0];
        
        for(int i = 1; i < n; i++){
            res[i] = res[i-1] * nums[i]; 
        }

        var product = 1;
        for(int i = n - 2; i >= 0; i--){
            res[i+1] = res[i]*product;
            product *= nums[i+1];
        }

        res[0] = product;
        return res;
    }
}<file_sep>public class Solution {
    public int FindDuplicate(int[] nums) {
        var n = nums.Length;
        for(int i = 0 ; i < n; i++){
            var idx = Math.Abs(nums[i])-1;
            if(nums[idx] < 0)
                return idx+1;
            nums[idx] *= -1;
        }

        return -1;
    }
}<file_sep>public class Solution {
    public bool SequenceReconstruction(int[] org, IList<IList<int>> seqs) {
        var n = org.Length;
        var order = new int[n+1];
        var pairs = new bool[n];
        
        for(var i =0; i < n; i++){
            order[org[i]] = i;
        }
        
        foreach(var seq in seqs){
            for(var i = 0; i< seq.Count; i++){
                if (seq[i] <= 0 || seq[i]> n) return false;
                if (i == 0 && seq[i] == org[0]) pairs[0] = true;
                if (i > 0 && order[seq[i-1]] >= order[seq[i]]) return false;
                if (i > 0 && order[seq[i-1]] + 1 == order[seq[i]]) pairs[order[seq[i]]] = true;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (!pairs[i]) return false;
        }
        return true;

    }
}<file_sep>public class Solution {
    public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) {
        var idx1 = 0;
        var idx2 = 0;
        var res = new List<int[]>();

        while(idx1 < firstList.Length && idx2 < secondList.Length){
            var start1 = firstList[idx1][0];
            var start2 = secondList[idx2][0];
            var end1 = firstList[idx1][1];
            var end2 = secondList[idx2][1];

            if(start2 >= start1 && start2 <= end1 || start1 >= start2 && start1 <= end2)
                res.Add(new int[]{Math.Max(start1, start2), Math.Min(end1, end2)});

            if(end1 <= end2)
                idx1++;
            if(end2 <= end1)
                idx2++;
        }

        return res.ToArray();
    }
}<file_sep>public class Solution {
    public int LengthOfLongestSubstring(string s) {
        var n = s.Length;
        var map = new int[128];
        int l = 0, r = 0, res = 0;
        
        while(r < n){
            var c = s[r];
            l = Math.Max(map[c], l);            
            res = Math.Max(res, r-l+1);
            map[c] = ++r;
        }
        
        return res;
    }
}<file_sep>public class Solution {
    
    public int CheckRecord(int n) {
        var M = (long)Math.Pow(10, 9)+7;
        var dp = new long[n<=5 ? 6 : n+1];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;
        dp[3] = 7; // 8-1
        
        for(var i = 4; i <= n; i++){
            dp[i] = ((2*dp[i-1])%M + (M -  dp[i-4])) % M;
        }
        
        var sum = dp[n];
        for(var i = 1; i <= n; i++){
            sum += (dp[i-1] * dp[n-i]) % M;
        }
        
        return (int)(sum % M);
    }
}<file_sep>public class Solution {
    public string CountAndSay(int n) { // 4
        var num = "1";

        for(; n > 1; n--){ //true 1
            var count = 1;
            var prev = num[0]; // 1
            var sb = new StringBuilder();
            for(int i = 1; i < num.Length; i++){ // true
                var cur = num[i]; // 1
                if(cur != prev){
                    sb.Append(count.ToString()); // 111
                    sb.Append(prev); // 1112

                    count = 1; 
                    prev = cur; // 1
                } else {
                    count++;  // 2
                }
            }

            sb.Append(count.ToString()); // 11122
            sb.Append(prev); // 111221
            num = sb.ToString(); // 1211
        }

        return num;
    }
}<file_sep>public class Solution {
    public int[][] Merge(int[][] intervals) {
        var n = intervals.Length;
        if(n <= 1)
            return intervals;

        Array.Sort(intervals, new IntervalComparer());
        var res = new List<int[]>();
        var cur = intervals[0];

        for(int i = 1; i < n; i++){
            if(cur[1] >= intervals[i][0]){
                cur[0] = Math.Min(cur[0], intervals[i][0]);
                cur[1] = Math.Max(cur[1], intervals[i][1]);
            } else {
                res.Add(cur);
                cur = intervals[i];
            }
        }
        
        res.Add(cur);
        return res.ToArray();
    }

    public class IntervalComparer : IComparer<int[]>{
        public int Compare(int[] a, int[] b){
            return a[0] - b[0];
        }
    }
}<file_sep>public class Solution {
    public int MaxArea(int[] height) {
        int l = 0, res = 0;
        var r = height.Length-1;
        while(l < r){
            res = Math.Max(res, Math.Min(height[l], height[r])*(r-l));
            if (height[l] > height[r])
                r--;
            else
                l++;
        }
        
        return res;
    }
}<file_sep>public class Solution {
    public string GetHint(string secret, string guess) {
        var bulls = 0;
        var cows = 0;
        var n = secret.Length;
        
        if(n == 0)
            return $"{bulls}A{cows}B";
        
        var map = new Dictionary<char, int>();
        foreach(var c in secret){
            if(map.ContainsKey(c))
                map[c] += 1;
            else
                map[c] = 1;
        }
        
        for(var i = 0; i < n; i++){
            var c = guess[i];
            if(map.ContainsKey(c)){
                if(secret[i] == c){
                    bulls++;
                    if(map[c] <= 0)
                        cows--;
                } else {
                    if(map[c] > 0)
                        cows++;
                }
                map[c] -= 1;
            }
        }
        
        return $"{bulls}A{cows}B";
    }
}<file_sep>using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution {

    // Complete the activityNotifications function below.
    static int activityNotifications(int[] ex, int d) {
        var arr = new int[200];
        var i = 0;
        for(; i < d; i++){
            arr[ex[i]]++;
        }

        var mid = (d+1)/2;
        var res = 0;
        i--;

        for(; i < ex.Length-1; i++){
            var counter = 0;
            var median = 0.0;
            for(int j = 0; j < arr.Length; j++){
                counter += arr[j];
                if(counter >= mid){
                    if(d%2 != 0){
                        median = j;
                    } else {
                        var k = j;
                        while(counter == mid){
                            counter += arr[++k];
                        }
                        //Console.WriteLine(j + " " + k);
                        median = (j + k) / 2.0;
                    }
                    break;
                }
            }
            
            //Console.WriteLine(median);

            if(ex[i+1] >= median*2)
                res++;

            var drop = ex[i-(d-1)];
            arr[drop]--;
            arr[ex[i+1]]++;
        }

        return res;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nd = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nd[0]);

        int d = Convert.ToInt32(nd[1]);

        int[] expenditure = Array.ConvertAll(Console.ReadLine().Split(' '), expenditureTemp => Convert.ToInt32(expenditureTemp));
        int result = activityNotifications(expenditure, d);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}
<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        return ReverseList(head, null);
    }
    
    public ListNode ReverseList(ListNode head, ListNode prev) {
        if(head == null)
            return prev;
        
        var next = head.next;        
        head.next = prev;

        return ReverseList(next, head);
        
        
    }
    
    /*public ListNode ReverseList(ListNode head) {
        
        ListNode prev = null;
        var curr = head;
        
        while(curr != null){
            var next = curr.next;
            
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }*/
}<file_sep>public class Solution {
    public string RemoveDuplicates(string s, int k) {
        if(k == 1)
            return "";

        var st = new LinkedList<Symbol>();

        foreach(var c in s){
            var peek = st?.Last?.Value;

            if(peek == null || peek.Char != c){
                st.AddLast(new Symbol{ Char = c, Count = 1});
            } else if(++peek.Count == k){
                st.RemoveLast();
            }
        }

        var sb = new StringBuilder();
        foreach(var symbol in st){
            while(symbol.Count-- > 0)
                sb.Append(symbol.Char);
        }

        return sb.ToString();
    }

    private class Symbol{
        public char Char;
        public int Count;
    }
}<file_sep>public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        	var buckets = new Dictionary<string, List<string>>();
			foreach (var str in strs)
			{
				var charArray = str.ToCharArray();
				Array.Sort(charArray);
				var sortedStr = new string(charArray);

				if (!buckets.TryGetValue(sortedStr, out var val))
				{
					buckets[sortedStr] = new List<string>{str};
				}
				else
				{
					val.Add(str);
				}
			}

			IList<IList<string>> matrix = new List<IList<string>>();

			foreach (var bucket in buckets.Values)
			{
				matrix.Add(bucket);
			}

			return matrix;
    }
}<file_sep>public class Solution {
    public int CompareVersion(string version1, string version2) {
        int i = 0, j = 0;
        int currentVersion1, currentVersion2;
        while(i < version1.Length || j < version2.Length) {
            currentVersion1 = 0;
            while(i < version1.Length && version1[i] != '.'){
                currentVersion1 = currentVersion1 * 10 + (version1[i] - '0');
                ++i;
            }
            
            currentVersion2 = 0;
            while(j < version2.Length && version2[j] != '.'){
                currentVersion2 = currentVersion2 * 10 + (version2[j] - '0');
                ++j;
            }
            
            if(currentVersion1 > currentVersion2)
                return 1;
            if(currentVersion2 > currentVersion1)
                return -1;
            ++i;
            ++j;
        }
        
        return 0;        

    }
}<file_sep>/*
  You're given an array of positive integers representing the prices of a single stock on
  various days (each index in the array represents a different day). You're also
  given an integer k, which represents the number of transactions
  you're allowed to make. One transaction consists of buying the stock on a
  given day and selling it on another, later day.
  
  Write a function that returns the maximum profit that you can make by buying
  and selling the stock, given k transactions.
  
  Note that you can only hold one share of the stock at a time; in other words,
  you can't buy more than one share of the stock on any given day, and you can't
  buy a share of the stock if you're still holding another share. Also, you
  don't need to use all k transactions that you're allowed.
  
  Input = [5, 11, 3, 50, 60, 90]
  k = 2
  
  Output = 93
  
  5, 11, 3, 50, 60, 90
  
  3, 5
  
  60, 90
  
day0  0, 6, -2, 45, 55, 85
day1     0, -8, 39, 49, 79

 55 11 3    60 90 
  */

class Program {
  public static int maxProfitWithKTransactions(int[] prices, int k) {
    if(prices == null || prices.Length < 2*k) // false
        return -1;
      
    return DFS(prices, 0, k, new int?[prices.Length, k]); // [1,2], 0, 1, new[][]
  }
  
  int DFS(int[] prices, int start, int k, int?[,] memo){ //
    if(memo[start, k] != null) //
        return memo[start,k];//
    
    var maxProfitTotal = int.MinValue;//
    for(int i = start; i <= prices.Length-(k-1)*2; i++){//
        var profit = prices[start] - prices[i];
        if(k > 1)
            profit += DFS(prices, i+1, k-1, memo);
        maxProfitTotal = Math.Max(maxProfitTotal, profit);//
    }
    
    memo[start, k] = maxProfitTotal;//
    return maxProfitTotal;
  }
}

/*
class Program { 
    // O(nk) time | O(nk) space 
    public static int maxProfitWithKTra if (prices.length == 0) { return 0; } 
    int[][] profits = new int[k + 1] 
    for (int t = 1; t < k + 1; t++) {
        int maxThusFar = Integer.MIN_VAL; 
        for (int d = 1; d < prices.length; d++) {
            maxThusFar = Math.max(maxThus profits[t][d] = Math.max(profits[t-1][d-1] - prices[d - 1]; 
            profits[t][d] = Math.max(profits[t][d-1], maxThusFar - prices[d]);
            
            return profits[k][prices.length - 1];
        } 
    }
}
*/

<file_sep>public class SnapshotArray {
    List<ValueTuple<int,int>>[] data;
    int snapshots;

    public SnapshotArray(int length) {
        data = new List<ValueTuple<int,int>>[length];
        for(int i = 0; i < length; i++){
            data[i] = new List<ValueTuple<int,int>>{(0, 0)};
        }
    }
    
    public void Set(int index, int val) {
        var versions = data[index];
        
        (var version, _) = versions[versions.Count-1];
        if(snapshots > version){
            versions.Add((snapshots, val));
        } else {
            versions[versions.Count-1] = (version, val);
        }
    }
    
    public int Snap() {
        return snapshots++;
    }
    
    public int Get(int index, int snap_id) {
        var versions = data[index];
            
        var lo = 0;
        var hi = versions.Count;
        while(lo < hi){
            var mid = lo + (hi-lo)/2;
            (var version, var val) = versions[mid];
            if (version == snap_id)
                return val;
            
            if(version > snap_id)
                hi = mid;
            else
                lo = mid + 1;
        }
        
        (var ver, var v) = versions[hi-1];
        return v;
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.Set(index,val);
 * int param_2 = obj.Snap();
 * int param_3 = obj.Get(index,snap_id);
 */<file_sep>public class Solution {
    private ValueTuple<int, int>[] dir = new ValueTuple<int, int>[]{
        (-1,0),
        (-1,1),
        (-1,-1),
        (0,-1),
        (1,1),
        (0,1),
        (1,0),
        (1,-1)
    };
    
    public int ShortestPathBinaryMatrix(int[][] grid) {
        var rows = grid.Length;
        if(rows == 0)
            return -1;
        var cols = grid[0].Length;
        if(grid[0][0] == 1 || grid[rows-1][cols-1] == 1)
            return -1;
                
        var q = new Queue<ValueTuple<int,int,int>>();
        q.Enqueue((0,0,0));
        grid[0][0] = 1;
        
                
        while(q.Any()){
            (var rowS, var colS, var path) = q.Dequeue();
            if(rowS == rows - 1 && colS == cols - 1)
                return path+1;
            
            foreach((var rowD, var colD) in dir){
                var row = rowS + rowD;
                var col = colS + colD;
                if(row >= 0 && col >= 0 && row < rows && col < cols && grid[row][col] != 1){
                    q.Enqueue((row,col, path+1));
                    grid[row][col] = 1;
                }
            }
        }
        
        return -1;
    }
}<file_sep>public class Solution {
    public int MinDistance(string word1, string word2) {
        if (word1 == null || word2 == null)
            return -1;

        var n = word1.Length;
        var m = word2.Length;

        if (n == 0)
            return m;
        if (m == 0)
            return n;

        var dp = new int[n+1, m+1];

        for(int i = 0; i <= n; i++)
            dp[i, 0] = i;

        for(int j = 0; j <= m; j++)
            dp[0, j] = j;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                dp[i+1, j+1] = word1[i] == word2[j] 
                    ? dp[i, j] 
                    : Math.Min(dp[i+1, j], Math.Min(dp[i, j+1], dp[i, j])) + 1;

        return dp[n, m];
    }
}

public class Solution {
    public int MinDistance(string word1, string word2) {
        if (word1 == null || word1.Length == 0)
            return word2.Length;
        if (word2 == null || word2.Length == 0)
            return word1.Length;

        return dfs(word1, word2, 0, 0, new int?[word1.Length+1, word2.Length+1]);
    }

    int dfs(string s1, string s2, int i, int j, int?[,] memo){
        if(i >= s1.Length)
            return s2.Length-j;
        if(j >= s2.Length)
            return s1.Length-i;
        
        if(memo[i, j] != null)
            return memo[i,j].Value;

        var len = 0;
        if(s1[i] == s2[j]){
            len = dfs(s1, s2, i+1, j+1, memo);
        } else {
            var ins = dfs(s1, s2, i+1, j, memo);
            var del = dfs(s1, s2, i, j+1, memo);
            var repl = dfs(s1, s2, i+1, j+1, memo);
            len = Math.Min(ins, Math.Min(del, repl)) + 1;
        }

        memo[i,j] = len;
        return len;
    }
}<file_sep>using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int solution(int N) {
        var max = 0;
        var cur = 0;
        var startCount = false;

        for(int i = 30; i >=0; i--){
            var exponent = 1 << i;
            if(N >= exponent){
                max = Math.Max(max, cur);
                N -= exponent;
                cur = 0;
                startCount = true;
            } else if(startCount){
                cur++;
            }
        }

        return max;
    }
}<file_sep>public class Solution {
    public int[] SortArray(int[] nums) {
        //MergeSort(nums, new int[nums.Length], 0, nums.Length-1);
        QuickSort(nums, 0, nums.Length-1);
        return nums;
    }
    
    public void MergeSort(int[] nums, int[] helper, int lo, int hi) {
        if(lo < hi){
            var mid = lo + (hi-lo)/2;
            MergeSort(nums, helper, lo, mid);
            MergeSort(nums, helper, mid+1, hi);
            Merge(nums, helper, lo, hi, mid);
        }
    }
    
    public void Merge(int[] nums, int[] helper, int lo, int hi, int mid) {
        for(int i = lo; i<= hi; i++)
            helper[i] = nums[i];
        
        var loh = lo;
        var hih = mid+1;
        while(loh <= mid && hih <= hi){
            if(helper[loh] <= helper[hih])
                nums[lo++] = helper[loh++];
            else
                nums[lo++] = helper[hih++];
        }
        
        while(loh <= mid)
            nums[lo++] = helper[loh++];
    }
    
    /////////////////////////////////////////////////////
    
    public void QuickSort(int[] nums, int lo, int hi) {
        if(lo < hi){
            var mid = Partition(nums, lo, hi);
            QuickSort(nums, lo, mid - 1);
            QuickSort(nums, mid + 1, hi);
        }
    }
    
    public int Partition(int[] nums, int lo, int hi) {
        var pivot = nums[hi];
        
        for(int i = lo; i < hi; i++){
            if(nums[i] < pivot)
                Swap(nums, lo++, i);
        }
        
        Swap(nums, lo, hi);
        return lo;
    }
    
    public void Swap(int[] nums, int a, int b){
        var t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}<file_sep>public class Solution {
    private int cols;
    private int rows;
    private int[][] dir = {new []{0,1}, new []{1,0}, new []{0,-1}, new []{-1,0}};
    private int[,] memo;
    
    public int LongestIncreasingPath(int[][] matrix) {
        rows = matrix.Length;
        if(rows == 0)
            return 0;
        cols = matrix[0].Length;
        memo = new int[rows, cols];
        
        var max = 0;
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                max = Math.Max(max, DFS(matrix, i, j));
        
        return max;
    }
    
    private int DFS(int[][] m, int row, int col){
        if(memo[row, col] > 0)
            return memo[row, col];
        
        var len = 0;
        foreach(var d in dir){
            var r = row+d[0];
            var c = col+d[1];
            
            if(r >= 0 && r < rows && c >= 0 && c < cols && m[row][col] < m[r][c])
               len = Math.Max(len, DFS(m, r, c));
        }
        
        memo[row, col] = ++len;
        return len;
    }
}<file_sep>public class Solution {
    public int KthGrammar(int N, int K) {
        if(N == 1)
            return 0;

        var prev = (K+1)/2.0;
        var prevK = (int)prev;
        var takeLeft = prev == (double)prevK;

        var parent = KthGrammar(N-1, prevK);

        return takeLeft ? parent : (parent+1)%2;
    }
}<file_sep>public class Solution {
    public int StoneGameII(int[] piles) {
        var n = piles.Length;
        var maxScore = new int[n];
        
        maxScore[n-1] = piles[n-1];
        for(int i = n-2; i >= 0; i--)
            maxScore[i] = maxScore[i+1] + piles[i];
        
        var memo = new Dictionary<(int, int), int>();
        
        int DFS(int pile, int m){
            if(pile >= n)
                return 0;
            if(n-pile <= 2*m)
                return maxScore[pile];
            
            var key = (pile, m);
            if(memo.ContainsKey(key))
                return memo[key];
            
            var min = int.MaxValue;
            for(var i=1; i <= 2*m; i++){
                min = Math.Min(min, DFS(pile+i, Math.Max(i,m)));
            }

            memo[key] = maxScore[pile] - min;
            return memo[key];
        }
        
        return DFS(0, 1);
    }
}<file_sep>public class Solution {
    public int LongestSubarray(int[] nums, int limit) {
        var max = new LinkedList<int>();
        var min = new LinkedList<int>();
        var lo = 0;
        var hi = 0;        
        var res = 1;
        
        while(hi < nums.Length){
            var v = nums[hi];

            while(max.Any() && max.Last.Value < v)
                max.RemoveLast();
            max.AddLast(v);
            
            while(min.Any() && min.Last.Value > v)
                min.RemoveLast();
            min.AddLast(v);
            
            while(max.First.Value - min.First.Value > limit){
                if(nums[lo] == max.First.Value)
                    max.RemoveFirst();
                if(nums[lo] == min.First.Value)
                    min.RemoveFirst();
                
                lo++;
            }
            
            res = Math.Max(res, hi-lo+1);
            hi++;
        }
        
        return res;
    }
}<file_sep>
/*
Let's say nums looks like this: [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Because it's not fully sorted, we can't do normal binary search. But here comes the trick:

    If target is let's say 14, then we adjust nums to this, where "inf" means infinity:
    [12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

    If target is let's say 7, then we adjust nums to this:
    [-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

    If nums[mid] and target are "on the same side" of nums[0], we just take nums[mid]. Otherwise we use -infinity or +infinity as needed.
*/

public class Solution {
    public int Search(int[] nums, int target) {
        var l = 0;
        var h = nums.Length-1;
        var sub = target < nums[0] ? int.MinValue : int.MaxValue;

        while(l <= h){            
            var mid = l + (h-l)/2;
            var midVal = nums[mid] < nums[0] == target < nums[0] 
                ? nums[mid] 
                : sub;

            if (midVal == target)
                return mid;          
            
            if (target > midVal)
                l = mid+1;
            else
                h = mid-1; 
        }
        
        return -1;
    }
}

public class Solution {
    public int Search(int[] nums, int target) {
        var l = 0;
        var h = nums.Length-1;
        while(l <= h){            
            var mid = l + (h-l)/2;
            var midVal = nums[mid];
            if (midVal == target)
                return mid;            
            
             if (target > midVal)
             {
                if (midVal <= nums[h] && target > nums[h]){
                    h = mid-1;                       
                } else {
                    l = mid+1;
                }
             }
            
            if (target < midVal)
             {
                if (midVal >= nums[l] && target < nums[l]){
                    l = mid+1;                   
                } else {
                    h = mid-1; 
                }
             }

        }
        
        return -1;
    }
}<file_sep>public class Solution {
    public int RemoveStones(int[][] stones) {
        var dsu = new DSU();
        var colsOffcet = 10000;
        
        foreach(var stone in stones){
            dsu.Union(stone[0], stone[1] + colsOffcet);
        }
        
        var sets = new HashSet<int>();
        
        foreach(var stone in stones){
            sets.Add(dsu.Find(stone[0]).Val);
        }
        
        return stones.Length - sets.Count;
    }
    
    public class DSU{
        private Dictionary<int, Node> map = new Dictionary<int, Node>();
        
        public Node Create(int v){
            if (!map.TryGetValue(v, out var node))
                node = map[v] = new Node(v);
            return node;
        }
        
        public void Union(int a, int b){
            var parentA = Find(Create(a));
            var parentB = Find(Create(b));
            
            if (parentA != parentB)
                parentB.Parent = parentA;
        }
        
        public Node Find(int v){
            return Find(map[v]);
        }
        
        public Node Find(Node n){
            return n.Parent == n ? n : Find(n.Parent);
        }
    }
    
    public class Node{        
        public Node Parent;
        public int Val;       
        
        public Node(int val){
            Parent = this;
            Val = val;
        }
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        var set = new Dictionary<string, bool>();
        var res = new List<TreeNode>();
        
        string Lookup(TreeNode node){
            if(node == null)
                return "#";
            
            var id = node.val + "," + Lookup(node.left) + "," + Lookup(node.right);
            if(set.TryGetValue(id, out var used)){
                if(!used){
                    res.Add(node);
                    set[id] = true;
                }
            } else {
                set[id] = false;
            }
            
            return id;
        }
        
        Lookup(root);
        return res;
    }
}<file_sep>public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        if(nums1.Length > nums2.Length)
            return Intersect(nums2, nums1);

        Dictionary<int, int> toMap(int[] nums){
            var map = new Dictionary<int, int>();
            foreach(var n in nums){
                if(map.ContainsKey(n))
                    map[n]++;
                else 
                    map[n] = 1;
            }
            return map;
        }

        var map1 = toMap(nums1);
        var map2 = toMap(nums2);
        var res = new List<int>();
        foreach(var kv in map1){
            if(map2.TryGetValue(kv.Key, out var count))
                res.AddRange(Enumerable.Repeat(kv.Key, Math.Min(kv.Value, count)));
        }

        return res.ToArray();
    }
}<file_sep>
public class Solution {
    public Node Insert(Node head, int insertVal) {
        if(head == null){
            head = new Node(insertVal);
            head.next = head;
            return head;
        }

        var node = head;
        var inserted = false;
        var maxNode = head;
        do{
            var next = node.next;
            if(insertVal >= node.val && insertVal < next.val){
                node.next = new Node(insertVal, next);
                inserted = true;
                break;
            }
            
            if(node.val >= maxNode.val)
                maxNode = node;

            node = next;
        }while(node != head);
        
        if(!inserted){
            maxNode.next = new Node(insertVal, maxNode.next);
        }

        return head;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return EnsureInterval(root, null, null);
    }
    
    private bool EnsureInterval(TreeNode n, int? min, int? max)
    {
        if (n == null)
            return true;
        
        if ((min == null || n.val > min.Value) && (max == null || n.val < max.Value) )
             return EnsureInterval(n.left, min, n.val) && EnsureInterval(n.right, n.val, max);
        
        return false;
    }
}<file_sep>public class Solution {
    int ans = int.MaxValue;
    
    public int TilingRectangle(int n, int m) {
        dfs(0, 0, new bool[n,m], 0);
        return ans;
    }
    
    // (r, c) is the starting point for selecting a square
    // rect records the status of current rectangle
    // cnt is the number of squares we have covered
    private void dfs(int r, int c, bool[,] rect, int cnt) {
        var n = rect.GetLength(0);
        var m = rect.GetLength(1);
        
        // optimization 1: The current cnt >= the current answer
        if (cnt >= ans)
            return;
        
        // Successfully cover the whole rectangle
        if (r == n) {
            ans = cnt; 
            return;
        }
        
        // Successfully cover the area [0, ..., n][0, ..., c] => Move to next row
        if (c == m) {
            dfs(r+1, 0, rect, cnt); 
            return;
        }
        
        // If (r, c) is already covered => move to next point (r, c+1)
        if (rect[r,c]) {
            dfs(r, c+1, rect, cnt);
            return;
        }
        
        // Try all the possible size of squares starting from (r, c)
        for (int k = Math.Min(n-r, m-c); k >= 1 && isAvailable(rect, r, c, k); k--) {
            cover(rect, r, c, k);
            dfs(r, c+k, rect, cnt+1);
            uncover(rect, r, c, k);
        }
    }
    // Check if the area [r, ..., r+k][c, ..., c+k] is alreadc covered
    private bool isAvailable(bool[,] rect, int r, int c, int k) {
        for (int i = 0; i < k; i++){
            for(int j = 0; j < k; j++){
                if(rect[r+i,c+j]) 
                    return false;
            }
        }
        return true;
    }
    // Cover the area [r, ..., r+k][c, ..., c+k] with a k * k square
    private void cover(bool[,] rect, int r, int c, int k) {
        for(int i = 0; i < k; i++){
            for(int j = 0; j < k; j++){
                rect[r+i,c+j] = true;
            }
        }
    }
    // Uncover the area [r, ..., r+k][c, ..., c+k]
    private void uncover(bool[,] rect, int r, int c, int k) {
        for(int i = 0; i < k; i++){
            for(int j = 0; j < k; j++){
                rect[r+i,c+j] = false;
            }
        }
    }
}<file_sep>public class Solution {
    public IList<int> FindClosestElements(int[] arr, int k, int x) {
        var lo = 0;
        var hi = arr.Length-k-1;
        while(lo <= hi){
            var mid = lo + (hi-lo)/2;
            if(x - arr[mid] <= arr[mid + k] - x)
                hi = mid - 1;
            else
                lo = mid + 1;
        }

        var res = new List<int>();
        hi = lo+k;
        while(lo < hi)
            res.Add(arr[lo++]);

        return res;
    }
}

public class Solution {
    public IList<int> FindClosestElements(int[] arr, int k, int x) {
        var res = new List<int>();
        if(k <= 0 || arr.Length == 0)
            return res;

        if(x <= arr[0]){
            for(int i = 0; i < k; i++)
                res.Add(arr[i]);

            return res;
        }

        if(x >= arr[arr.Length-1]){
            for(int i = arr.Length-k; i < arr.Length; i++)
                res.Add(arr[i]);

            return res;
        }

        var lo = 0;
        var hi = arr.Length-1;
        while(lo < hi){
            var mid = lo + (hi-lo)/2;
            if(arr[mid] == x){
                hi = mid;
                break;
            }

            if(arr[mid] > x)
                hi = mid;
            else
                lo = mid + 1;
        }

        lo = hi - 1;
        
        for(int i = 0; i < k; i++){
            if(lo < 0){
                hi++;
                continue;
            }
            if(hi >= arr.Length){
                lo--;
                continue;
            }

            var a = arr[lo];
            var b = arr[hi];
            var d = Math.Abs(a - x) - Math.Abs(b - x);
            
            if(d < 0 || d == 0 && a < b)
                lo--;
            else
                hi++;
        }

        lo++;
        hi--;

        while(lo <= hi)
            res.Add(arr[lo++]);

        return res;

    }
}<file_sep>public class Solution {
    public IList<string> LetterCombinations(string digits) {
        var arr = new []{
            new []{'a','b','c'},
            new []{'d','e','f'},
            new []{'g','h','i'},
            new []{'j','k','l'},
            new []{'m','n','o'},
            new []{'p','q','r','s'},
            new []{'t','u','v'},
            new []{'w','x','y','z'}
        };

        var res = new List<string>();
        
        for(int i = digits.Length-1; i >= 0; i--){
            var idx = digits[i] - '0' - 2;
            
            if(res.Count == 0){
                res = arr[idx].Select(c => c.ToString()).ToList();
                continue;
            }

            var newRes = new List<string>();

            foreach(var c in arr[idx]){
                for(int j = 0; j < res.Count; j++)
                    newRes.Add(c + res[j]);
            }

            res = newRes;
        }

        return res;
    }
}<file_sep>public class Solution {
    public int MinDeletions(string s) {
        var frq = new int[26];
        foreach(var c in s)
            frq[c-'a']++;

        Array.Sort(frq);
        var res = 0;
        for(int i = frq.Length-2; i >= 0 && frq[i] > 0; i--){
            var d = frq[i] - frq[i+1];
            
            if(d >= 0){
                d = frq[i] == d ? d : d+1;
                
                frq[i] -= d;
                res += d;
            }
        }
        
        return res;
    }
}<file_sep>public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        var sb = new StringBuilder();
        if(strs.Length == 0)
            return "";

        var pos = 0;
        while(pos < strs[0].Length){
            var c = strs[0][pos];
            foreach(var str in strs){
                if(pos >= str.Length || str[pos] != c)
                    return sb.ToString();
            }
            sb.Append(c);
            pos++;
        }

        return sb.ToString();
    }
}<file_sep>public class Solution {
    public int CoinChange(int[] coins, int amount) {
        return CoinChange(coins, amount, new int[amount]);
    }
    
    private int CoinChange(int[] coins, int amount, int[] memo){
        if (amount == 0)
            return 0;
        
        if (memo[amount-1] != 0)
            return memo[amount-1];      
        
        var min = int.MaxValue;
        
        for(var i = 0; i < coins.Length; i++){
            if(coins[i] > amount)
                continue;
            
            var res = CoinChange(coins, amount-coins[i], memo);
            
            if(res >= 0 && res < min)
                min = res;
        }
        
        min = min == int.MaxValue ? -1 : min+1;
        
        memo[amount-1] = min;
        
        return min;
    }
}<file_sep>
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        if(k==1)
            return head;

        /*
        
        1-2-3-4 2
        2-1-4-3
        */

        ListNode prevSubHead = null;
        var subHead = head; // 1

        while(subHead != null){ // t
            var nextHead = subHead; // null
            for(int i = 0; i < k; i++){ // 1
                if(nextHead == null)
                    return head;
                nextHead = nextHead.next; 
            }

            // !!! list integrity
            ListNode prev = nextHead; // null
            var curr = subHead; // 3
            while(curr != null && curr != nextHead){  // t
                var t = curr.next; // null
                curr.next = prev; // 2 - 1 - | 4 - 3 - null
                prev = curr; // 3
                curr = t; // 4
            }

            if(prevSubHead == null){
                head = prev;
            } else{
                prevSubHead.next = prev;
            }

            prevSubHead = subHead;
            subHead = nextHead;  // 3
        }

        return head;
    }
}<file_sep>public class Solution {
    public int OrangesRotting(int[][] grid) {
        var rows = grid.Length;
        var cols = grid[0].Length;
        var q = new Queue<(int, int)>();
        var freshCount = 0;
        
        for(int r = 0; r < rows; r++){
            for(int c = 0; c < cols; c++){
                if(grid[r][c] == 1)
                    freshCount++;
                else if(grid[r][c] == 2)
                    q.Enqueue((r,c));
            }
        }

        var dir = new []{(1,0), (0,1), (-1,0), (0,-1)};

        var minutes = 0;
        while(q.Any() && freshCount > 0){
            var count = q.Count;
            for(int i = 0; i < count; i++){
                var (row, col) = q.Dequeue();
                foreach(var (rd, cd) in dir){
                    var r = row+rd;
                    var c = col+cd;
                    if(r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1){
                        q.Enqueue((r,c));
                        grid[r][c] = 2;
                        freshCount--;
                    }
                }
            }
            minutes++;
        }

        return freshCount > 0 ? -1 : minutes;
    }
}<file_sep>public class Solution {
    public string StoneGameIII(int[] stoneValue) {
        var n = stoneValue.Length;
        var maxScore = new int[n];
        
        maxScore[n-1] = stoneValue[n-1];
        for(int i = n-2; i >= 0; i--)
            maxScore[i] = maxScore[i+1] + stoneValue[i];
        
        var memo = new int?[n];
        
        int DFS(int pile){
            if(pile >= n)
                return 0;
            
            if(memo[pile].HasValue)
                return memo[pile].Value;
            
            var min = int.MaxValue;
            for(var i=1; i <= 3; i++){
                min = Math.Min(min, DFS(pile+i));
            }

            memo[pile] = maxScore[pile] - min;
            return memo[pile].Value;
        }
        
        var score = DFS(0)*2;
        
        return score == maxScore[0] 
            ? "Tie" 
            : score > maxScore[0] 
                ? "Alice" 
                : "Bob";
    }
}<file_sep>public class Solution {
    public string MostCommonWord(string paragraph, string[] banned) {
        var maxCount = 0;
        string res = null;
        var frq = new Dictionary<string, int>();
        var bannedSet = new HashSet<string>(banned);

        foreach(var w in paragraph.Split(" !?',;.".ToCharArray())){
            if(string.IsNullOrEmpty(w))
                continue;

            var word = w.ToLower();
            if(frq.ContainsKey(word))
                frq[word]++;
            else
                frq[word] = 1;

            if(!banned.Contains(word) && frq[word] > maxCount){
                maxCount = frq[word];
                res = word;
            }
        }

        return res;
    }
}<file_sep>/*
// Definition for a Node.
public class Node {
    public int val;
    public Node next;
    public Node random;
    
    public Node(int _val) {
        val = _val;
        next = null;
        random = null;
    }
}
*/

public class Solution {
    public Node CopyRandomList(Node head) {
        var map = new Dictionary<Node, Node>();
        var curr = head;
        Node prev = null;
        
        while(curr != null){
            var newNode = new Node(curr.val);
            if(prev != null)
                prev.next = newNode;
            map[curr] = newNode;
            curr = curr.next;
            prev = newNode;
        }
        
        curr = head;
        while(curr != null){
            if(curr.random != null){
                map[curr].random = map[curr.random];
            }
            curr = curr.next;
        }
        
        return head != null ? map[head] : null;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<string> BinaryTreePaths(TreeNode root) {
        var res = new List<string>();
        if(root == null)
            return res;

        var q = new Queue<(TreeNode, string)>();
        q.Enqueue((root, ""));
        while(q.Any()){
            var (node, path) = q.Dequeue();
            if(path != "")
                path += "->";
            path += node.val;
            if(node.left == null && node.right == null)
                res.Add(path);
            else {
                if(node.left != null)
                    q.Enqueue((node.left, path));
                if(node.right != null)
                    q.Enqueue((node.right, path));
            }
        }

        return res;
    }
}<file_sep>public class Solution {
    /*
    
    ab
    adc
    
    */
    public string AlienOrder(string[] words) {
        var g = new Dictionary<char, HashSet<char>>(); // c[d] d[f]
        var indegree = new Dictionary<char, int>(); // c0 d1 f1

        foreach(var word in words)
            foreach(var c in word)
                indegree[c] = 0;

        for(int i = 1; i < words.Length; i++){ // f
            var w1 = words[i-1]; // abd
            var w2 = words[i]; // abf
            var pos = 0; // 2
            while(pos < w1.Length && pos < w2.Length){ 
                var a = w1[pos]; // d
                var b = w2[pos]; // f

                if(a != b){ // t
                    if(!g.ContainsKey(a) || !g[a].Contains(b)){
                        if(!g.ContainsKey(a))
                            g[a] = new HashSet<char>();
                        g[a].Add(b);
                        indegree[b]++;
                    }
                    break;
                }
                pos++;
            }
            // w1 should  not be longer!
            if(pos == w2.Length && w2.Length != w1.Length) // adc ab
                return "";
        }

        var q = new Queue<char>(); // d
        foreach(var kv in indegree){
            if(kv.Value == 0)
                q.Enqueue(kv.Key);
        }

        var sb = new StringBuilder(); // cd
        // c[d] d[f]
        // c0 d0 f0

        while(q.Any()){
            var c = q.Dequeue();
            sb.Append(c);

            if(!g.ContainsKey(c))
                continue;
            
            foreach(var nei in g[c]){
                indegree[nei]--;
                if(indegree[nei] == 0)
                    q.Enqueue(nei);
            }
        }
        
        Console.WriteLine(sb.ToString());

        return sb.Length == indegree.Count ? sb.ToString() : "";
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public string serialize(TreeNode root) {
        var sb = new StringBuilder();
        serialize(root, sb);
        return sb.ToString();
    }

    public void serialize(TreeNode node, StringBuilder sb) {
        if(node == null)
            return;
        sb.Append(node.val).Append(' ');
        serialize(node.left, sb);
        serialize(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        var q = new Queueu<int>();
        foreach(var str in data.Split(' '))
            q.Enqueue(int.Parse(str));

        return deserialize(q, int.MinValue, int.MaxValue);
    }

    public TreeNode deserialize(Queue<int> q, int min, int max) {
        if(!q.Any())
            return null;

        var n = q.Peek();
        if(n < min && n > max)
            return null;

        q.Dequeue();
        var node = new TreeNode(n);
        node.left = deserialize(q, min, n);
        node.right = deserialize(q, n, max);
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;<file_sep>public class Solution {
    public double MyPow(double x, int n) {
        var N = (long)n;
        if(N < 0){
            N *= -1;
            x = 1/x;
        }

        double fastPow(double x, long n){
            if(n == 0)
                return 1;
            var res = fastPow(x, n/2);
            res *= res;
            if(n % 2 == 1)
                res *= x;
            return res;
        }


        return fastPow(x, N);
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var st = new Stack<TreeNode>();
        
        void moveLeft(TreeNode node){
            while(node != null){
                st.Push(node);
                node = node.left;
            }
        }

        moveLeft(root);

        while(st.Any()){
            var node = st.Pop();
            if(--k == 0)
                return node.val;

            if(node.right != null){
                moveLeft(node.right);
            }
        }

        return -1;
    }
}<file_sep>public class Solution {
    public bool CanFinish(int n, int[][] prerequisites) {
        var inDegree = new int[n];
        var g = new Dictionary<int, HashSet<int>>();

        foreach(var edge in prerequisites){
            var next = edge[0];
            var prev = edge[1];

            inDegree[next]++;

            if(!g.ContainsKey(prev))
                g[prev] = new HashSet<int>();

            g[prev].Add(next);
        }

        var q = new Queue<int>();
        for(int i = 0; i < n; i++){
            if(inDegree[i] == 0)
                q.Enqueue(i);
        }

        while(q.Any()){
            var course = q.Dequeue();

            if(g.ContainsKey(course)){
                foreach(var next in g[course]){
                    inDegree[next]--;
                    if(inDegree[next] == 0)
                        q.Enqueue(next);
                }
            }
        }

        return !inDegree.Any(course => course > 0);
    }
}<file_sep>public class Solution {
    public string FindReplaceString(string S, int[] indexes, string[] sources, string[] targets) {
        if(S == "")
            return S;
        
        var replacements = new int[S.Length];
        
        for(int i = 0; i < indexes.Length; i++){
            var pos = indexes[i];
            var source = sources[i];
            
            var k = 0;
            while(k < source.Length && S[pos+k] == source[k])
                k++;
            
            if(k == source.Length){
                replacements[pos] = i+1;
                for(var j = 1; j < source.Length; j++)
                    replacements[pos+j] = -1;
            }
        }
        
        var sb = new StringBuilder();
        var ptr = 0;
        for(var i = 0; i < replacements.Length; i++){
            var idx = replacements[i];
            
            if(idx != -1){
                if (idx > 0){
                    foreach(var c in targets[idx-1])
                        sb.Append(c);
                } else {
                    sb.Append(S[ptr]);
                }
            }

            ptr++;
        }
        
        return sb.ToString();
    }
}<file_sep>// 438, 3
public class Solution {
    public string MinWindow(string s, string p) {
        var res = "";
        if(s.Length == 0 || p.Length > s.Length)
            return res;

        var frq = new Dictionary<char, int>();
        foreach(var c in p)
            frq[c] = frq.ContainsKey(c) ? frq[c] + 1 : 1;

        var count = p.Length;
        var lo = 0;
        var hi = 0;

        while(hi < s.Length){
            var c = s[hi++];

            if(frq.ContainsKey(c)){
                frq[c]--;
                if(frq[c] >= 0)
                    count--; 
            }
            
            while(count == 0 && lo < hi){
                if(res == "" || hi - lo < res.Length)
                    res = s.Substring(lo, hi-lo);

                c = s[lo++];
                if(frq.ContainsKey(c)){
                    frq[c]++;
                    if(frq[c] > 0)
                        count++;
                }
            }
        }
        
        return res;
    }

}<file_sep>public class FileSystem {

    private Node fs;

    public FileSystem() {
        fs = new Node{Name = "/"};
    }
    
    public IList<string> Ls(string path) {
        var dir = Navigate(path);
        var ls = new List<string>();

        if(dir.IsFile){
            ls.Add(dir.Name);
            return ls;
        }

        if(dir.Children == null)
            return ls;

        foreach(var kv in dir.Children)
            ls.Add(kv.Key);

        return ls;
    }
    
    public void Mkdir(string path) {
        Navigate(path);
    }
    
    public void AddContentToFile(string filePath, string content) {
        var f = Navigate(filePath);
        f.IsFile = true;
        f.Content = f.Content == null ? content : f.Content + content;
    }
    
    public string ReadContentFromFile(string filePath) {
        var f = Navigate(filePath);
        return f.Content;
    }

    private Node Navigate(string path){
        var cur = fs;
        
        foreach(var name in path.Split('/'))
            if(!string.IsNullOrEmpty(name))
                cur = cur.GetAddChild(name);

        return cur;
    }

    private class Node{
        public string Name;
        public SortedDictionary<string, Node> Children;
        public string Content;
        public bool IsFile;

        public Node GetAddChild(string name){
            if(Children == null)
                Children = new SortedDictionary<string, Node>();

            if(!Children.ContainsKey(name))
                Children[name] = new Node{Name = name};

            return Children[name];
        }
    }
}
<file_sep>public class Solution {
    public string Encode(string s) {
        return Encode(s, new Dictionary<string, string>());
    }
    
    public string Encode(string s, Dictionary<string, string> memo){
        var n = s.Length;
        if(n <= 4)
            return s;
        if(memo.ContainsKey(s))
            return memo[s];
        
        string res = null;
        for(var i=1; i <= n/2; i++){
            var sub = s.Substring(0, i);
            var repeatCount = CountRepetitions(s, sub);
            
            for(var j = 1; j <= repeatCount; j++){
                var head = j == 1 ? sub : $"{j}[{Encode(sub, memo)}]";
                
                if(res != null && head.Length >= res.Length)
                    break;
                
                var tail = Encode(s.Substring(i*j), memo);
                
                if(res == null || head.Length+tail.Length < res.Length)
                    res = head+tail;
            }
        }
        
        memo[s] = res;
        return res;
    }
    
    private  int CountRepetitions(string s, string sub){
        var res = 1;
        var n = sub.Length;
        for(var i = n; i <= s.Length-n; i += n){
            var j = 0;
            while(j<n && s[i+j] == s[j])
                j++;
            if(j != n)
                break;
            res++;
        }
        return res;
    }
}<file_sep>public class Solution {
    public IList<int> MostSimilar(int n, int[][] roads, string[] names, string[] targetPath) {
        var g = new List<int>[n];
        var len = targetPath.Length;
        
        foreach(var r in roads){
            var a = r[0];
            var b = r[1];
            if(g[a] == null)
                g[a] = new List<int>();
            if(g[b] == null)
                g[b] = new List<int>();
            
            g[a].Add(b);
            g[b].Add(a);
        }
        
        var end = targetPath[len-1];
        var dp = new int[len, n][];
        
        for(int j = 0; j < n; j++){
            dp[len-1,j] = new []{ names[j]==end ? 0 : 1, -1}; // cost;next city
        }
        
        for(var i = len-1; i > 0; i--){
            var currMin = int.MaxValue;
            for(var j = 0; j < n; j++){
                var city = dp[i,j];
                if(city == null || city[0]-i >= currMin)
                    continue;
                
                foreach(var nei in g[j]){
                    var cost = city[0] + (names[nei] == targetPath[i-1] ? 0 : 1);
                    if(dp[i-1, nei] == null || cost < dp[i-1, nei][0]){
                        dp[i-1, nei] = new []{cost, j};
                        currMin = Math.Min(currMin,cost);
                    }
                }
            }
        }
        
        var min = int.MaxValue;
        var res = new int[len];
        
        for(int j = 0; j < n; j++){
            var cur = dp[0,j];
            if(cur != null && cur[0] < min){
                min = cur[0];
                res[0] = j;
            }
        }
        
        for(int i = 0; i < len-1; i++){
            res[i+1] = dp[i,res[i]][1];
        }
        
        return res;
    }
}<file_sep>public class Solution {
    public string[] ReorderLogFiles(string[] logs) {
        return logs
            .Select(l => new Record(l))
            .OrderBy(r => r)
            .Select(r => r.Str)
            .ToArray();
    }

    class Record : IComparable<Record>{
        private bool isDigit;
        private string[] split;
        public string Str;

        public Record(string str){
            Str = str;
            split = str.Split(' ', 2);
            isDigit = split[1][0] <= '9';
        }

        public int CompareTo(Record other){
            if(isDigit)
                return other.isDigit ? 0 : 1;

            if(other.isDigit)
                return -1;

            var res = split[1].CompareTo(other.split[1]);
            return res == 0
                ? split[0].CompareTo(other.split[0])
                : res;
        }
    }
}<file_sep>public class Solution {
    public int LongestLine(int[][] M) {
        var rows = M.Length;
        if(rows == 0)
            return 0;
        var cols = M[0].Length;
        var max = 0;
        var dp = new int[cols, 3];
        
        for(var r = 0; r < rows; r++){
            var row = 0;
            var prevDiag = 0; 
            for(var c = 0; c < cols; c++){
                var col = 0;
                var diag = 0;
                var adiag = 0;
                    
                if(M[r][c] == 1){
                    row++;
                    col = dp[c,0] + 1;
                    diag = c != 0 ? prevDiag + 1 : 1;
                    adiag = c < cols-1 ? dp[c+1,2] + 1 : 1;
                    max = Math.Max(max , Math.Max(row, Math.Max(col, Math.Max(diag, adiag))));
                } else {
                    row = 0;
                }
                
                dp[c, 0] = col;
                // !!! prevent override
                prevDiag = dp[c, 1];
                dp[c, 1] = diag;
                dp[c, 2] = adiag;
            }
        }
        
        return max;
    }
}<file_sep>public class Solution {
    public IList<string> FindAllConcatenatedWordsInADict(string[] words) {
        var res = new List<string>();

        if(words.Length < 2)
            return res;

        var sorted = words.Where(w => w != null && w.Length > 0).OrderBy(w => w.Length).ToArray();
        var minLen = sorted[0].Length;
        var wordsSet = new HashSet<string>();
        var maxLen = 0;
        foreach(var word in sorted){
            //if(word.Length >= minLen*2 && WordBreak(word, wordsSet, minLen, maxLen))
            if(word.Length >= minLen*2 && WordBreak(word, wordsSet))
                res.Add(word);
            
            wordsSet.Add(word);
            maxLen = Math.Max(maxLen, word.Length);
        }

        return res;
    }

    public bool WordBreak(string s, HashSet<string> set) {
        var n = s.Length;
        var memo = new bool[n+1];
        memo[0] = true;

        for(int i = 1; i<= n; i++){
            for(int j = i-1; j >=0; j--){
                if(memo[j] && set.Contains(s.Substring(j, i-j))){
                    memo[i] = true;
                    break;
                }
            }
        }

        return memo[n];
    }

    public bool WordBreak(string s, HashSet<string> words, int minLen, int maxLen) {
        var memo = new List<bool?>[s.Length];

        bool DFS(int idx){
            if(memo[idx] != null)
                return memo[idx];

            var res = false;
            var sb = new StringBuilder();
            for(int i = idx; i < s.Length && i-idx+1 <= maxLen; i++){
                sb.Append(s[i]);
                if(i-idx+1 < minLen)
                    continue;

                var word = sb.ToString();
                if(words.Contains(word) && (i == s.Length-1 || DFS(i+1))){
                    res = true;
                    break;
                }
            }

            memo[idx] = res;
            return res;
        }
        
        return DFS(0);
    }
}<file_sep>public class Solution {
    public int PeakIndexInMountainArray(int[] arr) {
        int lo = 0, hi = arr.Length - 1;
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (arr[mi] < arr[mi + 1])
                lo = mi + 1;
            else
                hi = mi;
        }
        return hi;
    }
}<file_sep>public class Solution {
    /*
    a
    ac

    aa
    aaa

    aaaaaa
    aaabaaa

    aaabaaa
    aaaaaaa
    */
    public bool IsOneEditDistance(string s, string t) {
        var lenS = s.Length; // 3
        var lenT = t.Length; // 2

        if(lenS != lenT && Math.Abs(lenS - lenT) != 1)
            return false;

        var edited = false;
        var idxS = 0; // 1
        var idxT = 0; // 1
        while(idxS < lenS && idxT < lenT){ // t
            if(s[idxS] == t[idxT]){ // t
                idxS++;
                idxT++;
            } else {
                if(edited) // f
                    return false;

                edited = true;
                if(lenS <= lenT) // f
                    idxT++;
                if(lenT <= lenS) // t
                    idxS++;
            }
        }

        return edited && idxS == lenS && idxT == lenT || !edited && Math.Abs(lenS - lenT) == 1;
    }
}<file_sep>public class Solution {
    public IList<string> RemoveInvalidParentheses(string s) {
        var res = new List<string>();
        dfs(s, res, false, 0, 0);
        return res;
    }

    public static void dfs(String s, List<String> res, bool isReversed, int last_i, int last_j) {
        var check = isReversed ? new char[]{')', '('} : new char[]{'(', ')'};
        var count = 0;
        var i = last_i;
        for (; i < s.Length && count>= 0; i++) {
            if (s[i] == check[0]) count++;
            if (s[i] == check[1]) count--;
        }

        if (count >= 0)  {
            // no extra ')' is detected. We now have to detect extra '(' by reversing the string.
            var reversed = new String(s.Reverse().ToArray());
            if (!isReversed) 
                dfs(reversed, res, true, 0, 0);
            else 
                res.Add(reversed);
        }

        else {  // extra ')' is detected and we have to do something
            i -= 1; // 'i-1' is the index of abnormal ')' which makes count<0
            for (int j = last_j; j <= i; j++) {
                if (s[j] == check[1] && (j == last_j || s[j-1] != check[1])) {
                    dfs(s.Remove(j,1), res, isReversed, i, j);
                }
            }
        }
    }
}<file_sep>// quick select
public class Solution {
    public int[][] KClosest(int[][] points, int k) {
        var n = points.Length;
        if(n == k)
            return points;

        var res = new int[k][];

        int distance(int[] p) => p[0]*p[0] + p[1]*p[1];

        void swap(int a, int b){
            if(a == b) return;
            var t = points[a];
            points[a] = points[b];
            points[b] = t;
        }

        int partition(int lo, int hi){
            var pivot = distance(points[hi]);

            for(int i = lo; i < hi; i++){
                if(distance(points[i]) < pivot)
                    swap(lo++, i);
            }

            swap(lo, hi);
            return lo;
        }
        
        var lo = 0;
        var hi = n-1;
        var mid = -1;
        while(lo < hi && mid != k){
            mid = partition(lo, hi);
            if(mid > k)
                hi = mid-1;
            else
                lo = mid+1;
        }

        Array.Copy(points, res, k);

        return res;
    }
}<file_sep>/*
// Definition for a Node.
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
*/

public class Solution {
    public Node Connect(Node root) {
        if(root == null)
            return null;

        var left = root;
        while(left != null){
            var parent = left;
            left = parent.left;
            while(parent != null){
                parent.left.next = parent.right;
                if(parent.next != null){
                    parent.right.next = parent.next.left;
                parent = parent.next;
            }
        }

        return root;
    }
}<file_sep>public class Solution {
    public string NextClosestTime(string time) {
        var nums = new int[]{
            time[0] - '0',
            time[1] - '0',
            time[3] - '0',
            time[4] - '0'
        };
        
        var tmins = (nums[0]*10+nums[1])*60+nums[2]*10+nums[3];
        
        var res = new int[4];
        var diff = int.MaxValue;
        
        foreach(var n1 in nums.Where(n => n < 3))
            foreach(var n2 in nums.Where(n => n1*10+n < 24))
                foreach(var n3 in nums.Where(n => n < 6))
                    foreach(var n4 in nums.Where(n => n3*10+n < 60)){
                        if (n1*10+n2 < 24 && n3*10+n4 < 60){
                            var mins = (n1*10+n2)*60+n3*10+n4;
                            if(mins <= tmins)
                                mins = mins + 60 * 24;
                            if(mins - tmins < diff){
                                res[0]=n1;
                                res[1]=n2;
                                res[2]=n3;
                                res[3]=n4;
                                diff = mins - tmins;
                            }
                        }
                    }
        
        return $"{res[0]}{res[1]}:{res[2]}{res[3]}";
    }
    
     static IEnumerable<ValueTuple<int,int,int,int>> DoPermute(int[] nums, int start, int end)
        {
            if (start == end)
            {
                yield return (nums[0], nums[1], nums[2], nums[3]);
            }
            else
            {
                for (var i = start; i <= end; i++)
                {
                    Swap(ref nums[start], ref nums[i]);
                    foreach (var r in DoPermute(nums, start + 1, end))
                        yield return r;
                    Swap(ref nums[start], ref nums[i]);
                }
            }
        }

        static void Swap(ref int a, ref int b)
        {
            var temp = a;
            a = b;
            b = temp;
        }
}<file_sep>public class Solution {
    public int[] AssignBikes(int[][] workers, int[][] bikes) {
        var lenW = workers.Length;
        var lenB = bikes.Length;
        var res = new int[lenW];
        var buckets = new List<ValueTuple<int, int>>[2000];
        
        for(var w = 0; w < lenW; w++){
            for(var b = 0; b < lenB; b++){
                var dist = Math.Abs(bikes[b][0] - workers[w][0]) + Math.Abs(bikes[b][1] - workers[w][1]);
                if (buckets[dist] == null){
                    buckets[dist] = new List<ValueTuple<int,int>>{(w, b)};
                } else {
                    buckets[dist].Add((w,b));
                }
            }
        }
        
        var left = lenW;
        for(int i = 0; i < buckets.Length && left > 0; i++){
            var list = buckets[i];
            if(list == null)
                continue;
            
            foreach((var w, var b) in list){
                if(workers[w] != null && bikes[b] != null){
                    res[w] = b;
                    workers[w] = null;
                    bikes[b] = null;
                    left--;
                }
            }
        }
        
        return res;
    }

}<file_sep>public class Solution {
    public IList<string> WordBreak(string s, IList<string> wordDict) {
        var words = new HashSet<string>();
        var maxLen = 0;
        var minLen = int.MaxValue;
        var memo = new List<string>[s.Length];

        foreach(var w in wordDict){
            maxLen = Math.Max(maxLen, w.Length);
            minLen = Math.Min(minLen, w.Length);
            words.Add(w);
        }

        List<string> DFS(int idx){
            if(memo[idx] != null)
                return memo[idx];

            var res = new List<string>();
            
            var sb = new StringBuilder();
            for(int i = idx; i < s.Length && i-idx+1 <= maxLen; i++){
                sb.Append(s[i]);
                if(i-idx+1 < minLen)
                    continue;

                var word = sb.ToString();
                if(words.Contains(word)){
                    if(i == s.Length-1){
                        res.Add(word);
                    } else {
                        foreach(var str in DFS(i+1))
                            res.Add(word + " " + str);
                    }
                }
            }

            memo[idx] = res;
            return res;
        }
        
        return DFS(0);
    }
}<file_sep>public class Solution {
    public int NumMatchingSubseq(string S, string[] words) {
        var res = 0;
        var n = words.Length;
        var buckets = new List<Wrapper>[26];
        
        foreach(var word in words){
            var w = new Wrapper(word);
            var idx = w.Head - 'a';
            if(buckets[idx] == null)
                buckets[idx] = new List<Wrapper>(5000);

            buckets[idx].Add(w);
        }
        
        for(int i = 0; i < S.Length; i++){
            var idx = S[i]-'a';
            var bucket = buckets[idx];
            if(bucket == null || !bucket.Any())
                continue;
            
            var newBucket = new List<Wrapper>();
            foreach(var w in bucket){
                w.ptr += 1;
                if(w.Head == -1){
                    res++;
                    continue;
                }
                if(w.Head == S[i])
                    newBucket.Add(w);
                else{
                    if(buckets[w.Head - 'a'] == null)
                        buckets[w.Head - 'a'] = new List<Wrapper>(5000);
                    buckets[w.Head - 'a'].Add(w);
                }
            }
            buckets[idx] = newBucket;
        }
        
        return res;
    }
    
    class Wrapper{
        string s;
        public int ptr;
        
        public Wrapper(string s){
            this.s = s;
        }
        
        public int Head => ptr < s.Length ? s[ptr] : -1;
    }
}<file_sep>public class Solution {
    public bool IsPossibleDivide(int[] hand, int W) {
        var n = hand.Length;
        if(n % W != 0)
            return false;
        
        var heap = new SortedDictionary<int, int>();
        for(int i = 0; i < n; i++){
            if(heap.ContainsKey(hand[i]))
                heap[hand[i]] += 1;
            else
                heap[hand[i]] = 1;
        }
        
        for(int i = 0; i < n / W; i++){
            var min = heap.First().Key;
            
            for(int j = 0; j < W; j++){
                if(!heap.ContainsKey(min+j))
                    return false;
                
                if(heap[min+j] > 1)
                    heap[min+j] -= 1;
                else
                    heap.Remove(min+j);
            }
        }
        
        return true;
    }
}<file_sep>public class Solution {
    public int MaxLength(IList<string> arr) {
        var n = arr.Count;
        var dp = new List<(int, int)>();
        dp.Add((0,0));
        var max = 0;

        for(int i = 0; i < n; i++){
            var str = arr[i];
            var mask = 0;
            foreach(var c in str){
                var b = 1 << (c-'a');
                if((b | mask) != (b  ^ mask)){
                    mask = -1;
                    break;
                }
                mask |= b;
            }
            
            if(mask == -1)
                continue;

            for(int j = dp.Count-1; j >= 0; j--){
                var (m,l) = dp[j];
                if((m  & mask) == 0){
                    var len = str.Length + l;
                    dp.Add((m | mask, len));
                    max = Math.Max(max, len);
                }
            }
        }

        return max;
    }
}<file_sep>public class Solution {
    public int SumSubarrayMins(int[] A) {
        int MOD = 1000000007;
        var res = 0;
        var mins = new Stack<ValueTuple<int, int>>();
        var sum = 0;
        
        for(int i=0; i < A.Length; i++){
            var v = A[i];
            var count = 1;
            
            while(mins.Count > 0)
            {
                (var vPrev, var countPrev) = mins.Peek();
                
                if(vPrev<v)
                    break;
                
                count += countPrev;
                mins.Pop();
                sum -= (vPrev*countPrev);
            }
            
            mins.Push((v, count));
            sum += v*count;

            res += sum;
            res %= MOD;
        }
        
        return res;
    }
}<file_sep>public class Solution {
    public int[] PrisonAfterNDays(int[] cells, int N) {
        
        int calcState(int[] a){
            var b = 0;
            for(int i = 0; i < a.Length; i++){
                b <<= 1;
                b |= a[i];
            }
            return b;
        }

        var visited = new Dictionary<int, int>();
        visited[calcState(cells)] = 0;
        var daysCount = 1;

        while(N > 0){
            var curCells = new int[cells.Length];
            for(int i = 1; i < cells.Length-1; i++)
                curCells[i] = cells[i-1] != cells[i+1] ? 0 : 1;

            if(visited != null){
                var curState = calcState(curCells);

                if(visited.ContainsKey(curState)){
                    var cycleLength = daysCount-visited[curState];
                    N %= cycleLength; // magic
                    visited = null;
                } else {
                    visited[curState] = daysCount++;
                }
            }

            if(N > 0)
                cells = curCells;
            N--;
        }

        return cells;
    }
}<file_sep>public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        
        var graph = new Dictionary<string, Dictionary<string, double>>();
        
        for (var i = 0; i < equations.Count; i++){
            var dividend = equations[i][0];
            var divisor = equations[i][1];
            var quotent = values[i];
            
            if (!graph.TryGetValue(dividend, out var d1)){
                d1 = new Dictionary<string, double>();
                graph.Add(dividend, d1);
            }
            if (!graph.TryGetValue(divisor, out var d2)){
                d2 = new Dictionary<string, double>();
                graph.Add(divisor, d2);
            }
            
            d1.Add(divisor, quotent);
            d2.Add(dividend, 1/quotent);
        }
        
        var res = new double[queries.Count];
                                
        
        for(var i = 0; i < queries.Count; i++){
            var start = queries[i][0];
            var end = queries[i][1];
            
            if (!graph.ContainsKey(start) || !graph.ContainsKey(end)){
                res[i] = -1;
                continue;
            }
            if(start == end){
                res[i] = 1;
                continue;
            }            
            
            res[i] = -1;
            var visited = new HashSet<string>();
            
            res[i] = DFS(graph, start, end, visited, 1);
            
            /* DFS
            var q = new Queue<ValueTuple<string, double>>();
            q.Enqueue((start, 1.0));
            
            while(q.Count > 0){
                (string node, double sum) = q.Dequeue();
                
                visited.Add(node);
                var nodes = graph[node];
                
                if (nodes.TryGetValue(end, out var val)){
                    res[i] = sum*val;
                    break;
                }
                
                foreach(var kv in nodes){                    
                    if(visited.Contains(kv.Key))
                        continue;                   
                    
                    q.Enqueue((kv.Key, sum*kv.Value));
                }
            }
            */
        }

        return res;
    }
    
    private double DFS(Dictionary<string, Dictionary<string, double>> graph, string curr, string target, HashSet<string> visited, double sum){
        var nodes = graph[curr];
        
        if (nodes.TryGetValue(target, out var val)){
            return sum * val;    
        }     
        
        visited.Add(curr);
        var ret = -1.0;
        
        foreach(var kv in nodes.Where(n => !visited.Contains(n.Key))){
            ret = DFS(graph, kv.Key, target, visited, sum*kv.Value);
            
            if(ret > -1)
                break;
        }
        
        //visited.Remove(curr);
        return ret;
    }
}<file_sep>public class Solution {
    /*
    2
    aabaccc

    */
    public int LengthOfLongestSubstringKDistinct(string s, int k) {
        if(k==0)
            return 0;

        int[] frq = new int[256];
        int count = 0;
        var lo = 0;
        var res = 0;
    
        for (int hi = 0; hi < s.Length; hi++) {
            if (frq[s[hi]]++ == 0)
                count++;
            
            if (count > k) {
                while (--frq[s[lo++]] > 0);
                    count--;
            }
            
            res = Math.Max(res, hi - lo + 1);
        }
    
        return res;
    }
}<file_sep>public class MedianFinder {

    SortedDictionary<int, int> lo;
    SortedDictionary<int, int> hi;
    int countLo;
    int countHi;

    public MedianFinder() {
        lo = new SortedDictionary<int, int>();
        hi = new SortedDictionary<int, int>(new DescComparer());
    }
    
    public void AddNum(int num) {
        Add(lo, num, ref countLo);
        var top = RemoveTop(lo, ref countLo);
        Add(hi, top, ref countHi);

        while(countHi > countLo){
            top = RemoveTop(hi, ref countHi);
            Add(lo, top, ref countLo);
        }
    }
    
    public double FindMedian() {
        var isOdd = (countLo+countHi)%2 == 1;
        return isOdd 
            ? lo.First().Key
            : ((double)lo.First().Key + hi.First().Key) / 2;
    }

    private void Add(SortedDictionary<int, int> d, int num, ref int count){
        if(d.ContainsKey(num))
            d[num] += 1;
        else
            d[num] = 1;

        count++;
    }

    private int RemoveTop(SortedDictionary<int, int> d, ref int count){
        var top = d.First();
        if(top.Value == 1)
            d.Remove(top.Key);
        else
            d[top.Key] -= 1;

        count--;
        return top.Key;
    }

    class DescComparer : IComparer<int>{
        public int Compare(int a, int b) {
            return b-a;
        }
    }
}<file_sep>public class Solution {
    public bool CheckIfExist(int[] arr) {
        var set = new HashSet<int>();
        foreach(var n in arr){
            if(set.Contains(n*2) || (n%2 == 0 && set.Contains(n/2)))
                return true;
            set.Add(n);
        }
        return false;
    }
}<file_sep>public class Solution {
    public int MinKBitFlips(int[] A, int K) {
        var q = new Queue<int>();
        var n = A.Length;
        var flips = 0;
        for(int i = 0; i < n; i++){
            if(A[i] == 0){
                if(q.Count%2 == 0){
                    q.Enqueue(i+K-1);
                    flips++;
                }
            } else {
                if(q.Any() && q.Count%2 == 1){
                    q.Enqueue(i+K-1);
                    flips++;
                }
            }
            
            if(q.Any() && q.Peek() <= i)
                q.Dequeue();
        }
        
        return q.Any() ? -1: flips;
    }
}<file_sep>public class Solution {
    public int Divide(int dividend, int divisor) {
        if(dividend == int.MinValue && divisor == -1)
            return int.MaxValue;

        uint a = dividend >= 0 ? (uint)dividend : (uint)(-(int)(dividend+1))+1;
        uint b = divisor >= 0 ? (uint)divisor : (uint)(-(int)(divisor+1))+1;
        var res = 0;

        for(int exp = 31; exp >= 0 && a >= b; exp--){
            if(a >> exp >= b){
                a -= b << exp;
                res += 1 << exp;
            }
        }

        return dividend > 0 == divisor > 0 ? res : -res;
    }
}<file_sep>	public class Solution
	{
		public bool BackspaceCompare(string S, string T)
		{
			var sCurrent = S.Length - 1;
			var tCurrent = T.Length - 1;

			while (sCurrent >= 0 && tCurrent >= 0)
			{
				PeekNextIndex(S, ref sCurrent);
				PeekNextIndex(T, ref tCurrent);
                
				if (sCurrent < 0 || tCurrent < 0)
					return sCurrent == tCurrent;

				if (S[sCurrent] != T[tCurrent])
					return false;

				sCurrent--;
				tCurrent--;
			}
            
            PeekNextIndex(S, ref sCurrent);
			PeekNextIndex(T, ref tCurrent);

			return sCurrent == tCurrent;
		}


		private static void PeekNextIndex(string str, ref int current)
		{
			var skip = 0;

			while (current >= 0)
			{
				if (str[current] == '#')
				{
					skip++;
				}
				else
				{
					if (skip > 0)
						skip--;
					else
						return;
				}

				current--;
			}
		}
	}<file_sep>/**
 * // This is BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *     public int Get(int row, int col) {}
 *     public IList<int> Dimensions() {}
 * }
 */

class Solution {
    public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        var mat = binaryMatrix;
        var rows = mat.Dimensions()[0];
        var cols = mat.Dimensions()[1];
        
        var row = 0;
        var col = cols-1;
        
        while(row < rows){
            while(col >= 0 && mat.Get(row, col) == 1){
                if (col-- == 0)
                    break;
            }
            row++;
        }
        
        return col == cols-1 ? -1 : col+1;
    }
}<file_sep>public class Solution {
    public int Reverse(int x) {
        long result = 0;
        var sign = x < 0 ? -1 : 1;
        x *= sign;
        
        while(x > 0){
            result *= 10;                        
            result += x % 10;
            x /= 10;    
            if (result > int.MaxValue)
                return 0;
        }
        
        return (int)result*sign;
    }
}<file_sep>public class Solution {
    public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections) {
        var g = new IList<IList<int>>[n];

        foreach(var conn in connections){
            if(g[conn[0]] == null)
                g[conn[0]] = new List<IList<int>>();
            if(g[conn[1]] == null)
                g[conn[1]] = new List<IList<int>>();
            g[conn[0]].Add(conn);
            g[conn[1]].Add(conn);
        }

        var strongConnections = new HashSet<IList<int>>();
        var dfsRanks = new int[n];
        
        // to eliminate 1-1 = 0 on parent check
        DFS(g, strongConnections, dfsRanks, 2, 0);
        
        var res = new List<IList<int>>();
        foreach(var conn in connections)
            if(!strongConnections.Contains(conn))
                res.Add(conn);

        return res;
    }

    int DFS(IList<IList<int>>[] g, HashSet<IList<int>> conns, int[] ranks, int rank, int nodeIdx){
        if(ranks[nodeIdx] > 0)
            return ranks[nodeIdx];

        ranks[nodeIdx] = rank;
        var minDfsRank = rank;
        foreach(var nei in g[nodeIdx]){
            var neiIdx = nei[0] == nodeIdx ? nei[1] : nei[0];

            // parent
            if(ranks[neiIdx] == rank - 1)
                continue;

            var dfsRank = DFS(g, conns, ranks, rank+1, neiIdx);

            if(dfsRank <= rank)
                conns.Add(nei);

            minDfsRank = Math.Min(minDfsRank, dfsRank);
        }

        return minDfsRank;
    }
}<file_sep>public class Solution {
    public int MinDifficulty(int[] jobDifficulty, int d) {
        return jobDifficulty.Length >= d 
            ? DFS(jobDifficulty, 0, d, new int?[jobDifficulty.Length, d])
            : -1;
    }

    public int DFS(int[] jd, int idx, int remaining, int?[,] memo){
        if(memo[idx, remaining-1].HasValue)
            return memo[idx, remaining].Value;

        var max = int.MinValue;
        var res = int.MaxValue;
        for(int i = idx; i < jd.Length - remaining + 1; i++){
            max = Math.Max(max, jd[i]);
            res = remaining == 1 ? max : Math.Min(res, max + DFS(jd, i+1, remaining-1, memo));
        }
        
        memo[idx, remaining-1] = res;
        return res;
    }
}<file_sep>public class Solution {
    public int RangeBitwiseAnd(int m, int n) {
        if (m==0)
            return 0;
        
        var shift = 0;
        while (m != n){
            m >>= 1;            
            n >>= 1;

            shift++;
        }
        
        return m << shift;
    }
}<file_sep>public class Solution {
    public IList<IList<int>> Combine(int n, int k) {
        var res = new List<IList<int>>();
        Combine(1, 0, n, k, res, new int[k]);
        return res;
    }


    public void Combine(int cur, int pos, int n, int k, IList<IList<int>> res, int[] comb) {
        if(pos == k){
            var arr = new int[k];
            Array.Copy(comb, arr, k);
            res.Add(arr);
            return;
        }

        for(int i = cur; i <= n; i++){
            comb[pos] = i;
            Combine(i+1, pos+1, n, k, res, comb); 
        }
    }
}<file_sep>public class Logger {
    private const int n = 10;
    private ValueTuple<int, HashSet<string>>[] hist = new ValueTuple<int, HashSet<string>>[n];

    /** Initialize your data structure here. */
    public Logger() {
        for(int i = 0; i < n; i++)
          hist[i] = (i, new HashSet<string>());
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public bool ShouldPrintMessage(int timestamp, string message) {
        for(var i = 0; i < n; i++){
            (var hts, var hset) = hist[i];
            if(timestamp - hts < n && hset.Contains(message))
                return false;
        }
        
        (var ts, var set) = hist[timestamp % n];
        if(ts != timestamp)
            hist[timestamp % n] = (timestamp, set = new HashSet<string>());
        set.Add(message);
        
        return true;
    }
}

/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * bool param_1 = obj.ShouldPrintMessage(timestamp,message);
 */<file_sep>public class Solution {
    public int KConcatenationMaxSum(int[] arr, int k) {
        var res = 0L;
        var sum = 0L;
        var prev = 0L;
        var delta = 0L;
        var baseSum = 0L;
        
        for(int n = 0; n < 3; n++){
            for(int i = 0; i < arr.Length; i++){
                sum = Math.Max(sum+arr[i], arr[i]);
                res = Math.Max(res, sum);
            }
            
            if(prev >= res)
                return (int)(prev % (Math.Pow(10, 9) + 7));
                    
            if(n==0){
                baseSum = res;
            } else if(n == 1){
                delta = res-prev;
            } else if(n == 2){
                return (int)(((k-1)*delta+baseSum) % (Math.Pow(10, 9) + 7));
            }
            
            prev = res;
        }
        
        return 0;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public void Flatten(TreeNode root) {
        FlattenInternal(root);
    }

    /*
             1
        2        5
    3      4        6

    1 - 2 - 3 - 4 - 
    */

    public TreeNode FlattenInternal(TreeNode node) { //1 
        if(node == null) // false
            return node;

        var left = node.left; // 2 
        var right = node.right; // 5
        node.right = null;
        node.left = null;
        TreeNode lastSubtreeNode = node;

        // visit left subtree
        if(left != null){ // t
            lastSubtreeNode.right = left; 
            lastSubtreeNode = FlattenInternal(left); // 4
        }
        
        // visit right
        if(right != null){
            // contunie left subtree or curent node
            lastSubtreeNode.right = right;
            lastSubtreeNode = FlattenInternal(right); // 4
        }

        return lastSubtreeNode; // 4
    }
}<file_sep>public class Solution {
    public IList<string> WordsAbbreviation(IList<string> dict) {
        var map = new Dictionary<string, List<int>>();
        var n = dict.Count;
        var res = new string[n];
        
        for(int i=0; i<n; i++){
            var w = dict[i];
            if(w.Length < 4){
                res[i] = w;
                continue;
            }
            
            var key = Shorter(1, w);
            
            if(!map.ContainsKey(key))
                map[key] = new List<int>();
            
            map[key].Add(i);
        }
        
        foreach(var kv in map){
            if(kv.Value.Count == 1){
                var idx = kv.Value[0];
                res[idx] = kv.Key;
                continue;
            }
            
            var trie = new Trie();
            
            foreach(var idx in kv.Value){
                var w = dict[idx];
                var curr = trie;
                
                for(var i = 1; i < w.Length; i++){
                    var c = w[i]-'a';
                    curr.Count++;
                    curr = curr.Children[c] ?? (curr.Children[c] = new Trie());
                }
            }
            
            foreach(var idx in kv.Value){
                var w = dict[idx];
                var curr = trie;
                var i = 1;
                for(i = 1; i < w.Length && curr.Count > 1; i++)
                    curr = curr.Children[w[i]-'a'];
                res[idx] = Shorter(i, w);
            }
        }
        
        return res;
    }
    
    private string Shorter(int count, string str){
        if(count > str.Length-3)
            return str;
        return str.Substring(0, count) + (str.Length-count-1).ToString() + str[str.Length-1]; 
    }
    
    public class Trie{
        public Trie[] Children = new Trie[26];
        public int Count;
    }
}<file_sep>public class Solution {
    public int StrStr(string haystack, string needle) {
        if (needle == null || needle == string.Empty)
            return 0;

        var i = 0;
        var n = 0;
        
        while(n < needle.Length && i < haystack.Length){
            if(haystack[i]==needle[n]){
                n++;
                i++;
            }
            else if(n > 0){
                i -= (n-1);
                n = 0;               
            } else{
                i++;
            }          
        }       
        
        return n == needle.Length ? i-n : -1;
    }
}<file_sep>public class Solution {
    public IList<string> AddOperators(string num, int target) {
        var res = new List<string>();

        void DFS(string eq, int start, long eval, long mult) {
            if(start >= num.Length){
                if(eval == target)
                    res.Add(eq);
                return;
            }

            var n = 0L;
            var end = num[start] == '0' ? start + 1 : num.Length;
            for(int i = start; i < end; i++){
                n = n*10 + num[i]-'0';
                if(start == 0){
                    DFS(eq + n, i+1, n, n);
                }
                else{
                    DFS(eq + '+' + n, i+1, eval + n, n);
                    DFS(eq + '-' + n, i+1, eval - n, -n);
                    DFS(eq + '*' + n, i+1, eval - mult + mult * n, mult * n);
                }
            }
        }

        DFS("", 0 , 0, 0);
        return res;
    }
}<file_sep>public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var frq = new Dictionary<int, int>();
        foreach(var n in nums)
            if(frq.ContainsKey(n))
                frq[n]++;
            else
                frq[n] = 1;

        var arr = frq.Select(kv => new []{kv.Key, kv.Value}).ToArray();

        void swap(int a, int b){
            if(a == b)
                return;
            var t = arr[a];
            arr[a] = arr[b];
            arr[b] = t;
        }

        int partition(int lo, int hi){
            var pivot = arr[hi];

            for(int i = lo; i < hi; i++)
                if(arr[i][1] < pivot[1])
                    swap(i, lo++);

            swap(hi, lo);
            return lo;
        }

        var lo = 0;
        var hi = arr.Length - 1;
        while(hi >= lo){
            var mid = partition(lo, hi);
            if(mid == k)
                break;
            if(mid > k)
                hi = mid-1;
            else
                lo = mid+1;
        }

        var res = new int[k];
        for(int i = 0; i < k; i++)
            res[i] = arr[i][0];
        
        return res;
    }
}<file_sep>public class Solution {
    public int MaxScore(int[] cardPoints, int k) {
        var max = 0;
        var cp = cardPoints;
        var len = cp.Length;
        var lo = len - k;
        var hi = lo;
        var sum = 0;
        
        while(hi < len + k){
            if(hi-lo >= k){
                sum -= cp[lo % len];
                lo++;
            }
                
            sum += cp[hi % len];
            max = Math.Max(sum, max);
            hi++;
        }
        
        return max;
    }
}<file_sep>public class Solution {
    public int Trap(int[] height) {
        var n = height.Length;
        if(n < 3)
            return 0;
        
        var lo = 0;
        var hi = n-1;
        var loMax = height[lo];
        var hiMax = height[hi];
        var res = 0;
        
        while(lo < hi-1){
            if(loMax <= hiMax){
                var curr = height[++lo];
                if(curr < loMax)
                    res += loMax - curr;
                else
                    loMax = curr; // !!!
            } else{
                var curr = height[--hi];
                if(curr < hiMax)
                    res += hiMax - curr;
                else
                    hiMax = curr;  // !!!
            }
        }
        
        return res;
    }
}<file_sep>public class Solution {
    public int NumSubmat(int[][] mat) {
        int rows = mat.Length, cols = mat[0].Length;
        int res = 0;
        
        for (int up = 0; up < rows; ++up) {
                int[] h = Enumerable.Repeat(1, cols).ToArray();
                for (int down = up; down < rows; ++down) {
                    
                    for (int k = 0; k < cols; ++k) 
                        h[k] &= mat[down][k];
                    
                    var curr = countOneRow(h);
                    if(curr == 0)
                        break;
                    
                    res += countOneRow(h);
                }
            }

            return res;
        }

        private int countOneRow(int[] A) {
            int res = 0, length = 0;
            for (int i = 0; i < A.Length; ++i) {
                length = (A[i] == 0 ? 0 : length + 1);
                res += length;
            }
            return res;
        }
    }
<file_sep>public class MovingAverage {
    LinkedList<int> data;
    int size;
    long sum;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        data = new LinkedList<int>();
        this.size = size;
    }
    
    public double Next(int val) {
        if(data.Count >= size){
            var stale = data.First.Value;
            data.RemoveFirst();
            sum -= stale;
        }
        sum += val;
        data.AddLast(val);
        return sum/(double)data.Count;
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.Next(val);
 */<file_sep>public class Solution {
    public IList<IList<string>> FindDuplicate(string[] paths) {
        var map = new Dictionary<string, List<string>>();
        foreach(var path in paths){
            var infos = path.Split(" ");
            if(infos.Length <= 1)
                continue;
            var dir = infos[0];
            foreach(var file in infos.Skip(1)){
                var fileInfo = file.Split("(");
                var name = dir + "/" + fileInfo[0];
                var content = fileInfo[1];
                if(map.ContainsKey(content)){
                    map[content].Add(name);
                } else{
                    map[content] = new List<string>{name};
                }
            }
        }
        return map
            .Where(kv => kv.Value.Count > 1)
            .Select(kv => (IList<string>)kv.Value)
            .ToList();
    }
}<file_sep>public class Solution {
    public int[][] Multiply(int[][] A, int[][] B) {
        var rows = A.Length;
        var cols = A[0].Length;
        var colsB = B[0].Length;
        var res = new int[rows][];

        // keep values of B != 0
        // below it woulb the subject of the repetitive iterations
        var helper = new List<(int, int)>[B.Length];
        for(int r = 0; r < B.Length; r++){
            helper[r] = new List<(int, int)>();
            for(int c = 0; c < colsB; c++){
                if(B[r][c] != 0)
                    helper[r].Add((c, B[r][c])); 
            }
        }

        
        for(int r = 0; r < rows; r++){
            res[r] = new int[colsB];
            for(int c = 0; c < cols; c++){
                var a = A[r][c];
                if(a != 0)
                    foreach(var (idx, val) in helper[c])
                        res[r][idx] += a * val; 
            }
        }

        return res;
    }
}<file_sep>public class NumMatrix {
    private int[,] m;

    public NumMatrix(int[][] matrix) {
        var rows = matrix.Length;
        var cols = matrix[0].Length;

        m = new int[rows, cols];
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                m[i,j] = matrix[i][j] + (j == 0 ? 0 : m[i, j-1]);
    }
    
    public int SumRegion(int row1, int col1, int row2, int col2) {
        var sum = 0;
        for(int r = row1; r <= row2; r++){
            sum += m[r,col2] - (col1 == 0 ? 0 : m[r,col1-1]);
        }

        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.SumRegion(row1,col1,row2,col2);
 */<file_sep>public class Solution {
    public int MinSubArrayLen(int s, int[] nums) {
        var lo = 0;
        var hi = 0;
        var sum = 0;
        var res = int.MaxValue;
        while(hi < nums.Length){
            while(hi < nums.Length && sum < s){
                sum += nums[hi++];
            }
            while(sum >= s && lo <= hi && lo < nums.Length){
                res = Math.Min(res, hi - lo);
                sum -= nums[lo++];
            }
        }
        return res == int.MaxValue ? 0 : res;
    }
}<file_sep>public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int n = nums.Length;
    
        // 1. mark numbers (num < 0) and (num > n) with a special marker number (n+1) 
        // (we can ignore those because if all number are > n then we'll simply return 1)
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        // note: all number in the array are now positive, and on the range 1..n+1
        
        // 2. mark each cell appearing in the array, by converting the index for that number to negative
        for (int i = 0; i < n; i++) {
            int num = Math.Abs(nums[i]);
            if (num > n) {
                continue;
            }
            num--; // -1 for zero index based array (so the number 1 will be at pos 0)
            if (nums[num] > 0) { // prevents double negative operations
                nums[num] *= -1;
            }
        }
        
        // 3. find the first cell which isn't negative (doesn't appear in the array)
        for (int i = 0; i < n; i++) {
            if (nums[i] >= 0) {
                return i + 1;
            }
        }
        
        // 4. no positive numbers were found, which means the array contains all numbers 1..n
        return n + 1;    
    }
}<file_sep>public class Solution {
    public int NumTrees(int n) {
        if(n == 0)
            return 0;
        
        N = n;
        
        return NumTrees(1, n);
    }
    
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    private int N = 0;
    
    public int NumTrees(int start, int end) {
        var count = 0;
        
        if (start > end){
            return 1;
        }
        
        var key = start*N+end;
        if(memo.TryGetValue(key, out var res))
            return res;
        
        for(int i = start; i <= end; i++){
            var lTrees = NumTrees(start, i-1);
            var rTrees = NumTrees(i+1, end);
            
            count += lTrees * rTrees;
        }
        
        memo[key] = count;
        
        return count;
    }
}<file_sep>public class Solution {
    public string AlphabetBoardPath(string target) {
        var sb = new List<char>();
        var x = 0;
        var y = 0;
        foreach(var c in target){
            var xt = (c - 'a') % 5;
            var yt = (c - 'a') / 5;
            while(y > yt){
                sb.Add('U');
                y--;
            }

            while(x > xt){
                sb.Add('L');
                x--;
            }
            while(x < xt){
                sb.Add('R');
                x++;
            }
            while(y < yt){
                sb.Add('D');
                y++;
            }
            sb.Add('!');
        }
        
        return new String(sb.ToArray());
    }
}<file_sep>public class Solution {
    public void Rotate(int[][] matrix) {
        if (matrix == null || matrix.Length <= 1)
            return;
        
        var rank = matrix.Length;
        
        for(var i=0; i < rank; i++){
            for(var j=i; j < rank; j++){
                var t = matrix[j][i];
                matrix[j][i] = matrix[i][j];
                matrix[i][j] = t;
            }
        }   
        
        for(var i=0; i < rank; i++){
            for(var j=0; j < rank/2; j++){
                var t = matrix[i][j];
                matrix[i][j] = matrix[i][rank-j-1];
                matrix[i][rank-j-1] = t;
            }
        }
    }
}<file_sep>public class Solution {
    public int MissingElement(int[] nums, int k) {
        int missing(int idx) {
            return nums[idx] - nums[0] - idx;
        }
        
        var n = nums.Length;
        var diff = missing(n-1);
        
        if(diff < k){
            return nums[n-1]+k-diff; 
        }
        
        var lo = 0;
        var hi = n-1;
        while(hi != lo){
            var mid = lo + (hi-lo)/2;
            diff = missing(mid);
            if(diff < k){
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return nums[hi - 1] + k - missing(hi-1);
    }
}<file_sep>public class Solution {
    public int MinSumOfLengths(int[] arr, int target) {
        var n = arr.Length;
        // Optimization: it is not required to populate this array
        var best = new int[n];
        var bestSoFar = int.MaxValue;
        var sum = 0;
        var start = 0;
        var res = int.MaxValue;
    
        for(var i = 0; i < n; i++){
            sum += arr[i];
            
            while(sum > target && start < n){
                sum -= arr[start++];
            }
            
            if(sum == target){
                var currLen = i-start+1;
                bestSoFar = Math.Min(bestSoFar, currLen);
                
                if(start > 0 && best[start-1] != int.MaxValue)
                    res = Math.Min(res, best[start-1] + currLen);
                
                // Optimization: minimum possible length is 2
                if(res == 2)
                    return res;
            }
            
            best[i] = bestSoFar;
        }
        
        return res == int.MaxValue ? -1 : res;
    }
}<file_sep>public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        var ptr = 0;
        var n = pushed.Length;
        var stack = new Stack<int>();
        
        foreach(var pu in pushed){
            stack.Push(pu);
            
            while(stack.Any() && ptr < n && stack.Peek() == popped[ptr]){
                stack.Pop();
                ptr++;
            }
        }
        
        return !stack.Any();
    }
}<file_sep>public class RangeModule {
    List<ValueTuple<int,int>> data;
    
    public RangeModule() {
        data = new List<ValueTuple<int,int>>();
        // dirty hack for binary searxh simplification
        data.Add((int.MinValue, int.MinValue));
        data.Add((int.MaxValue, int.MaxValue));
    }
    
    public void AddRange(int left, int right) {
        var next = FindNext(left);
        
        while(next < data.Count){
            (var start, var end) = data[next];
            if(start > right)
                break;
            
            left = Math.Min(left, start);
            right = Math.Max(right, end);
            data.RemoveAt(next);
        }
        data.Insert(next, (left, right));
    }
    
    public bool QueryRange(int left, int right) {
        (var start, var end) = data[FindNext(left)];
        return start <= left && end >= right;
    }
    
    public void RemoveRange(int left, int right) {
        var next = FindNext(left);
        var temp = new List<ValueTuple<int,int>>();
        
        while(next < data.Count){
            (var start, var end) = data[next];
            if(start > right)
                break;
            
            if(start < left)
                temp.Add((start, left));
            if(end > right)
                temp.Add((right, end));
            
            data.RemoveAt(next);
        }
        
        for(var i = temp.Count-1; i >= 0; i--)
            data.Insert(next, temp[i]);
    }
    
    private int FindNext(int left){
        var lo = 0;
        var hi = data.Count-1;
        while(lo < hi){
            var mid = lo + (hi - lo)/2;
            (_, var nextRight) = data[mid];
            if(left == nextRight)
                return mid;
            
            if(left < nextRight)
                hi = mid;
            else
                lo = mid+1;
        }
        
        return hi;
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.AddRange(left,right);
 * bool param_2 = obj.QueryRange(left,right);
 * obj.RemoveRange(left,right);
 */<file_sep>public class Solution {
    public int AssignBikes(int[][] workers, int[][] bikes) {
        var memo = new Dictionary<ValueTuple<int,int>, int>();
        
        int DFS(int w, int taken){
            if(w == workers.Length)
                return 0;
            
            var key = (w,taken);
            if(memo.ContainsKey(key))
                return memo[key];
            
            var min = int.MaxValue;
            for(var b = 0; b < bikes.Length; b++){
                if((taken & (1<<b)) > 0)
                    continue;
                
                var dist = Math.Abs(workers[w][0]-bikes[b][0]) + Math.Abs(workers[w][1]-bikes[b][1]);
                min = Math.Min(min, DFS(w+1, (taken | (1<<b)))+dist);
            }
            
            memo[key] = min;
            return min;
        }
        
        return DFS(0, 0);
    }
}<file_sep>public class Solution {
    public int MinMeetingRooms(int[][] intervals) {
        var n = intervals.Length;
        if(n < 2)
            return n;

        Array.Sort(intervals, new CompareStart());
        var rooms = new SortedSet<(int, int)>(new CompareEnd());

        for(int i=0; i <n ; i++){
            var meet = intervals[i];
            if(rooms.Any()){
                var room = rooms.First();
                var isFree = room.Item1 <= meet[0];
                //Console.WriteLine(room.Item1 + " " + meet[0] + " " + isFree);
                if(isFree)
                    rooms.Remove(room);
            }
            rooms.Add((meet[1], i));
        }

        return rooms.Count;
    }

    class CompareStart : IComparer<int[]>{
        public int Compare(int[] a, int[] b){
            return a[0]-b[0];
        }
    }

    class CompareEnd : IComparer<(int, int)>{
        public int Compare((int, int) a, (int, int) b){
            var dif = a.Item1 - b.Item1;
            return dif != 0 ? dif : a.Item2-b.Item2;
        }
    }
}<file_sep>public class Solution {
    public int ThirdMax(int[] nums) {
        var dq = new int?[3];
        for(int i = 0; i < nums.Length; i++){
            var n = nums[i];
            if((dq[2] == null || n > dq[2]) && dq[1] != n && dq[0] != n){
                dq[2] = n;
                var j = 2;
                while(j > 0 && (dq[j-1] == null || dq[j] > dq[j-1])){
                    var t = dq[j];
                    dq[j] = dq[j-1];
                    dq[j-1] = t;
                    j--;
                }
            }
        }

        return dq[2] != null ? dq[2].Value : dq[0].Value;
    }
}<file_sep>public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        if(wordDict?.Count == 0)
            return false;

        var n = s.Length;
        var set = new HashSet<string>(wordDict);
        var memo = new bool[n+1];
        memo[0] = true;

        for(int i = 1; i<= n; i++){
            for(int j = i-1; j >=0; j--){
                if(memo[j] && set.Contains(s.Substring(j, i-j))){
                    memo[i] = true;
                    break;
                }
            }
        }

        return memo[n];
    }

    public bool WordBreak(string s, IList<string> wordDict) {
        if(wordDict?.Count == 0)
            return false;

        var n = s.Length;
        var set = new HashSet<string>(wordDict);
        var memo = new bool?[n];

        bool CheckSubstring(int start){
            if (start >= n)
                return true;

            if(memo[start] != null)
                return memo[start].Value;

            for (int end = start + 1; end <= n; end++) {
                var str = s.Substring(start, end-start);
                if(set.Contains(str) && CheckSubstring(end)){
                    memo[start] = true;
                    return true;
                }
            }

            memo[start] = false;
            return false;
        }

        return CheckSubstring(0);
    }
}<file_sep>public class Solution {
    public int CherryPickup(int[][] grid) {
        var rows = grid.Length;
        var cols = grid[0].Length;
        var dp = new int[rows, cols, cols];
        
        for(var r = rows-1; r >= 0; r--){
            for(var c1 = 0; c1 < cols; c1++){
                for(var c2 = 0; c2 < cols; c2++){
                    var val = c1 == c2 ? grid[r][c1] : grid[r][c1] + grid[r][c2];
                    var max = 0;
                    
                    if(r != rows-1)
                        for(var i=c1-1; i<=c1+1; i++)
                            for(var j=c2-1; j<=c2+1; j++)
                                if(i >= 0 && j>=0 && i <cols && j< cols)
                                    max = Math.Max(max, dp[r+1,i,j]);
                    
                    dp[r,c1,c2] = val+max;
                }
            }
        }
        
        return dp[0,0,cols-1];
    }
}<file_sep>public class Solution
    {
        public TreeNode BstFromPreorder(int[] preorder)
        {
            var index = 0;
            return InsertValue(null, ref index, preorder);
        }

        public TreeNode InsertValue(int? max, ref int i, int[] arr)
        {
            if (i >= arr.Length || (max != null && arr[i] > max))
                return null;

            var node = new TreeNode(arr[i]);
            i += 1;

            node.left = InsertValue(arr[i-1], ref i, arr);
            node.right = InsertValue(max, ref i, arr);

            return node;
        }
    }<file_sep>public class RandomizedSet {
    private Dictionary<int,int> map = new Dictionary<int, int>();
    private List<int> list = new List<int>();
    private Random rand = new Random();
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public bool Insert(int val) {
        if(map.ContainsKey(val))
            return false;
        
        list.Add(val);
        map[val] = list.Count-1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public bool Remove(int val) {
        if(!map.ContainsKey(val))
            return false;
        
        var idx = map[val];
        if (list.Count-1 != idx){ // element is already at the end
            list[idx] = list[list.Count-1];
            map[list[idx]] = idx;
        }
        
        list.RemoveAt(list.Count-1);
        map.Remove(val);
        return true;
    }
    
    /** Get a random element from the set. */
    public int GetRandom() {
        var idx = rand.Next(0,list.Count);
        return list[idx];
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.Insert(val);
 * bool param_2 = obj.Remove(val);
 * int param_3 = obj.GetRandom();
 */<file_sep>public class Solution {
    
    private int[] prefixSums;
    private int totalSum;
    private Random rand;

    public Solution(int[] w) {
        prefixSums = new int[w.Length];
        for (int i = 0; i < w.Length; ++i) {
            totalSum += w[i];
            prefixSums[i] = totalSum;
        }
        rand = new Random(totalSum);
    }
    
    public int PickIndex() {
        double target = totalSum * rand.NextDouble();
        
        var low = 0;
        var high = prefixSums.Length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (target > prefixSums[mid])
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.PickIndex();
 */<file_sep>public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        var rows = isConnected.Length;
        if(rows == 0) return 0;
        var cols = isConnected[0].Length;
        var visited = new HashSet<int>();
        var q = new Queue<int>();
        var res = 0;
        
        for(int r = 0; r < rows; r++){
            if(visited.Contains(r))
                continue;

            visited.Add(r);
            q.Enqueue(r);
            
            while(q.Any()){
                var city = q.Dequeue();
                for(int c = 0; c < cols; c++){
                    if(isConnected[city][c] == 1 && !visited.Contains(c)){
                        visited.Add(c);
                        q.Enqueue(c);
                    }
                }
            }
            res++;
        }

        return res;
    }
}<file_sep>public class Solution {
    public int MinReorder(int n, int[][] connections) {
        var nei = new List<int>[n];
        var res = 0;
        
        for(int i = 0; i < n; i++)
            nei[i] = new List<int>();
        
        foreach(var con in connections){
            nei[con[0]].Add(con[1]+n); // from city to next
            nei[con[1]].Add(con[0]);
        }
        
        var q = new Queue<int>();
        q.Enqueue(0);
        var visited = new HashSet<int>();
        visited.Add(0);
        
        while(q.Any()){
            var city = q.Dequeue();
            
            foreach(var next in nei[city]){
                var nextCity = next >= n ? next-n : next;
                if(visited.Contains(nextCity))
                    continue;
                
                if(next >= n)
                    res++;

                q.Enqueue(nextCity);
                visited.Add(nextCity);
            }
        }
        
        return res;
    }
}


public class Solution {
    public int MinReorder(int n, int[][] connections) {
        var nei = new List<int>[n];
        
        foreach(var con in connections){
            if(nei[con[0]] == null)
                nei[con[0]] = new List<int>();
            if(nei[con[1]] == null)
                nei[con[1]] = new List<int>();
            
            nei[con[0]].Add(con[1]+n);
            nei[con[1]].Add(con[0]);
        }
        
        return FixDirection(0, nei, n, int.MinValue);
    }
    
    private int FixDirection(int city, List<int>[] nei, int max, int prevCity){
        var res = 0;
        
        for(int j = 0; j < nei[city].Count; j++){
            var n = nei[city][j];
            
            if(n == prevCity || n-max == prevCity)
                continue;
            
            if(n >= max){
                n -= max;
                res++;
            }
            
            res += FixDirection(n, nei, max, city);
        }
        
        return res;
    }
}<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        
        if (head == null || head.next == null)
            return true;
        
        var slow = head;
        var fast = head;
        
        var history = new Stack<int>();
        
        while(fast != null && fast.next != null){
            history.Push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        
        if (fast != null)
            slow = slow.next;
        
        while(history.Any()){
            if (history.Pop() != slow.val)
                return false;
            
            slow = slow.next;
        }
        
        return true;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    /*
         0
       1    2
          3
    
    */
    public IList<IList<int>> VerticalOrder(TreeNode root) {
        var res = new List<IList<int>>();
        if(root == null)
            return res;

        var map = new Dictionary<int, List<int>>(); // 0;03 -1;1 1;2 
        var q = new Queue<(TreeNode, int)>();

        q.Enqueue((root, 0)); // 2;1

        var max = 0; 
        var min = 0;  

        while(q.Any()){
            var (node, level) = q.Dequeue(); // 3;0
            if(node == null) //f
                continue;
            
            if(!map.ContainsKey(level)) // f
                map[level] = new List<int>();
            map[level].Add(node.val); 

            max = Math.Max(max, level); // 0
            min = Math.Min(min, level); // -1

            q.Enqueue((node.left, level-1));
            q.Enqueue((node.right, level+1));
        }

        for(int i = min; i <=max; i++){
            res.Add(map[i]);
        }

        return res;
    }
}<file_sep>public class Solution {
    public int DiameterOfBinaryTree(TreeNode root) {
        int diameter = 0;
        DiameterOfBinaryTree(root, ref diameter);
        return diameter > 0 ? diameter-1 : 0;
    }

    public int DiameterOfBinaryTree(TreeNode node, ref int diameter) {
        if(node == null)
            return 0;

        var diameterLeft = DiameterOfBinaryTree(node.left, ref diameter);
        var diameterRight = DiameterOfBinaryTree(node.right, ref diameter);
        diameter = Math.Max(diameter, diameterLeft+diameterRight+1);

        return Math.Max(diameterLeft, diameterRight)+1;
    }
}<file_sep>public class Solution {
    public int MaxProfit(int[] inventory, int orders) {
        var n = inventory.Length;
        Array.Sort(inventory);
        long res = 0;
        long max = inventory[n-1];

        for(int i = n-2; i >= -1; i--){
            long cur = i != -1 ? inventory[i] : 0;

            if(cur == max)
                continue;

            long available = n-1-i;

            if(available * (max-cur) <= orders){
                orders -= (int)(available * (max-cur));
                res += ((max*max+max)/2 - (cur*cur+cur)/2)*available;
                max = cur;
            } else {
                while(max > cur && orders > 0){
                    var count = Math.Min(available, orders);
                    orders -= (int)count;

                    res += max * count;
                    max--;
                }
            }
        }

        return (int)(res % 1000000007);
    }
}<file_sep>public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        var q = new Heap(k+1);
        
        foreach(var n in nums){
            q.Add(n);
            if(q.len > k)
                q.Pool();
        }
        
        return q.Peek();
    }
}

public class Heap{
    public int len;
    int[] arr;
    
    public Heap(int cap){
        arr = new int[cap];
    }
    
    public int Peek(){
        return arr[0];
    }
    
    public void Pool(){
        arr[0] = arr[len-1];
        len--;
        HeapifyDown();
    }
    
    public void Add(int val){
        arr[len] = val;
        len++;
        HeapifyUp();
    }
    
    int left(int idx) {return idx*2+1;}
    int right(int idx) {return idx*2+2;}
    int parent(int idx) {return (idx-1)/2;}
    
    private void HeapifyDown(){
        var idx = 0;
        
        while(left(idx) < len){
            var childIdx = left(idx);
            if(right(idx) < len && arr[right(idx)] < arr[childIdx])
                childIdx = right(idx);
            
            if(arr[childIdx] > arr[idx])
                break;
            
            swap(idx, childIdx);
            idx = childIdx;
        }
    }    
    
    private void HeapifyUp(){
        var idx = len - 1;
        
        while(idx > 0){
            if(arr[parent(idx)] < arr[idx])
                break;
                
            swap(idx, parent(idx));
            idx = parent(idx);
        } 
    }
    
    void swap(int a, int b){
        var temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}





<file_sep>public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<TreeNode>();

    public BSTIterator(TreeNode root) {
        TraverseLeft(root);
    }
    
    public int Next() {
        node = stack.Pop();
        TraverseLeft(node.right);
        return node.val;
    }
    
    public bool HasNext() {
        return stack.Any();
    }

    private void TraverseLeft(TreeNode node){
        while(node != null){
            stack.Push(node);
            node = node.left;
        }
    }
}
<file_sep>public class Solution {
    public int MinimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        var n = source.Length;
        var dsu = new DSU(n);

        foreach(var sw in allowedSwaps)
            dsu.Union(sw[0], sw[1]);

        var map = new Dictionary<int, List<int>>();

        for(int i = 0; i < n; i++){
            var p = dsu.Find(i);
            if(!map.ContainsKey(p))
                map[p] = new List<int>();

            map[p].Add(i);
        }
        
        var res = 0;

        foreach(var indexes in map.Values){
            var targetMap = new Dictionary<int, int>();

            foreach(var idx in indexes){
                var val = target[idx];
                if(!targetMap.ContainsKey(val))
                    targetMap[val] = 1;
                else   
                    targetMap[val]++;
            }

            foreach(var idx in indexes){
                var val = source[idx];
                if(targetMap.ContainsKey(val)){
                    targetMap[val]--;
                    if(targetMap[val] < 0)
                        res++;
                }
                else{
                    res++;
                }
            }
        }

        return res;
    }

    private class DSU{
        private int[] arr;

        public DSU(int n){
            arr = Enumerable.Range(0, n).ToArray();
        }

        public void Union(int a, int b){
            var pa = Find(a);
            var pb = Find(b);
            arr[pa] = pb;
        }

        public int Find(int a){
            if(arr[a] == a)
                return a;

            return Find(arr[a]);
        }
    }
}<file_sep>public class Solution {
    public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        var maxh = 0;
        var maxv = 0;

        horizontalCuts.Sort();
        verticalCuts.Sort();

        for(int i = 0; i <= horizontalCuts.Length; i++){
            var prev = i == 0 ? 0 : horizontalCuts[i-1];
            var next = i == horizontalCuts.Length ? h : horizontalCuts[i];

            maxh = Math.Max(maxh, next-prev);
        }

        for(int i = 0; i <= verticalCuts.Length; i++){
            var prev = i == 0 ? 0 : verticalCuts[i-1];
            var next = i == verticalCuts.Length ? w : verticalCuts[i];

            maxv = Math.Max(maxv, next-prev);
        }

        maxh = maxh == 0 ? h : maxh;
        maxv = maxv == 0 ? w : maxv;

        long res = (long)maxh * (long)maxv;

        return (int)(res % 1000000007);
    }
}<file_sep>public class Solution {
    public void Rotate(int[] nums, int k) {
        var n = nums.Length;
        var count =0;
        
        for(int start =0; count < n; start++){
            var idx = start;
            var memo = nums[idx];
            
            do{
                var pos= (idx+k)%n;
                var t = nums[pos];
                nums[pos] = memo;
                memo = t;
                idx = pos;

                count++;
            } while(idx != start);
        }
    }
}<file_sep>public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        var n = gas.Length;
        
        var total = 0;
        var curr = 0;
        var station = 0;
        
        for(int i = 0; i < n; i++){
            var balance = gas[i] - cost[i];
            total += balance;
            curr += balance;
            
            if(curr < 0){
                curr = 0;
                station = i+1;
            }
        }
        
        return total < 0 ? -1 : station;
    }
}<file_sep>public class Solution {
    public int LargestRectangleArea(int[] heights) {
        var st = new Stack<int>();
        st.Push(-1);
        var len = heights.Length;
        var max = 0;

        for(int i = 0; i < len; i++){
            var h = heights[i];
            while(st.Peek() > -1 && heights[st.Peek()] > h){
                var prevIdx = st.Pop();
                var prevVal = heights[prevIdx];

                var square = prevVal * (i - 1 - st.Peek());
                max = Math.Max(max, square);
            }
            st.Push(i);
        }

        while(st.Peek() > -1){
            var prevIdx = st.Pop();
            var prevVal = heights[prevIdx];

            var square = prevVal * (len - 1 - st.Peek());
            max = Math.Max(max, square);
        }

        return max;
    }
}<file_sep>public class Solution {
    private int rows;
    private int cols;
    public int MaxAreaOfIsland(int[][] grid) {
        rows = grid.Length;
        cols = grid[0].Length;
        var res = 0;
        
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(grid[i][j] == 1){
                    res = Math.Max(res, BFS(i, j, grid));
                }
            }
        }
        
        return res;
    }
    
    private int BFS(int row, int col, int[][] grid){
        var res = 0;
        var q = new Queue<ValueTuple<int, int>>();
        q.Enqueue((row, col));
        grid[row][col] = -1;
        
        while(q.Any()){
            (var r, var c) = q.Dequeue();
            res++;
            foreach((var rd, var cd) in Directions){
                var nr = r+rd;
                var nc = c+cd;
                if(nr>=0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1){
                    q.Enqueue((nr, nc));
                    grid[nr][nc] = -1;
                }
            }
        }
        return res;
    }
    
    private ValueTuple<int,int>[] Directions = new []{(1,0),(-1,0),(0,1),(0,-1)};
}<file_sep>public class Solution {
    public int TotalFruit(int[] tree) {
        
        var lo = 0;
        var hi = 0;
        var max = int.MinValue;
        
        var map = new Dictionary<int, int>();
        
        while(hi<tree.Length){
            
            map[tree[hi]] = hi;           
            
            if(map.Count == 3){
                var minIdx = map.Min(kv => kv.Value);
                map.Remove(map.First(kv => kv.Value == minIdx).Key);
                
                lo = minIdx + 1;
            } else if(hi-lo+1 > max){
                max = hi - lo+1;
            }
            
            hi++;
        }
        
        return max;
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var res = new List<IList<int>>();
        if(root == null)
            return res;
        
        var prev = new Stack<TreeNode>();
        prev.Push(root);
        res.Add(new List<int>{root.val});
        var forward = false;

        while(prev.Any()){
            var cur = new Stack<TreeNode>();
            var level = new List<int>();

            void AddNode(TreeNode n){
                if(n != null){
                    level.Add(n.val);
                    cur.Push(n);
                }
            }
            
            for(int count = prev.Count; count > 0; count--){
                var node = prev.Pop();
                if(forward){
                    AddNode(node.left);
                    AddNode(node.right);
                } else {
                    AddNode(node.right);
                    AddNode(node.left);
                }
            }

            prev = cur;
            if(level.Any())
                res.Add(level);
            forward = !forward;
        }

        return res;
    }
}<file_sep>public class Solution {
    public bool IsAlienSorted(string[] words, string order) {
        var comparer = new AlienComparer(order);
        
        for(int i = 1; i < words.Length; i++){
            if(comparer.Compare(words[i-1], words[i]) > 0)
                return false;
        }

        return true;
    }

    public class AlienComparer: IComparer<string>{
        private Dictionary<char, int> order;

        public AlienComparer(string order){
            this.order = new Dictionary<char, int>();
            for(int i = 0; i < order.Length; i++)
                this.order[order[i]] = i;
        }

        public int Compare(string a, string b){
            var len = Math.Min(a.Length, b.Length);
            for(int i = 0; i < len; i++){
                var c1 = order[a[i]];
                var c2 = order[b[i]];
                if(c1 != c2)
                    return c1 - c2;
            }

            return a.Length-b.Length;
        }
    }
}<file_sep>public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        var res = new int[nums.Length-k+1];
        var dq = new LinkedList<int>();

        for(int i = 0; i < nums.Length; i++){
            var n = nums[i];

            // remove max if it out of window 
            if(dq.Any() && dq.First.Value == i-k)
                dq.RemoveFirst();

            // keep decreasing order of the dequeue
            while(dq.Any() && nums[dq.Last.Value] <= n)
                dq.RemoveLast();

            dq.AddLast(i);

            if(i-k+1 >= 0)
                res[i-k+1] = nums[dq.First.Value];
        }

        return res;
    }
}<file_sep>public class LRUCache {
    private int cap;
    private Dictionary<int, LinkedListNode<ValueTuple<int,int>>> map = new Dictionary<int, LinkedListNode<ValueTuple<int,int>>>();
    private LinkedList<ValueTuple<int,int>> history = new LinkedList<ValueTuple<int,int>>();
    
    public LRUCache(int capacity) {
        cap = capacity;
    }
    
    public int Get(int key) {
        if(map.TryGetValue(key, out var node)){
            history.Remove(node);
            history.AddLast(node);
            return node.Value.Item2;
        }
        return -1;
    }
    
    public void Put(int key, int value) {
        var containsKey = map.ContainsKey(key);
        
        if(!containsKey && map.Count == cap){
            var evicted = history.First;
            history.Remove(evicted);
            map.Remove(evicted.Value.Item1);
        }
        
        if(containsKey){
            var node = map[key];
            node.Value = (key, value);
            history.Remove(node);
            history.AddLast(node);
        } else{
            history.AddLast((key, value));
            map[key] = history.Last;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.Get(key);
 * obj.Put(key,value);
 */<file_sep>public class Solution {
    public int MinTransfers(int[][] transactions) {
        var balance = new Dictionary<int, int>();
        foreach(var t in transactions){
            if(!balance.ContainsKey(t[0]))
                balance[t[0]] = 0;
            if(!balance.ContainsKey(t[1]))
                balance[t[1]] = 0;
            
            balance[t[0]] += t[2];
            balance[t[1]] -= t[2];
        }
        
        var d = balance.Values.Where(v => v != 0).ToArray();
        var n = d.Length;
        
        if(n == 0)
            return 0;
        
        int rebalance(int p){
            while(p < n && d[p] == 0)
                p++;
            
            if(p == n)
                return 0;
            
            var count = int.MaxValue;
            for(var i = p+1; i < n; i++){
                if((d[p] > 0 && d[i] < 0) || (d[p] < 0 && d[i] > 0)){
                    d[i] += d[p];
                    count = Math.Min(count, rebalance(p+1)+1);
                    d[i] -= d[p];
                }
            }
            
            return count;
        }
        
        return rebalance(0);
    }
}<file_sep>public class SparseVector {

    Dictionary<int,int> v = new Dictionary<int, int>();
    
    public SparseVector(int[] nums) {
        for(var i = 0; i < nums.Length; i++){
            if(nums[i] != 0)
                v[i] = nums[i];
        }
    }
    
    // Return the dotProduct of two sparse vectors
    public int DotProduct(SparseVector vec) {
        if(vec.v.Count < v.Count)
            return vec.DotProduct(this);

        var res = 0;
        foreach(var kv in v){
            if(vec.v.TryGetValue(kv.Key, out var val))
                res += val * kv.val;
        }

        return res;
    }
}

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.DotProduct(v2);<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {

        ListNode prev = null;
        ListNode res = null;
        
        while(head != null && head.next != null){
            var second = head.next;
            var third = second.next;
            
            second.next = head;
            if(prev != null)
                prev.next = second;
            else
                res = second;
            
            prev = head;
            head = third;
        }
        
        if (prev != null)
            prev.next = head;
        
        return res;
    }
    
    /*public ListNode SwapPairs(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        var next = head.next;
        var memo = next.next;
        next.next = head;
        head.next = SwapPairs(memo);
        
        
        
        return next;
    }*/
}<file_sep>public class Solution {
    public string LongestPalindrome(string s) {
        var n = s.Length;
        var length = 1;
        var start = 0;
        for(var i = 1; i <= 2*n-1; i++){
            var idx = i/2.0;
            int lo = (int)idx; 
            int hi = idx == lo ? lo : lo+1;

            while(lo >= 0 && hi < n && s[lo] == s[hi]){
                var len = hi-lo+1;
                if(len > length){
                    start = lo;
                    length = len;
                }
                lo--;
                hi++;
            }
        }

        return s.Substring(start, length);
    }
}<file_sep>public class Solution {
    public void NextPermutation(int[] nums) {
        var n = nums.Length;
        var idx = n - 2;
        while(idx >= 0 && nums[idx] >= nums[idx+1])
            idx--;

        if(idx >= 0){
            var idx2 = n-1;
            while(nums[idx2] <= nums[idx])
                idx2--;

            var t = nums[idx];
            nums[idx] = nums[idx2];
            nums[idx2] = t;
        }
        
        idx++;
        Array.Reverse(nums, idx, n-idx);
        
        return;
    }
}<file_sep>public class AutocompleteSystem {

    TrieNode Trie;
    TrieNode Current;
    private StringBuilder sb;

    public AutocompleteSystem(string[] sentences, int[] times) {
        Trie = new TrieNode();

        for(int i = 0; i < sentences.Length; i++){
            AddSentence(sentences[i], times[i]);
        }

        Reset();
    }

    private void Reset(){
        Current = Trie;
        sb = new StringBuilder();
    }

    private int Idx(char c){
        return c == ' ' ? 26 : c-'a';
    }

    private void AddSentence(string str, int frq){
        var t = Trie;
        t.Frq[str] = frq;

        foreach(var c in str){
            if(t.Children[Idx(c)] == null)
                t.Children[Idx(c)] = new TrieNode();

            t = t.Children[Idx(c)];
            t.AddSentence(str, frq);
        }

    }

    public IList<string> Input(char c) {
        var res = new List<string>();
        if(c == '#'){
            var str = sb.ToString();
            var frq = Trie.Frq.ContainsKey(str) ? Trie.Frq[str]+1 : 1;
            AddSentence(str, frq);
            Reset();
            return res;
        }

        sb.Append(c);

        if(Current == null || Current.Children[Idx(c)] == null){
            Current = null;
            return res;
        }

        Current = Current.Children[Idx(c)];

        foreach(var bucket in Current.Hot){
            foreach(var s in bucket.Value){
                res.Add(s);
                if(res.Count == 3)
                    return res;
            }
        }

        return res;
    }

    class TrieNode{
        public TrieNode[] Children = new TrieNode[27];
        public Dictionary<string, int> Frq = new Dictionary<string, int>();
        public SortedDictionary<int, SortedSet<string>> Hot = new SortedDictionary<int, SortedSet<string>>(new ReverseComparer());

        public void AddSentence(string str, int frq){
            // remove from prev bucket
            if(Frq.ContainsKey(str)){
                var bucket = Frq[str];
                Hot[bucket].Remove(str);
            }

            Frq[str] = frq;

            if(Hot.ContainsKey(frq))
                Hot[frq].Add(str);
            else
                Hot[frq] = new SortedSet<string>{ str };
        }
    }

    class ReverseComparer : IComparer<int>{
        public int Compare(int a, int b){
            return b-a;
        }
    }
}

/**
 * Your AutocompleteSystem object will be instantiated and called as such:
 * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
 * IList<string> param_1 = obj.Input(c);
 */<file_sep>public class Solution {
    public string ReorganizeString(string S) {
        var n = S.Length;
        var a = 26;
        var frq = new int[a];
        
        if(n < 2)
            return S;
        
        foreach(var c in S){
            if (frq[c-'a'] == 0)
                frq[c-'a'] = c-'a';
            
            frq[c-'a'] += a;
        }
        
        Array.Sort(frq);
        var ptr = 0;
        var res = new char[n];
        
        for(int i = a-1; i >= 0; i--){
            var count = frq[i]/a;
            var c = frq[i] % a;
            
            if(count > (n+1)/2)
                return "";
            
            while(count-- > 0){
                res[ptr] = (char)(c + 'a');
                ptr = ptr < n-2 ? ptr+2 : 1;
            }
        }
        
        return new String(res.ToArray());
    }
}<file_sep>public class Solution {
    public int UniquePaths(int m, int n) {
        int Fact(int a){
            return a == 0 ? 1 : a * Fact(a-1);
        }
        
        return Fact(n+m-2)/(Fact(n-1)*Fact(m-1)); // (n chose k combinations)
    }
}<file_sep>public class Solution {

    // 
    public int MaxSubArrayLen(int[] nums, int k) {
        var map = new Dictionary<int, int>();
        var max = 0;
        var sum = 0;
        for(int i = 0; i < nums.Length; i++){
            sum += nums[i];
            if(sum == k){
                max = Math.Max(max, i+1);
            } else if(map.ContainsKey(sum-k)){
                max = Math.Max(max, i - map[sum-k]);
            }

            if(!map.ContainsKey(sum))
                map[sum] = i;
        }

        return max;
    }
}<file_sep>public class Solution {
    public int MaximizeSweetness(int[] sweetness, int K) {
        var n = sweetness.Length;
        var lo = 0;
        var hi = 0;
        for(int i =0; i < n; i++){
            lo = Math.Min(lo, sweetness[i]);
            hi += sweetness[i];
        }

        while(lo < hi){
            var mid = lo + (hi-lo)/2 + 1;
            var cuts = 0;
            var sum = 0;
            for(int i = 0; i < n; i++){
                sum += sweetness[i];
                if(sum >= mid){
                    sum = 0;
                    if(++cuts == K+1)
                        break;
                }
            }
            
            if(cuts < K+1)
                hi = mid-1;
            else
                lo = mid;
        }
        
        return lo;
    }
}<file_sep>public class Solution {
	public IList<string> MostVisitedPattern(string[] username, int[] timestamp, string[] website) {
            int len = username.Length;
            string[] orderedSites = website.Distinct().OrderBy(x => x).ToArray();
            int n = orderedSites.Length;
            Dictionary<string, int> siteOrder = new Dictionary<string, int>();
            for (int i = 0; i < n; i++) {
                siteOrder[orderedSites[i]] = i;
            }
            Dictionary<string, List<Tuple<int, int>>> dict = new Dictionary<string, List<Tuple<int, int>>>();
            for (int i = 0; i < len; i++) {
                if (!dict.ContainsKey(username[i])) {
                    dict[username[i]] = new List<Tuple<int, int>>();
                }
                dict[username[i]].Add(new Tuple<int, int>(timestamp[i], siteOrder[website[i]]));
            }
            int[] tab = new int[n * n * n];
            foreach (string key in dict.Keys) {
                int[] temp = dict[key].OrderBy(x => x.Item1).Select(x => x.Item2).ToArray();
                HashSet<int> visited = new HashSet<int>();
                for (int i = 0; i < temp.Length; i++) {
                    for(int j = i + 1; j < temp.Length; j++) {
                        for(int k = j + 1; k < temp.Length; k++) {
                            int t = ((temp[i] * n) + temp[j]) * n + temp[k];
                            if (!visited.Contains(t)) {
                                tab[t]++;
                                visited.Add(t);
                            }
                        }
                    }
                }
            }
            int max = 0;
            int res = 0;
            for (int i = 0; i < tab.Length; i++) {
                if (tab[i] > max) {
                    res = i;
                    max = tab[i];
                }
            }
            return new List<string> { orderedSites[res / (n * n)], orderedSites[(res % (n * n)) / n], orderedSites[res % n] };
        }
}<file_sep>public class Solution {
    public int MaxDistToClosest(int[] seats) {

        var max = -1;
        var firstOccupied = -1;
        var lastOccupied = -1;
        
        var i = 0;
        while(i < seats.Length){
            
            if(seats[i] == 1){
                if (firstOccupied == -1)
                    firstOccupied = i;
                
                lastOccupied = i;
            }
            
            var counter = 0;
            while(i < seats.Length && seats[i] == 0){
                counter++;
                i++;
            }
            
            if(counter > 0 && counter > max)
                max = counter;
            
            if(counter == 0)
                i++;
        }
        
        return Math.Max((int)Math.Floor((max+1)/2.0), Math.Max(firstOccupied, seats.Length-1-lastOccupied));
        
    }
}<file_sep>public class Solution {
    public int Rob(int[] nums) {
        var len = nums.Length;

        for(int i = 2; i < len; i++)
            nums[i] += Math.Max(i > 2 ? nums[i-3] : 0, nums[i-2]); // choose from 2 prev maximums

        return len < 2 ? nums[0] : Math.Max(nums[len-1], nums[len-2]);
    }
}

public class Solution {
    public int Rob(int[] nums) {
        var len = nums.Length;

        for(int i = 2; i < len; i++){
            var max = Math.Max(nums[i-2], nums[i-1]);
            for(int j = 0; j <= i-2; j++){
                max = Math.Max(max, nums[j]);
            } 
            nums[i] += max;
        }

        return len < 2 ? nums[0] : Math.Max(nums[len-1], nums[len-2]);
    }
}<file_sep>public class Solution {
    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        for(int i = 0; i < n; i++)
            if(informTime[i] > 0)
               calcManagerialLine(i, manager, informTime);
        
        return informTime.Max();
    }
    
    void calcManagerialLine(int id, int[] manager, int[] informTime){
        if(manager[id] != -1){
            calcManagerialLine(manager[id], manager, informTime);
            informTime[id] += informTime[manager[id]];
            manager[id] = -1;
        }
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int CountNodes(TreeNode root) {
        if (root == null)
            return 0;
        
        var n = root;        
        var d = 0;
        
        while(n.left != null){
            n = n.left;
            d++;
        }
        
        if (d == 0)
            return 1;
        
        var lo = 1;
        var hi = (int)Math.Pow(2, d)-1;
        
        
        while(lo <= hi){
            var mid = lo + (hi-lo)/2;
            
            if (Exists(root, mid, d))
                lo = mid+1;
            else
                hi = mid -1;
        }
        
        return (int)Math.Pow(2, d) - 1 + lo;
    }
    
    public bool Exists(TreeNode n, int t, int d){
        var lo = 0;
        var hi = (int)Math.Pow(2, d)-1;
        
        while(d > 0){
            var mid = lo+(hi-lo)/2;
            if (t>mid){
                lo = mid +1;
                n = n.right;
            } else {
                hi = mid-1;
                n = n.left;
            }
            d--;
        }
        
        return n != null;
    }
}<file_sep>public class Solution {
    public void ReverseString(char[] s) {
        var l = 0;
        var r = s.Length-1;
        
        while(r>l){
            var t = s[l];
            s[l] = s[r];
            s[r] = t;
            l++;
            r--;
        }
    }
}<file_sep>public class Trie {
    
    private Dictionary<char, Trie> Children = new Dictionary<char, Trie>();
    private bool EndOfWord = false;

    /** Initialize your data structure here. */
    public Trie() {
        
    }
    
    /** Inserts a word into the trie. */
    public void Insert(string word) {
        if(!string.IsNullOrEmpty(word))
            Insert(word.ToCharArray(), 0);
    }
    
    private void Insert(char[] word, int ptr){
        if(ptr == word.Length){
            EndOfWord = true;
            return;
        }        

        Trie child = null;
        
        if(!Children.TryGetValue(word[ptr], out child)){
            child = Children[word[ptr]] = new Trie();
        }
        
        child.Insert(word, ptr+1);
    }
    
    /** Returns if the word is in the trie. */
    public bool Search(string word) {
        if(!string.IsNullOrEmpty(word))
            return Search(word.ToCharArray(), 0, true);
        
        return false;
    }
    
    private bool Search(char[] word, int ptr, bool checkEnd) {
        if(word.Length == ptr){
            return checkEnd ? EndOfWord : true;
        }
        
        if(Children.TryGetValue(word[ptr], out var child)){
            return child.Search(word, ptr+1, checkEnd);
        }
        
        return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public bool StartsWith(string prefix) {
        if(!string.IsNullOrEmpty(prefix))
            return Search(prefix.ToCharArray(), 0, false);        
        
        return false;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.Insert(word);
 * bool param_2 = obj.Search(word);
 * bool param_3 = obj.StartsWith(prefix);
 */<file_sep>public class Solution {
    public int Jump(int[] nums) {
        var n = nums.Length;
        if(n <= 1)
            return 0;
        var curJump = nums[0];
        var nextJump = curJump;
        var res = 1;

        for(int i = 1; i < n; i++){
            if(curJump < i){
                curJump = nextJump;
                res++;
            }
            nextJump = Math.Max(nextJump, nums[i]+i);
        }

        return res;
    }
}<file_sep>public class Solution {
    public int LongestConsecutive(int[] nums) {
        var num_set = new HashSet<int>(nums);
        int longestStreak = 0;

        foreach (int num in num_set) {
            if (!num_set.Contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.Contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.Max(longestStreak, currentStreak);
            }
        }

        return longestStreak;  
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool FlipEquiv(TreeNode root1, TreeNode root2) {
        if(root1?.val != root2?.val){
            return false;
        }  
        
        if (root1 == null)
            return true;        
        
        return FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left) ||
            FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right);
    }
    
    
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        bool DFS(TreeNode node){
            if(node == null)
                return false;

            var l = DFS(node.left);
            var r = DFS(node.right);
            if(l && r || (node == p || node == q) && (r || l)){
                root = node;
                return false;
            }

            return node == p || node == q || r || l;
        }

        DFS(root);
        return root;
    }
}

/*
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        parent.put(root, null);
        stack.push(root);

        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }

        To find the lowest common ancestor, we need to find where is p and q and a way to track their ancestors. 
        A parent pointer for each node found is good for the job. After we found both p and q, we create a set of p's ancestors. 
        Then we travel through q's ancestors, the first one appears in p's is our answer.

        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }
}
*/<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        var preIdx = 0;
        var n = preorder.Length-1;

        var map = new Dictionary<int, int>();
        for(int i = 0; i <= n; i++)
            map[inorder[i]] = i;

        TreeNode buildTree(int lo, int hi){
            if(lo > hi)
                return null;

            var rootIdx = map[preorder[preIdx++]];
            var root = new TreeNode(inorder[rootIdx]);
            
            root.left = buildTree(lo, rootIdx-1);
            root.right = buildTree(rootIdx+1, hi);

            return root;
        }

        return buildTree(0, n);
    }
}<file_sep>public class Solution {
    public bool ValidPalindrome(string s) {
        var l = 0;
        var r = s.Length-1;
        
        if(IsPalindrome(s, ref l, ref r))
            return true;
        
        var l2 = l+1;
        var r2 = r-1;
        
        return IsPalindrome(s, ref l, ref r2) || IsPalindrome(s, ref l2, ref r);
    }

    bool IsPalindrome(string s, ref int l, ref int  r){
        while(r >= l){
            if(s[l] != s[r])
                return false;
            l++;
            r--;
        }

        return true;
    }
}<file_sep>public class Solution {
    public int MaxProfit(int[] prices) {
       int maxCurr = 0;
        int maxSoFar = 0;
        
        for(int i = 1; i < prices.Length; i++){
            maxCurr += prices[i] - prices[i-1];
            maxCurr = Math.Max(maxCurr,  prices[i] - prices[i-1]);
            maxSoFar = Math.Max(maxSoFar, maxCurr);
        }
        
        return maxSoFar;
    }

}<file_sep>public class Solution {
    public int ClosestValue(TreeNode root, double target) {
        var res = root.val;
        var delta = double.MaxValue;
        while(root != null){
            if((double)root.val == target)
                return root.val;

            var d = Math.Abs(root.val-target);
            if(d < delta){
                delta = d;
                res = root.val;
            }

            root = (double)root.val > target ? root.left : root.right;
        }

        return res;
    }
}<file_sep>public class Solution {
    public int MyAtoi(string str) {
        str = str.Trim();
        
        if (str.Length == 0)
            return 0;
        
        var i = 0;
        var sign = 1;
        int res = 0;
        int prev = 0;
        
        if (str[0] == '-'){
            i++;
            sign = -1;
        }
        if (str[0] == '+'){
            i++;
        }
        
        for(; i < str.Length; i++){
            if (char.IsDigit(str[i])){
                res *= 10;
                res += (str[i]-'0');
                
                if (sign == 1 && res < 0)
                    return int.MaxValue;

                if (sign == -1 && res < 0)
                    return int.MinValue;        
            } else{
                break;
            }
        }  
        
        
        return (int)res*sign;      
       
    }
}<file_sep>public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        var rows = matrix.Length;
        if(rows == 0)
            return 0;
        var cols = matrix[0].Length;
        var hist = new int[cols];
        var max = 0;

        for(int r = 0; r < rows; r++){
            for(int c = 0; c < cols; c++){
                hist[c] = matrix[r][c] == '1' ? hist[c]+1 : 0;
            }
            max = Math.Max(max, LargestRectangleArea(hist));
        }

        return max;
    }

    public int LargestRectangleArea(int[] heights) {
        var st = new Stack<int>();
        st.Push(-1);
        var len = heights.Length;
        var max = 0;

        for(int i = 0; i <= len; i++){
            var h = i == len ? -1 : heights[i];
            while(st.Peek() > -1 && heights[st.Peek()] > h){
                var prevIdx = st.Pop();
                var prevVal = heights[prevIdx];

                var square = prevVal * (i - 1 - st.Peek());
                max = Math.Max(max, square);
            }
            st.Push(i);
        }

        return max;
    }
}<file_sep>public class Solution {

    // ["az","ba"],
    public IList<IList<string>> GroupStrings(string[] strings) {
        var map = new Dictionary<int, Dictionary<string, List<string>>>(); // [2][az[az]]

        foreach(var str in strings){ // ba
            var len = str.Length; //2
            if(!map.ContainsKey(len)){ // f
                map[len] = new Dictionary<string, List<string>>();
                map[len][str] = new List<string>{str};
                continue;
            }
            if(len == 1){ // f
                map[len].First().Value.Add(str);
                continue;
            }

            var newGroup = true;
            foreach(var group in map[len]){ // az[az ba]
                if(IsShifted(group.Key, str)){  // t
                    group.Value.Add(str); // 
                    newGroup = false;
                    break;
                }
            }

            if(newGroup) // f
                map[len][str] = new List<string>{str};
        }

        var res = new List<IList<string>>();
        foreach(var d in map.Values){
            foreach(var l in d.Values)
                res.Add(l);
        }

        return res;
    }

    bool IsShifted(string a, string b){ // az ba
        if(a[0] > b[0])
            return IsShifted(b, a);
        
        var shift = b[0] - a[0]; //1
        
        var sb = new char[a.Length];
        for(int i = 0; i < a.Length; i++){
            var shifted = (a[i] - 'a' + shift) % 26 + 'a'; //   
            if(b[i] != (char)shifted)
                return false;
        }
        return true;
    }
}<file_sep>public class Solution {
    public IList<int> DistanceK(TreeNode root, TreeNode target, int K) {
        var st = new Stack<int>();
        var res = new List<int>();

        if(root == null || target == null)
            return res;
        
        if(K == 0){
            res.Add(target.val);
            return res;
        }

        var path = DFS(root, target);
        if(path == null)
            return res;

        TreeNode prev = null;
        while(path.Any() && K > 0){
            var q = new Queue<TreeNode>();
            q.Enqueue(path.Peek());
            var d = K;
            
            while(q.Any() && d > 0){
                for(int i = q.Count; i > 0; i--){
                    var node = q.Dequeue();

                    if(node.left != null && node.left != prev)
                        q.Enqueue(node.left);

                    if(node.right != null && node.right != prev)
                        q.Enqueue(node.right);
                }
                d--;
            }

            while(q.Any())
                res.Add(q.Dequeue().val);

            K--;
            prev = path.Dequeue();
            
            if(K==0 && path.Any())
                res.Add(path.Peek().val);
                
        }

        return res;
    }

    Queue<TreeNode> DFS(TreeNode node, TreeNode target){
        if(node == null)
            return null;

        if(node.val == target.val){
            var q = new Queue<TreeNode>();
            q.Enqueue(node);
            return q;
        }

        var path = DFS(node.left, target) ?? DFS(node.right, target);

        if(path != null){
            path.Enqueue(node);
            return path;
        }

        return null;
    }
}<file_sep>public class Solution {
    public IList<IList<int>> GetSkyline(int[][] buildings) {
        var n = buildings.Length;
        var res = new List<IList<int>>();
        var points = new int[n*2][];

        var idx = 0;
        foreach(var b in buildings){
            points[idx++] = new int[]{b[0], -b[2]}; // x, h
            points[idx++] = new int[]{b[1], b[2]}; // x, h
        }
        
        // sort by x if xa != xb
        // greater hight goes first at start
        // lesser hight goes frist at end
        // start goes before end
        Array.Sort(points, Comparer<int[]>.Create((a,b) => a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));
        var map = new SortedDictionary<int, int>(Comparer<int>.Create((a,b) => b - a)); // sort by hight
        map[0] = 0;

        foreach(var p in points){
            var h = p[1];
            var maxHight = map.First().Key;

            if(h < 0){ // start
                h = -h; // !!!
                map[h] = map.ContainsKey(h) ? map[h]+1 : 1;
            } else { // end
                map[h]--;
                if(map[h] == 0)
                    map.Remove(h);
            }

            var newMax = map.First().Key;
            if(maxHight != newMax)
                res.Add(new List<int>{p[0], newMax});
        }

        return res;
    }

}<file_sep>public class Solution {
    
    private Trie Words;
    private char[][] Board;
    private HashSet<string> Result;
    private int LenR;
    private int LenC;
    private int MaxLen = -1;
    
    public IList<string> FindWords(char[][] board, string[] words) {
        Result = new HashSet<string>();
        
        if(board == null || board[0] == null || words == null || words.Length == 0)
            return Result.ToList();
        
        Board= board;
        LenC = board[0].Length;
        LenR = board.Length;
        
        Words = new Trie();
        foreach(var w in words){
            Words.Insert(w);
            if(w.Length > MaxLen)
                MaxLen = w.Length;
        }
        
        for(var i = 0; i < LenR; i++)
            for(var j =0; j < LenC; j++){
                FindWords(i, j, "");
                if(Result.Count == words.Length)
                    return Result.ToList();
            }
        
        return Result.ToList();
    }
    
    private void FindWords(int row, int col, string prefix){        
        var letter = Board[row][col];
        if(letter == '#')
            return;      
        
        prefix += letter.ToString();
        if(prefix.Length > MaxLen || !Words.StartsWith(prefix))
            return;
        
        if(Words.Search(prefix))
            Result.Add(prefix);
        
        Board[row][col] = '#'; 
        
        foreach((int r, int c) in GetAdjacent(row, col)){
            FindWords(r,c, prefix);
        }
        
        Board[row][col] = letter;
    }
    
    private ValueTuple<int, int>[] Sides = new ValueTuple<int, int>[]{
        (-1,0),
        (1,0),
        (0,-1),
        (0,1)
    };
    
    private IEnumerable<ValueTuple<int, int>> GetAdjacent(int row, int col){
        foreach((int r, int c) in Sides){
            var nRow = row+r;
            var nCol = col+c;
            
            if (nRow >= 0 && nRow < LenR && nCol >=0 && nCol < LenC)
                yield return (nRow, nCol);
        }
    }
    
    public class Trie {
        private Dictionary<char, Trie> Children = new Dictionary<char, Trie>();
        private bool EndOfWord = false;

        /** Initialize your data structure here. */
        public Trie() {

        }

        /** Inserts a word into the trie. */
        public void Insert(string word) {
            if(!string.IsNullOrEmpty(word))
                Insert(word.ToCharArray(), 0);
        }

        private void Insert(char[] word, int ptr){
            if(ptr == word.Length){
                EndOfWord = true;
                return;
            }        

            Trie child = null;

            if(!Children.TryGetValue(word[ptr], out child)){
                child = Children[word[ptr]] = new Trie();
            }

            child.Insert(word, ptr+1);
        }

        /** Returns if the word is in the trie. */
        public bool Search(string word) {
            if(!string.IsNullOrEmpty(word))
                return Search(word.ToCharArray(), 0, true);

            return false;
        }

        private bool Search(char[] word, int ptr, bool checkEnd) {
            if(word.Length == ptr){
                return checkEnd ? EndOfWord : true;
            }

            if(Children.TryGetValue(word[ptr], out var child)){
                return child.Search(word, ptr+1, checkEnd);
            }

            return false;
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public bool StartsWith(string prefix) {
            if(!string.IsNullOrEmpty(prefix))
                return Search(prefix.ToCharArray(), 0, false);        

            return false;
        }
    }
}<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution
{
    public void ReorderList(ListNode head)
    {
        if (head == null)
		{
			return;
		}
        ReorderList(head.next, head);
    }
    
    private ListNode ReorderList(ListNode tail, ListNode parent)
    {
        if(tail == null)
            return parent;

        var head = ReorderList(tail.next, parent);

        if(head == null || head == tail){
            if(head != null)
                head.next = null;
            return null;
        }

        var next = head.next;
        head.next = tail;

        if(next == tail){
            tail.next = null;
            return null;
        }

        tail.next = next;
        return next;
    }
}

public class Solution {
    public void ReorderList(ListNode head) {
        var st = new Stack<ListNode>(); // 1 2 
        var node = head;
        while(node != null){
            st.Push(node);
            node = node.next;
        }

        while(head != null){
            var next = head.next;
            var tail = st.Pop();

            if(tail == head)
                break;
            head.next = tail;
            head = head.next;

            if(next == head)
                break;
            head.next = next;
            head = head.next;
        }

        if(head != null)
            head.next = null;
    }
}<file_sep>public class Solution {
    public int OpenLock(string[] deadends, string target) {
        var dead = new HashSet<string>(deadends);
        var visiteds = new HashSet<string>();
        var visitede = new HashSet<string>();
        if(dead.Contains("0000") || dead.Contains(target))
            return -1;
        if(target == "0000")
            return 0;
        
        var qs = new Queue<string>();
        var qe = new Queue<string>();
        qs.Enqueue("0000");
        visiteds.Add("0000");
        qe.Enqueue(target);
        visitede.Add(target);
        var level = 1;
        
        while(qs.Any() && qe.Any()){
            if(BFS(qs, visiteds, visitede, dead))
                return level;
            level++;
            if(BFS(qe, visitede, visiteds, dead))
                return level;
            level++;
        }
        
        return -1;
    }
    
    bool BFS(Queue<string> q, HashSet<string> visited, HashSet<string> visitedOther, HashSet<string> deadSet){
        for(var count = q.Count; count > 0; count--){
                var node = q.Dequeue();
                foreach(var nei in GetNeighbours(node)){
                    //Console.WriteLine(nei);
                    
                    if (visitedOther.Contains(nei))
                        return true;
                    
                    if(!visited.Contains(nei) && !deadSet.Contains(nei)){
                        visited.Add(nei);
                        q.Enqueue(nei);
                    }
                }
            }
        
        return false;
    }
    
    IEnumerable<string> GetNeighbours(string str){
        
        for(int i = 0; i < str.Length; i++){
            var node = str.ToCharArray();
            var c = (int)(node[i] - '0');
            node[i] = (char)((c == 9 ? 0 : c+1) + '0');
            yield return new String(node);
            
            node[i] = (char)((c == 0 ? 9 : c-1) + '0');
            yield return new String(node);
        }
    }
}<file_sep>public class Solution {
    public bool IsValidSudoku(char[][] board) {
        bool isValid(char c, int[] vals){
            if(c == '.')
                return true;
            if(c < '1' || c > '9')
                return false;
            var idx = c - '1';
            if(vals[idx] == 1)
                return false;
            vals[idx] = 1;
            return true;
        }

        for(int i = 0; i < 9; i++){
            var col = new int[9];
            var row = new int[9];
            for(int j = 0; j < 9; j++){
                if (!isValid(board[i][j], row) || !isValid(board[j][i], col))
                    return false;
            }
        }

        for(var k = 0; k < 9*3; k+=3){
            var col = k % 9;
            var row = (k / 9)*3;
            var vals = new int[9];
            
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    if (!isValid(board[i + row][j + col], vals))
                        return false;
                }
            }
        }

        return true;
    }
}<file_sep>public class Solution {
    public bool CheckValidString(string s) {
        int balance = 0;
        
        foreach(var c in s){
            if (c == ')')
                balance--;
            else
                balance++;
            
            if (balance < 0 )
                return false;
        }
        
        if (balance == 0)
            return true;
        
        balance =0;
        
        for(var i = s.Length -1; i >=0; i--){
            if (s[i] == '(')
                balance--;
            else
                balance++;
            
            if (balance < 0)
                return false;
        }
        
        return true;
    }
}<file_sep>public class Solution {
    public int ExpressiveWords(string S, string[] words) {
       int count = 0;
        foreach(String originalWord in words){
            if(isStretchy(originalWord, S)){
                count ++;
            }
        }
        return count;
    }

    private bool isStretchy(String originalWord, String stretched){
        int i = 0, j = 0;
        while(i < originalWord.Length && j < stretched.Length){
			//Check Rule 1
            if(originalWord[i] != stretched[j]){
                return false;
            }
            
            int repeated1 = getRepeatedLength(originalWord, i);
            int repeated2 = getRepeatedLength(stretched, j);
            
            //Check Rule 2
            if((repeated1 >= repeated2 || repeated2 < 3) && repeated1 != repeated2){
                return false;
            }
            
            i += repeated1;
            j += repeated2;
        }
        
        //Check Rule 1
        return i == originalWord.Length && j == stretched.Length;
    }
    
    private int getRepeatedLength(String word, int start){
        int end = start;
        while (end < word.Length && word[end] == word[start]){
            end ++;
        }
        
        return end - start;
    }

}<file_sep>public class Solution {
    public IList<string> FindStrobogrammatic(int n) {
        var addZero = !firstCall;
        firstCall = false;
        
        if(n == 0)
            return new List<string>{""};
        
        if(n == 1)
            return new List<string>{"0","1","8"};
        
        var prev = FindStrobogrammatic(n - 2);
        
        var list = new List<string>();
        
        foreach(var str in prev){
            if(addZero)
                list.Add($"0{str}0");
            list.Add($"1{str}1");
            list.Add($"6{str}9");
            list.Add($"8{str}8");
            list.Add($"9{str}6");
        }
            
        return list;
    }
    
    private bool firstCall = true;
}<file_sep>/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Master {
 *     public int Guess(string word);
 * }
 */
class Solution {
    public void FindSecretWord(string[] wordlist, Master master) {
        
        var attempts = 10;
        var wl = wordlist;
        var left = wl.Length;
        
        while(attempts > 0 && left > 1){
            var frq = new int[6,26];
            
            foreach(var w in wl){
                if(w == null)
                    continue;
                
                for(int i = 0; i < 6; i++){
                    frq[i, w[i]-'a'] += 1;
                }
            }
            
            string guess = null;
            var best = -1;
            
            foreach(var w in wl){
                if(w == null)
                    continue;
                
                var score = 0;
                for(int i = 0; i < 6; i++){
                    score += frq[i, w[i]-'a'];
                }
                if(score > best){
                    guess = w;
                    best = score;
                }
            }
            
            var match = master.Guess(guess);
            
            for(var j = 0; j < wl.Length; j++){
                var w = wl[j];
                
                if(w == null)
                    continue;
                
                var m = 0;
                for(int i = 0; i < 6; i++){
                    if (w[i] == guess[i])
                        m++;
                }
                
                if(m != match)
                    wl[j] = null;
                else
                    left++;
            }
            
            attempts--;
        }
    }
}<file_sep>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
        var res = new List<IList<int>>();

        var r = PathSum(root, targetSum, 0);
        if( r != null)
            foreach(var st in r)
                res.Add(st.ToList());

        return res;
    }

    public List<Stack<int>> PathSum(TreeNode node, int targetSum, int sum) {
        if(node == null)
            return null;

        if(node.left == null && node.right == null){
            if(sum+node.val == targetSum){
                var r = new List<Stack<int>>{new Stack<int>()};
                r[0].Push(node.val);
                return r;
            }

            return null;
        }

        var stl = PathSum(node.left, targetSum, sum+node.val);
        var str = PathSum(node.right, targetSum, sum+node.val);

        if(stl == null && str == null)
            return null;

        var l = stl ?? str;

        if(str != null && stl != null)
            foreach(var st in str)
                l.Add(st);

        foreach(var st in l)
            st.Push(node.val);

        return l;
    }
}<file_sep>public class Solution {
    public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
        var dsu = new DSU();
        var emailToName = new Dictionary<string, string>();

        foreach(var acc in accounts){
            var name = acc[0];
            for(int i = 1; i < acc.Count; i++){
                emailToName[acc[i]] = name;
                dsu.Union(acc[1], acc[i]);
            }
        }

        var emailGroups = new Dictionary<string, HashSet<string>>();
        foreach(var email in emailToName.Keys){
            var key = dsu.Find(email);
            if(!emailGroups.ContainsKey(key))
                emailGroups[key] = new HashSet<string>();
            
            emailGroups[key].Add(email);
        }

        var res = new List<IList<string>>();

        foreach(var kv in emailGroups){
            var name = emailToName[kv.Key];
            var acc = kv.Value.OrderBy(v => v, StringComparer.Ordinal).ToList();
            acc.Insert(0, name);
            res.Add(acc);
        }

        return res;
    }

    public class DSU{
        public Dictionary<string, string> Nodes = new Dictionary<string, string>();
        
        public void Union(string a, string b){
            Nodes[Find(a)] = Find(b);
        }
        
        public string Find(string v){
            if(!Nodes.ContainsKey(v))
                Nodes[v] = v;

            if(Nodes[v] != v)
                Nodes[v] = Find(Nodes[v]);

            return Nodes[v];
        }
    }
}<file_sep>public class Solution {
    public bool IsBipartite(int[][] graph) {
        var len = graph.Length;
        var colors = new int[len];

        for(int i = 0; i < len; i++){
            if(colors[i] != 0)
                continue;
            
            var q = new Queue<int>();
            q.Enqueue(i);
            colors[i] = 1;
            while(q.Any()){
                var node = q.Dequeue();
                var color = colors[node];

                foreach(var nei in graph[node]){
                    if(colors[nei] == 0){
                        q.Enqueue(nei);
                        colors[nei] = color == 1 ? 2 : 1;
                    } else if(colors[nei] == color){
                        return false;
                    }
                }
            }
        }

        return true;
    }
}<file_sep>public class Solution
{
    public int MaxProfit(int k, int[] prices){
        if (prices == null || prices.Length < 2 || k <= 0)
            return 0;
        
        if (prices.Length < 2 * k)
            k = prices.Length/2;
        
        return  DFS(prices, 0, k, new int?[prices.Length, k+1]);
    }

    int DFS(int[] prices, int start, int k, int?[,] memo){
        if(start > prices.Length-2)
            return 0;
        
        if (memo[start, k] != null) 
            return memo[start, k].Value;

        var maxProfitTotal = int.MinValue;
        var min = int.MaxValue; 
        for (int i = start; i < prices.Length; i++){
            min = Math.Min(min, prices[i]);
            var profit = prices[i]-min;
            if (k > 1)
                profit += DFS(prices, i + 1, k - 1, memo);
            maxProfitTotal = Math.Max(maxProfitTotal, profit);
        }
        
        if(maxProfitTotal < 0)
            maxProfitTotal = 0;

        memo[start, k] = maxProfitTotal;
        return maxProfitTotal;
    }
}<file_sep>public class Codec {

    // Encodes a tree to a single string.
    public string serialize(TreeNode root) {
        if(root == null)
            return "";

        var sb = new List<string>();
        var q = new Queue<TreeNode>();
        q.Enqueue(root);

        while(q.Any()){
            var node = q.Dequeue();
            if(node != null){
                sb.Add(node.val.ToString());
                q.Enqueue(node.left);
                q.Enqueue(node.right);
            } else{
                sb.Add("");
            }
        }
        
        return string.Join(",", sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        if(data == "")
            return null;

        var treeValues = data.Split(",");
        var n = treeValues.Length;

        bool tryGetNode(int idx, out TreeNode node){
            var hasValue = treeValues[idx] != "";
            node = hasValue ? new TreeNode{val = int.Parse(treeValues[idx])} : null;
            return hasValue;
        }

        tryGetNode(0, out var root);
        var q = new Queue<TreeNode>();
        q.Enqueue(root);

        for(int i = 1; i < n; i++){
            var node = q.Dequeue();

            if(tryGetNode(i, out node.left))
                q.Enqueue(node.left);

            if(tryGetNode(++i, out node.right))
                q.Enqueue(node.right);
        }

        return root;
    }
}<file_sep>public class Solution {
    public string DecodeString(string s) {
        var ptr = 0;
        var sb = new StringBuilder();
        while(ptr < s.Length){
            var c = s[ptr];
            if(c > '0' && c <= '9')
                sb.Append(Decode(s, ref ptr));
            else
                sb.Append(c);
            ptr++;
        }
        return sb.ToString();
    }
    
    private string Decode(string s, ref int ptr){
        var num = 0;
        while(ptr < s.Length && s[ptr] != '['){
            num *= 10;
            num += (int)(s[ptr]-'0');
            ptr++;
        }
        ptr++;
        
        var sb = new StringBuilder();
        while(ptr < s.Length && s[ptr] != ']'){
            var c = s[ptr];
            if(c > '0' && c <= '9')
                sb.Append(Decode(s, ref ptr));
            else{
                sb.Append(c);
            }
            ptr++;
        }
                
        return string.Concat(Enumerable.Repeat(sb.ToString(), num));
    }
}<file_sep>public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        var n1 = m-1;
        var n2 = n-1;
        var i = nums1.Length-1;
        
        while(n1 >= 0 && n2 >= 0){
            if(nums1[n1] > nums2[n2]){
                nums1[i]=nums1[n1];
                n1--;                
            } else{
                nums1[i] = nums2[n2];
                n2--;
            }            
            i--;
        }
        
        while(n2 >= 0){
            nums1[i] = nums2[n2];
            n2--;
            i--;
        }
    }
}<file_sep>/**
 * The Read4 API is defined in the parent class Reader4.
 *     int Read4(char[] buf4);
 */

public class Solution : Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */

    // abcde
    public int Read(char[] buf, int n) { // [] 5
        var buf4 = new char[4];
        var idx = 0; // 5
        var len = 4; // 4

        while(n > idx && len == 4){ // true
            len = Read4(buf4); // 1
            for(int i = 0; i < len && n > idx; i++) // 1
                buf[idx++] = buf4[i];
        }

        return idx;
    }
}<file_sep>public class Solution {
    public int NumDecodings(string s) { 
        return DFS(s, 0, new int?[s.Length]);
    }

    public int DFS(string s, int start, int?[] memo){
        if(start > s.Length-1)
            return 1;

        if(memo[start] != null)
            return memo[start].Value;

        var res = 0;
        var num = s[start] - '0';
        if(num > 0){
            res += DFS(s, start+1, memo); 
            if(start+1 < s.Length){
                num = num * 10 + s[start+1] - '0';
                if(num <= 26)
                    res += DFS(s, start+2, memo);
            }
        }
            
        memo[start] = res;
        return res;
    }
}<file_sep>public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        var rows = matrix.Length;
        if(rows == 0)
            return false;
        var cols = matrix[0].Length;
        var c = 0;
        var r = rows-1;

        while(r >=0 && c < cols){
            var val = matrix[r][c];
            if(target == val)
                return true;

            if(target > val)
                c++;
            else
                r--;
        }

        return false;
    }
}<file_sep>public class RLEIterator {
    int[] a;
    int reps = 0;
    int ptr = -2;
    
    public RLEIterator(int[] A) {
       a = A; 
    }
    
    public int Next(int n) {
        while(reps < n && ptr + 2 < a.Length){
            n -= reps;
            ptr += 2;
            reps = a[ptr];
        }
        
        if(reps < n){
            reps = 0;
            return -1;
        }
        
        reps -= n;
        return a[ptr+1];
    }
}

/**
 * Your RLEIterator object will be instantiated and called as such:
 * RLEIterator obj = new RLEIterator(A);
 * int param_1 = obj.Next(n);
 */<file_sep>public class Solution {
    public string AddBinary(string a, string b) {
        var idxa = a.Length-1;
        var idxb = b.Length-1;
        var sb = new List<char>();
        var carry = 0;
        while(idxa >=0 || idxb >=0){
            var sum = carry;
            if(idxa >= 0)
                sum += a[idxa--]-'0';
            if(idxb >= 0)
                sum += b[idxb--]-'0';
            sb.Add((char)((sum % 2)+'0'));
            carry = sum / 2;
        }

        if(carry == 1)
            sb.Add((char)(carry+'0'));

        sb.Reverse();
        return new String(sb.ToArray());
    }
}
<file_sep>class Solution {
    public int CountSquares(int[][] matrix) {
        var res = 0;
        for(int i = 0; i < matrix.Length; i++)
            for(int j = 0; j < matrix[0].Length; j++)
                if(matrix[i][j] > 0){
                    if(i > 0 && j > 0)
                        matrix[i][j] = Math.Min(Math.Min(matrix[i-1][j], matrix[i][j-1]), matrix[i-1][j-1])+1;
                    res += matrix[i][j];
                }
        
        return res;
    }
}<file_sep>public class Solution {
    /*
         1

    */
    public Node TreeToDoublyList(Node root) { // 4
        if(root == null)
            return null;

        var st = new Stack<Node>(); // 1

        void TraverseLeft(Node n){
            while(n != null){
                st.Push(n);
                n = n.left;
            }
        }
        
        TraverseLeft(root);
        var head = st.Peek(); // 1
        Node node = null; // 1

        while(st.Any()){ 
            var n = st.Pop(); // 5
            if(node == null){
                node = n; // 1
            } else {
                node.right = n; // 1 - 2 - 3 - 4 -5
                n.left = node; 
                node = n; // 5
            }

            if(n.right != null) // t
                TraverseLeft(n.right);
        }

        node.right = head; // 1-1
        head.left = node; // 1-1

        return head;
    }
}<file_sep>/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        
        var result = new ListNode(0);
        var l = result;
        
        while(l1 != null && l2 != null)
        {
            if (l1.val < l2.val){
                l.next = l1;
                l1 = l1.next;
            } else{
                l.next = l2;
                l2 = l2.next;
            }
            l = l.next;
        }
        
        var left = l1 != null ? l1 : l2;
        
        while(left != null){
            l.next = left;
            left = left.next;
            l = l.next;
        }

        
        return result.next;
    }
}<file_sep>public class Solution {
    public int[] AsteroidCollision(int[] a) {
        var n = a.Length;
        if(n < 2)
            return a;

        var res = new List<int>();
        var st = new Stack<int>();
        for(int i=0; i < n;){
            var v = a[i];
            if(v < 0){
                if(!st.Any() || st.Peek() < -1*v){
                    if(st.Any())
                        st.Pop(); // positive destroyed
                    else
                    {
                        res.Add(v); // no collision
                        i++;
                    }
                } else {
                    if(st.Peek() == -1*v) // both destroyed
                        st.Pop();
                    i++;
                }
            } else{
                st.Push(v);
                i++;
            }
        }

        foreach(var v in st.Reverse())
            res.Add(v);

        return res.ToArray();
    }
}<file_sep>public class Solution {

    /*

    1 2  2
    0 -1 1
    1 1  0
    */
    public void WallsAndGates(int[][] rooms) {
        var rows = rooms.Length;
        var cols = rooms[0].Length;
        var q = new Queue<(int,int)>();
        for(int r = 0; r < rows; r++){
            for(int c = 0; c < cols; c++){
                if(rooms[r][c] == 0)
                    q.Enqueue((r,c)); // (0, 1) (2,2)
            }
        }

        var distance = 1;
        var directions = new (int, int)[]{(-1,0),(1,0),(0,1),(0,-1)};
        while(q.Any()){
            for(int i = q.Count; i > 0; i--){
                var (row, col) = q.Dequeue();
                foreach(var (deltaRow, deltaCol) in directions){
                    var r = row+deltaRow;
                    var c = col+deltaCol;
                    if(r >= 0 && r < rows && c >= 0 && c < cols && rooms[r][c] == int.MaxValue){
                        rooms[r][c] = distance;
                        q.Enqueue((r,c));
                    }
                }
            }
            distance++;
        }
    }
}<file_sep>public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        if (text1.Length > text2.Length){
            return LongestCommonSubsequence(text2, text1);
        }
        
        var l1 = text1.Length;
        var l2 = text2.Length;
        var memo = new int[l2+1,l1+1];
        
        for(int i = 1; i <= l2; i++){
            for(int j = 1; j <= l1; j++){
                if (text2[i-1]==text1[j-1]){
                    memo[i,j] = memo[i-1,j-1]+1;
                } else{
                    memo[i,j] = Math.Max(memo[i-1,j], memo[i,j-1]);
                }
            }
        }
        
        return memo[l2, l1];
    }
}<file_sep>public class Solution {
    public int LengthOfLIS(int[] nums) {
        //return DFS(nums, 0, -1, new int?[nums.Length+1, nums.Length+1]);

        
        var res = 0;
        var len = nums.Length;
        
        if(len < 2)
            return len;
        
        var dp = new int[len];
        dp[0] = 1;

        for(int i = 1; i < len; i++){
            var max = 0;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    max = Math.Max(max, dp[j]);
            }
            dp[i] = max+1;
            res = Math.Max(max+1, res);
        }

        return res;
    }

    private int DFS(int[] nums, int cur, int prev, int?[,] memo){
        if(cur == nums.Length)
            return 0;

        if(memo[cur, prev+1] != null)
            return memo[cur, prev+1].Value;

        var count = DFS(nums, cur+1, prev, memo);
        
        var isIncreasing = prev == -1 || nums[cur] > nums[prev];
        if(isIncreasing)
            count = Math.Max(count, DFS(nums, cur+1, cur, memo)+1);

        memo[cur, prev+1] = count;
        return count;
    }
}<file_sep>public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        var res = new List<int>();

        var rows = matrix.Length-1;
        if(rows == -1)
            return res;

        var cols = matrix[0].Length-1;
        var frow = 0;
        var fcol = 0;

        while(fcol<=cols && frow<=rows){
            for(int i = fcol; i <= cols; i++)
                res.Add(matrix[frow][i]);
            frow++;

            for(int i = frow; i <= rows; i++)
                res.Add(matrix[i][cols]);
            cols--;
            

            if(frow<=rows){
                for(int i = cols; i >= fcol; i--)
                    res.Add(matrix[rows][i]);
                rows--;
            }

            if(fcol<=cols){
                for(int i = rows; i >= frow; i--)
                    res.Add(matrix[i][fcol]);
                fcol++;
            }
        }
        return res;
    }
}<file_sep>public class Solution {
    public void SortColors(int[] nums) {
        var lo = 0;
        var hi = nums.Length-1;
        
        for(int i = 0; i < nums.Length; i++)
            if(nums[i] == 0)
                Swap(nums, lo++, i);
        
        for(int i = nums.Length-1; i >= lo; i--)
            if(nums[i] == 2)
                Swap(nums, i, hi--);
    }

    private void Swap(int[] nums, int a, int b){
        if(a == b)
            return;
        
        var t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}<file_sep>public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        var res = new List<IList<int>>();
        for(int i = 0; i < nums.Length && nums[i] <= 0; i++){
            if (i == 0 || nums[i-1] != nums[i]){
                TwoSum(nums, i, res);
            }
        }
        
        return res;
    }
    
    public void TwoSum(int[] nums, int i, List<IList<int>> res) {
        var lo = i+1;
        var hi = nums.Length-1;
        
        while(lo < hi){          
            var sum = nums[i] + nums[lo] + nums[hi];
            if(sum > 0){
                hi--;
            } else if(sum < 0){
                lo++;
            } else{
                res.Add(new List<int>{nums[i], nums[lo++], nums[hi--]});
                while (lo < hi && nums[lo-1] == nums[lo]){
                    lo++;
                }
            }
        }
    }
}<file_sep>public class Solution {
    public int[] ExclusiveTime(int n, IList<string> logs) {
        var res = new Dictionary<int, int>();
        var callStack = new Stack<Function>();

        foreach(var entry in logs){
            var f = new Function(entry);
            if(f.Type == "start"){
                callStack.Push(f);
            } else {
                var fStart = callStack.Pop();
                var exclusive = f.Ts - fStart.Ts + 1;
                
                if(!res.ContainsKey(f.Id))
                    res[f.Id] = 0;

                res[f.Id] += exclusive-fStart.Inclusive;
                if(callStack.Any())
                    callStack.Peek().Inclusive += exclusive;
            }
        }

        var ans = new int[res.Count];
        foreach(var kv in res)
            ans[kv.Key] = kv.Value;

        return ans;
    }

    class Function{
        public int Ts;
        public int Id;
        public string Type;
        public int Inclusive;

        public Function(string entry){
            var arr = entry.Split(":");
            Id = int.Parse(arr[0]);
            Type = arr[1];
            Ts = int.Parse(arr[2]);
        }
    }
}<file_sep>public class Solution {
    public bool IsPalindrome(string s) {

        
        
        var l = 0;
        var r = s.Length-1;
        while (r >= l){            
            if(!char.IsLetterOrDigit(s[l])){
                l++;
            } else if(!char.IsLetterOrDigit(s[r])){
                r--;
            } else if(char.ToLower(s[l++]) != char.ToLower(s[r--]))
                return false;
        }
        
        return true;
    }
}<file_sep>public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.Length > nums2.Length)
            return FindMedianSortedArrays(nums2, nums1);
        
        var l1 = nums1.Length;
        var l2 = nums2.Length;
        var len = (l1+l2+1)/2;
        
        var lo = 0;
        var hi = l1;
        
        while(lo <= hi){
            
            var mid1 = lo + (hi-lo)/2;
            var mid2 = len - mid1;
            
            var vLeft1 = mid1 == 0 ? int.MinValue : nums1[mid1-1];
            var vLeft2 = mid2 == 0 ? int.MinValue : nums2[mid2-1];
            
            var vRight1 = mid1 == l1 ? int.MaxValue : nums1[mid1];
            var vRight2 = mid2 == l2 ? int.MaxValue : nums2[mid2];
            
            if(vLeft1 <= vRight2 && vLeft2 <= vRight1){
                return (l1+l2) % 2 == 0
                    ? (Math.Max(vLeft1, vLeft2) + Math.Min(vRight1, vRight2)) / 2.0
                    : Math.Max(vLeft1, vLeft2);
            }
                
            if(vLeft1 > vRight2)
                hi = mid1-1;
            else
                lo = mid1+1;
            
        }
        
        return -1;
    }
}<file_sep>public class Solution {
    public int NumPairsDivisibleBy60(int[] time) {
        var map = new Dictionary<int, int>();
        foreach(var t in time){
            var n = t%60;
            if(map.ContainsKey(n))
                map[n]++;
            else
                map[n] = 1;
        }

        var res = 0;
        foreach(var term1 in map.Keys.ToArray()){
            if(term1 == 30 || term1 == 0){
                var n = map[term1]-1;
                res += ((n*n+n)/2);
                continue;
            }

            var term2 = 60-term1;
            if(map.ContainsKey(term2)){
                res += map[term1] * map[term2];
                map[term1] = 0;
            }
        }

        return res;
    }
}<file_sep>public class Solution {
    public int FindMaxLength(int[] nums) {
        

			var equalSums = new Dictionary<int, int>();
			equalSums[0] = -1;
			int maxDistance = 0;
			int prev = 0;
			for(int i=0; i<nums.Length; i++){
				var v = nums[i] == 0 ? -1 : 1;
				var currentSum = prev + v;
				prev = currentSum;
            
				if (equalSums.TryGetValue(currentSum, out var firstIndexOccurance))
				{
					var distance = i-firstIndexOccurance;
					if (distance > maxDistance)
						maxDistance = distance;
				}
				else
				{
					equalSums[currentSum] = i;   
				}
			}
        
			return maxDistance;
    }
}<file_sep>public class Solution {
    public int ShortestDistance(int[][] grid) {
        
    }
}<file_sep>public class Solution {
    public bool IsNumber(string s) {
        if(s == null || s.Length == 0)
            return false;

        var sign = new State{ Symbols = new HashSet<char>{'-', '+'}};
        var digit = new State{ Symbols = new HashSet<char>{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}};
        var dot = new State{ Symbols = new HashSet<char>{'.'}};

        sign.Next = new List<State>{dot, digit};
        dot.Next = new List<State>{digit};
        digit.Next = new List<State>{dot, digit};

        var state = new State{Next = new List<State>{sign, digit, dot}};
        var isExpVisited = false;

        foreach(var c in s){
            if(c == 'E' || c == 'e'){
                if(isExpVisited || sign.Visited > 1 || dot.Visited > 1 || digit.Visited < 1)
                    return false;
                
                // reset state machine
                isExpVisited = true;
                sign.Visited = digit.Visited = 0;
                sign.Next = new List<State>{digit};
                digit.Next = new List<State>{digit};
                state = new State{Next = new List<State>{sign, digit}};
            } else{
                state = state.Next.FirstOrDefault(st => st.Symbols.Contains(c));
                if(state == null)
                    return false;
                state.Visited++;
            }
        }     

        return !(sign.Visited > 1 || dot.Visited > 1 || digit.Visited < 1);
    }
    
    class State{
        public HashSet<char> Symbols;
        public List<State> Next;
        public int Visited;
    }
}<file_sep>public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var res = new List<IList<int>>();
        var n = nums.Length;

        void swap(int a, int b){
            if(a != b){                
                var t = nums[a];
                nums[a] = nums[b];
                nums[b] = t;
            }
        }

        void permute(int start){
            if(start == n)
                res.Add(new List<int>(nums)); // copy current !!!!
            else
                for(int i = start; i < n; i++){
                    swap(start, i);
                    permute(start+1);
                    swap(start, i);                       
                }
        }

        permute(0);
        return res;
    }
    
}<file_sep>public class MyCalendar {
    List<ValueTuple<int,int>> data;

    public MyCalendar() {
        data = new List<ValueTuple<int,int>>();
        // dirty hack for binary searxh simplification
        //data.Add((int.MinValue, int.MinValue));
       // data.Add((int.MaxValue, int.MaxValue));
    }
    
    public bool Book(int start, int end) {
        if(!data.Any()){
            data.Add((start, end)); 
            return true;
        }
        
        if(data.Count == 1){
            (var iStart, var iEnd) = data[0];
            //Console.WriteLine(iStart +" "+ end  +" "+start +" "+ iEnd);
            
            if(iStart > end || start < iEnd)
                return false;
            data.Insert(start < iStart ? 0 : 1, (start, end)); 
            return true;
        }
        
        var lo = 0;
        var hi = data.Count;
        while(lo < hi){
            var mid = lo + (hi - lo)/2;
            (var next, _) = data[mid];
            if(start == next)
                return false;
            
            if(start < next)
                hi = mid;
            else
                lo = mid+1;
        }
        
        if (lo >= data.Count-1)
            return data[data.Count-1].Item2 <= start;
        
        if (lo == 0)
            return end <= data[lo].Item1;
        
        (var nextStart, _) = data[lo+1];
        (_, var prevEnd) = data[lo];
        if(nextStart < end || start < prevEnd)
            return false;
        
        data.Insert(lo, (start, end)); 
        return true;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * bool param_1 = obj.Book(start,end);
 */<file_sep>public class AutocompleteSystem {

    TrieNode Trie;
    TrieNode Current;
    private StringBuilder sb;

    public AutocompleteSystem(string[] sentences, int[] times) {
        Trie = new TrieNode();

        for(int i = 0; i < sentences.Length; i++){
            AddSentence(sentences[i], times[i]);
        }

        Reset();
    }

    private void Reset(){
        Current = Trie;
        sb = new StringBuilder();
    }

    private int Idx(char c){
        return c == ' ' ? 26 : c-'a';
    }

    private void AddSentence(string str, int frq){
        var trie = Trie;

        foreach(var c in str){
            if(trie.Children[Idx(c)] == null)
                trie.Children[Idx(c)] = new TrieNode();

            trie = trie.Children[Idx(c)];
        }

        trie.Sentence = str;
        trie.Frq += frq;
    }

    public IList<string> Input(char c) {
        var res = new List<string>();
        if(c == '#'){
            var str = sb.ToString();
            AddSentence(str, 1);
            Reset();
            return res;
        }

        sb.Append(c);

        if(Current == null || Current.Children[Idx(c)] == null){
            Current = null;
            return res;
        }

        Current = Current.Children[Idx(c)];

        var heap = new Heap(3);
        var q = new Queue<TrieNode>();
        q.Enqueue(Current);
        while(q.Any()){
            var node = q.Dequeue();
            if(node.Sentence != null)
                heap.Add(node.Sentence, node.Frq);
            foreach(var child in node.Children.Where(n => n != null))
                q.Enqueue(child);
        }

        return heap.Take();
    }

    class TrieNode{
        public TrieNode[] Children = new TrieNode[27];
        public string Sentence;
        public int Frq;
    }

    class Heap{
        SortedDictionary<int, SortedSet<string>> map = new SortedDictionary<int, SortedSet<string>>();
        int capacity;

        public Heap(int cap){
            capacity = cap;
        }

        public void Add(string str, int frq){
            if(map.Count == capacity){
                var smallest = map.First();
                if(smallest.Key > frq)
                    return;
                
                if(smallest.Key != frq)
                    map.Remove(smallest.Key);
            }

            if(map.ContainsKey(frq))
                map[frq].Add(str);
            else
                map[frq] = new SortedSet<string>{str};
        }

        public List<string> Take(){
            var top = new List<string>();

            foreach(var bucket in map.Reverse()){
                foreach(var s in bucket.Value){
                    top.Add(s);
                    if(top.Count == capacity)
                        return top;
                }
            }

            return top;
        }
    }
}
<file_sep>public class Solution {
    public bool CanJump(int[] nums) {
        
        if(nums == null || nums.Length <= 1){
            return true;
        }
        
        
        var lastGood = nums.Length - 1;
        
        for(var pos = nums.Length - 2; pos >= 0; pos--){            
            if(pos+nums[pos] >= lastGood)
                lastGood = pos;
        }
        
        return lastGood == 0;
        
        /*var memo = new int[nums.Length];
        memo[nums.Length-1] = 1;
        
        for(var pos = nums.Length - 2; pos >= 0; pos--){
            var jump = (int)Math.Min(nums[pos]+pos, nums.Length-1);
            
            for(var i = pos + 1; i <= jump; i++){
                if(memo[i] == 1){
                    memo[pos] = 1;
                    break;
                }
            }
        }
        
        return memo[0] == 1;*/
        
        //return BackTrack(nums, 0, new int[nums.Length]);
    }
    
    /*private bool BackTrack(int[] nums, int pos, int[] memo){
        if(pos == nums.Length-1 || memo[pos] == 1)
            return true;
        
        if(memo[pos] == -1)
            return false;
        
        var jump = (int)Math.Min(nums[pos]+pos, nums.Length-1);
        for(var i = jump; i > pos; i--){
            if(BackTrack(nums, i, memo)){
                memo[pos] = 1;
                return true;
            }
        }
        
        memo[pos] = -1;
        return false;
    }*/
}<file_sep>public class Solution {
    public IList<int> CountSmaller(int[] nums) {
        var n = nums.Length;
        var s = new List<int>(n);
        var res = new int[n];
        
        for(var i = n-1; i >= 0; i--){
            var num = nums[i];
            var last = s.Count-1;
        
            if(last == -1 || s[0] >= num){
                s.Insert(0, num);
                res[i] = 0;
                continue;
            }
        
            if(s[last] < num){
                res[i] = s.Count;
                s.Add(num);
                continue;
            }
            
            var lo = 0;
            var hi = last;
            while(lo < hi){
                var mid = lo + (hi-lo)/2;
                if(s[mid] >= num)
                    hi = mid;
                else
                    lo = mid + 1;
            }
            
            res[i] = lo;
            s.Insert(lo, num);
        }
        
        return res;
    }
}

// Binary index tree

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new LinkedList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        // find min value and minus min by each elements, plus 1 to avoid 0 element
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            min = (nums[i] < min) ? nums[i]:min;
        }
        int[] nums2 = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            nums2[i] = nums[i] - min + 1;
            max = Math.max(nums2[i],max);
        }
        int[] tree = new int[max+1];
        for (int i = nums2.length-1; i >= 0; i--) {
            res.add(0,get(nums2[i]-1,tree));
            update(nums2[i],tree);
        }
        return res;
    }
    private int get(int i, int[] tree) {
        int num = 0;
        while (i > 0) {
            num +=tree[i];
            i -= i&(-i);
        }
        return num;
    }
    private void update(int i, int[] tree) {
        while (i < tree.length) {
            tree[i] ++;
            i += i & (-i);
        }
    }
}<file_sep>public class Solution {
    public int DieSimulator(int n, int[] rollMax) {
        var memo = new Dictionary<ValueTuple<int,int,int>, int>();
        var m = (int)Math.Pow(10,9)+7;
        int DFS(int roll, int prev, int len){
            if(roll > n)
                return 1;
            
            var key = (roll, prev, len);
            if(memo.ContainsKey(key))
                return memo[key];
            
            var res = 0;
            for(int i = 1; i <=6; i++){
                if(i == prev && rollMax[i-1] == len)
                    continue;
                
                res = (res + DFS(roll+1, i,  i == prev ? len+1 : 1)) % m;
            }
            
            memo[key] = res;
            return res;
        }
        
        return DFS(1, -1, 0);
    }
}<file_sep>/**
 * The Read4 API is defined in the parent class Reader4.
 *     int Read4(char[] buf4);
 */

public class Solution : Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    
    private int buffPtr;
    private int buffCnt;
    private char[] buf4 = new char[4];
    private bool eof;
    
    public int Read(char[] buf, int n) {
        if (n <= 0 || eof)
            return 0;
        
        var ptr = 0;
        
        while(ptr < n){            
            if(buffCnt == 0){
                buffPtr = 0;
                buffCnt = Read4(buf4);
            }
            
            if(buffCnt == 0){
                eof = true;
                break;
            }
            
            while(buffCnt > 0 && ptr < n){
                buf[ptr++] = buf4[buffPtr++];
                buffCnt--;
            }
        }       
        
        return ptr;
    }

}<file_sep>public class Solution {
    public int Compress(char[] chars) {
        var n = chars.Length;
        var w = 0;
        for(int r = 0; r < n; r++){
            var start = r;
            while(r < n-1 && chars[r+1] == chars[r])
                r++;
            
            chars[w++] = chars[r];
            
            if(r > start)
                foreach(var c in (r - start + 1).ToString())
                    chars[w++] = c;
        }
        return w;
    }
}