Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

public class Solution {
    public double KnightProbability(int n, int k, int row, int column) {
        int[][] directions = new int[][] {
            new int[] {1, 2}, new int[] {1, -2}, new int[] {-1, 2}, new int[] {-1, -2},
            new int[] {2, 1}, new int[] {2, -1}, new int[] {-2, 1}, new int[] {-2, -1}
        };
        double[][][] dp = new double[k + 1][][];
        for (int i = 0; i <= k; i++) {
            dp[i] = new double[n][];
            for (int j = 0; j < n; j++) {
                dp[i][j] = new double[n];
            }
        }
        dp[0][row][column] = 1;

        for (int moves = 1; moves <= k; moves++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] direction : directions) {
                        int prevI = i - direction[0];
                        int prevJ = j - direction[1];
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
                        }
                    }
                }
            }
        }

        double totalProbability = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalProbability += dp[k][i][j];
            }
        }

        return totalProbability;
    }
}

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

public class Solution {
    protected int CellsToBitmap(int[] cells) {
        int stateBitmap = 0;
        foreach (int cell in cells) {
            stateBitmap = (stateBitmap << 1) | cell;
        }
        return stateBitmap;
    }

    protected int[] NextDay(int[] cells) {
        int[] newCells = new int[cells.Length];
        for (int i = 1; i < cells.Length - 1; ++i) {
            newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
        }
        return newCells;
    }

    public int[] PrisonAfterNDays(int[] cells, int N) {
        Dictionary<int, int> seen = new Dictionary<int, int>();
        bool isFastForwarded = false;

        while (N > 0) {
            if (!isFastForwarded) {
                int stateBitmap = CellsToBitmap(cells);
                if (seen.ContainsKey(stateBitmap)) {
                    N %= seen[stateBitmap] - N;
                    isFastForwarded = true;
                } else {
                    seen[stateBitmap] = N;
                }
            }

            if (N > 0) {
                N--;
                cells = NextDay(cells);
            }
        }
        return cells;
    }
}

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> LargeGroupPositions(string S) {
        var ans = new List<IList<int>>();
        int i = 0, N = S.Length;

        for (int j = 0; j < N; ++j) {
            if (j == N - 1 || S[j] != S[j + 1]) {
                if (j - i + 1 >= 3) {
                    ans.Add(new List<int> { i, j });
                }
                i = j + 1;
            }
        }

        return ans;
    }
}

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode pred = sentinel;
        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pred.next = head.next;
            } else {
                pred = pred.next;
            }
            head = head.next;
        }
        return sentinel.next;
    }
}

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

public class Solution {
    public int NumFactoredBinaryTrees(int[] A) {
        const int MOD = 1_000_000_007;
        Array.Sort(A);
        var dp = new long[A.Length];
        Array.Fill(dp, 1);
        var index = new Dictionary<int, int>();
        
        for (int i = 0; i < A.Length; i++) {
            index[A[i]] = i;
        }
        
        for (int i = 0; i < A.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.ContainsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index[right]]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        foreach (long x in dp) {
            result = (result + x) % MOD;
        }
        return (int)result;
    }
}

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

public class Solution {
    public int PathSum(int[] nums) {
        var tree = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree[depth * 10 + pos] = val;
        }
        
        return Dfs(tree, 1, 1, 0);
    }
    
    private int Dfs(Dictionary<int, int> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.ContainsKey(key)) {
            return 0;
        }
        currentSum += tree[key];
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.ContainsKey(leftChild) && !tree.ContainsKey(rightChild)) {
            return currentSum;
        }
        return Dfs(tree, depth + 1, 2 * pos - 1, currentSum) + Dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

public class Solution {
    public IList<int> FindClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.Length - k;

        while (left < right) {
            int mid = (left + right) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return arr.Skip(left).Take(k).ToList();
    }
}

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

public class Solution {
    public int CountGoodSubarrays(int[] nums, int k) {
        int count = 0;
        int left = 0;
        int right = 0;
        int distinctCount = 0;
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        while (right < nums.Length) {
            if (!freq.ContainsKey(nums[right])) {
                freq[nums[right]] = 0;
            }
            freq[nums[right]]++;
            if (freq[nums[right]] == 1) {
                distinctCount++;
            }
            right++;
            
            while (distinctCount > k) {
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    distinctCount--;
                }
                left++;
            }
            
            if (distinctCount == k) {
                count++;
            }
        }
        
        return count;
    }
}

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

public class Solution {
    public int ComputeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int areaOfA = (ay2 - ay1) * (ax2 - ax1);
        int areaOfB = (by2 - by1) * (bx2 - bx1);

        int left = Math.Max(ax1, bx1);
        int right = Math.Min(ax2, bx2);
        int xOverlap = right - left;

        int top = Math.Min(ay2, by2);
        int bottom = Math.Max(ay1, by1);
        int yOverlap = top - bottom;

        int areaOfOverlap = 0;
        if (xOverlap > 0 && yOverlap > 0) {
            areaOfOverlap = xOverlap * yOverlap;
        }

        int totalArea = areaOfA + areaOfB - areaOfOverlap;
        return totalArea;
    }
}

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

public class Solution {
    public int MaxSubArrayLen(int[] nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        Dictionary<int, int> indices = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.ContainsKey(prefixSum - k)) {
                longestSubarray = Math.Max(longestSubarray, i - indices[prefixSum - k]);
            }
            if (!indices.ContainsKey(prefixSum)) {
                indices[prefixSum] = i;
            }
        }
        
        return longestSubarray;
    }
}

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

class Solution {
    public bool Overlap(int[] interval1, int[] interval2) {
        return (interval1[0] >= interval2[0] && interval1[0] < interval2[1]) ||
               (interval2[0] >= interval1[0] && interval2[0] < interval1[1]);
    }
    
    public bool CanAttendMeetings(int[][] intervals) {
        for (int i = 0; i < intervals.Length; i++) {
            for (int j = i + 1; j < intervals.Length; j++) {
                if (Overlap(intervals[i], intervals[j])) {
                    return false;
                }
            }
        }
        return true;
    }
}

Input: nums = [1,1,2]  
Output: 2, nums = [1,2,_]  

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 0) return 0;
        
        int i = 0;
        for (int j = 1; j < nums.Length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        
        return i + 1;
    }
}

Input: nums = [3,2,1]
Output: 1

public class Solution {
    public int ThirdMax(int[] nums) {
        int? first = null;
        int? second = null;
        int? third = null;
        
        foreach (int num in nums) {
            if (num == first || num == second || num == third) {
                continue;
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = num;
            } else if (second == null || num > second) {
                third = second;
                second = num;
            } else if (third == null || num > third) {
                third = num;
            }
        }
        
        return third ?? first.Value;
    }
}