LeetCode OJ(C#) – Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solution 1: in place swap solution.

        public int MissingNumber2(int[] nums)
        {
            for (int i = 0; i < nums.Length; i++)             
            {                 
                if(nums[i] == i) continue;                 
                if(nums[i] > nums.Length) continue;

                Utility.Swap(nums, i, nums[i]);
                i--;
            }

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != i) return i;
            }

            return nums.Length;
        }

Solution 2: get sum

        public int MissingNumber3(int[] nums)
        {
            long sum = 0;
            for (int i = 0; i < nums.Length + 1; i++)
            {
                sum += i;
            }

            return (int)(sum - nums.Sum());
        }

Solution 3: use bit manipulation to avoid overflow checking.

        public int MissingNumber4(int[] nums)
        {
            var result = nums.Length;
            var i = 0;
            foreach (var num in nums)
            {
                result ^= num;
                result ^= i;
                i++;
            }

            return result;
        }

LeetCode OJ(C#) – Self Crossing

Tags

ou are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return true (self crossing)

Solution : if we can use extra space, we can store all the nodes that we have already visited and when it moves, check it has to visit the previously visited node or not.

        public bool IsSelfCrossing(int[] x)
        {
            var visited = new HashSet<Tuple<int, int>>();
            var cur = new Tuple<int, int>(0, 0);
            visited.Add(cur);

            for (int i = 0; i < x.Length; i++)
            {
                var xCoordinate = cur.Item1;
                var yCoordinate = cur.Item2;

                var next = new Tuple<int, int>(xCoordinate, yCoordinate);

                if (i%4 == 0)
                {
                    // up
                    for (int j = 1; j <= x[i]; j++)
                    {
                        next = new Tuple<int, int>(xCoordinate, yCoordinate + j);
                        if (visited.Contains(next))
                        {
                            return true;
                        }

                        visited.Add(next);
                    }
                }
                else if (i%4 == 1)
                {
                    // left
                    for (int j = 1; j <= x[i]; j++)
                    {
                        next = new Tuple<int, int>(xCoordinate - j, yCoordinate);
                        if (visited.Contains(next))
                        {
                            return true;
                        }

                        visited.Add(next);
                    }
                }
                else if (i%4 == 2)
                {
                    // down
                    for (int j = 1; j <= x[i]; j++)
                    {
                        next = new Tuple<int, int>(xCoordinate, yCoordinate - j);
                        if (visited.Contains(next))
                        {
                            return true;
                        }

                        visited.Add(next);
                    }
                }
                else
                {
                    // right
                    for (int j = 1; j <= x[i]; j++)
                    {
                        next = new Tuple<int, int>(xCoordinate + j, yCoordinate);
                        if (visited.Contains(next))
                        {
                            return true;
                        }

                        visited.Add(next);
                    }
                }

                cur = next;
            }

            return false;
        }

Solution 2: if you analysis all the self crossing cases, you may find it has only 3 cases. see here for more info.

        public bool IsSelfCrossing2(int[] x)
        {
            for (int i = 3; i < x.Length; i++)             
            {                 
                // case 1                 
                if (x[i] >= x[i - 2] && x[i - 1] <= x[i - 3]) return true;                 
                // case 2                 
                if (i >= 4 && (x[i] >= x[i - 2] - x[i - 4] && x[i - 1] == x[i - 3])) return true;
                // case 3
                if (i >= 5 && (x[i] >= x[i - 2] - x[i - 4] && x[i - 1] < x[i - 3] 
                    && x[i - 2] > x[i - 4] && x[i - 5] + x[i - 1] >= x[i - 3])) return true;
            }

            return false; 
        }

Delete node in BST

Tags

Solution : Use recursion to do it.

        public TreeNode DeleteNode(TreeNode root, int value)
        {
            if(root == null) return root;

            if (root.val < value)             
            {                 
                root.right = DeleteNode(root.right, value);             
            }             
            else if (root.val > value)
            {
                root.left = DeleteNode(root.left, value);
            }
            else
            {
                if (root.left == null)
                {
                    return root.right;
                }
                else
                {
                    var pre = root.left;
                    while (pre != null && pre.right != null)
                    {
                        pre = pre.right;
                    }

                    root.val = pre.val;
                    root.left = DeleteNode(root.left, pre.val);
                }
            }

            return root;
        }

LeetCode OJ(C#) – Longest Increasing Subsequence

Tags

,

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Solution 1: dynamic programming solution. use dp[i] to indicate longest increasing subsequence end at i. so for each item i, scan all the previous dp[j] and find the max dp[j] + 1 where nums[j] < nums[i].

        public int LengthOfLIS(int[] nums)
        {
            if (nums == null || nums.Length == 0) return 0;
            var dp = new int[nums.Length];

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

            return dp.Max();
        }

Solution 2: see here for explanation.

    public int LengthOfLIS(int[] nums) {
        if (nums == null || nums.Length == 0) return 0;
        var orderednum  = new List();

        foreach (var num in nums)
        {
            var index = orderednum.BinarySearch(num);
            if (index < 0) index = -(index + 1);

            if(index == orderednum.Count) orderednum.Add(num);
            else orderednum[index] = num;
        }

        return orderednum.Count;
    }

Longest common substring, longest common subsequence problem, longest palindromic subsequence

Tags

They can both solved by dynamic programming. see Wiki for longest common sub-string and wiki for longest common sub-sequence problem.

Solution : use dynamic programming.

        public int LCSubstring(string s1, string s2)
        {
            var res = 0;
            var len1 = s1.Length;
            var len2 = s2.Length;

            var dp = new int[len1, len2];
            for (int i = 0; i < len1; i++)
            {
                for (int j = 0; j < len2; j++)
                {
                    if (s1[i] == s2[j])
                    {
                        if (i == 0 || j == 0)
                        {
                            dp[i, j] = 1;
                        }
                        else
                        {
                            dp[i, j] = dp[i - 1, j - 1] + 1;
                        }

                        res = Math.Max(res, dp[i, j]);
                    }
                    else
                    {
                        dp[i, j] = 0;
                    }
                }
            }

            return res;
        }
        public int LCSubsequence(string s1, string s2)
        {
            var len1 = s1.Length;
            var len2 = s2.Length;

            var dp = new int[len1 + 1, len2 + 1];
            for (int i = 1; i <= len1; i++)
            {
                for (int j = 1; j <= len2; j++)
                {
                    if (s1[i - 1] == s2[j - 1])
                    {
                        dp[i, j] = dp[i - 1, j - 1] + 1;
                    }
                    else
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                    }
                }
            }

            return dp[len1, len2];
        }
        public int LPS(string s)
        {
            var len = s.Length;

            var dp = new int[len, len];
            for (int i = 0; i < len; i++)
            {
                dp[i, i] = 1;
            }

            for (int l = 2; l <= len; l++)
            {
                for (int i = 0; i < len - l + 1; i++)
                {
                    var j = i + l - 1;
                    if (s[i] == s[j])
                    {
                        dp[i, j] = dp[i + 1, j - 1] + 2;
                    }
                    else
                    {
                        dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
                    }
                }
            }

            return dp[0, len - 1];
        }

LeetCode OJ(C#) – Count Inversions in an array

Tags

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Solution 1: brute force solution, for each of element, scan the rest the of array to see how many value <= current value. time complexity is O(n^2).

Solution 2: Using BST to do it, each node in the BST has the left count information. So we can search how many values greater than current value in O(lgn) time. So the time complexity time reduce to O(nlgn), space complexity is O(n).

        public int InversionCount2(int[] arr)
        {
            var res = 0;
            var bst = new BSTWithCount();
            for (int i = 0; i < arr.Length; i++)
            {
                res += i - bst.Search(arr[i]);
                bst.Insert(arr[i]);
            }

            return res;
        }

Solution 3: we can still do better by using merge sort,  whenever merge two arrays, we can easily know how many values greater than the current value.

        public int InversionCount(int[] arr)
        {
            return Helper(arr, 0, arr.Length - 1);
        }

        private int Helper(int[] arr, int low, int high)
        {
            var count = 0;
            if (high > low)
            {
                var mid = (high - low)/2 + low;
                count += Helper(arr, low, mid);
                count += Helper(arr, mid + 1, high);

                count += Merge(arr, low, mid + 1, high);
            }

            return count;
        }

        private int Merge(int[] arr, int low, int mid, int high)
        {
            int count = 0;
            var tmp = new List();
            int i = low, j = mid;
            while (i < mid && j <= high)
            {
                if (arr[i] <= arr[j])
                {
                    tmp.Add(arr[i]);
                    i++;
                }
                else
                {
                    count += (mid - i);
                    tmp.Add(arr[j]);
                    j++;
                }
            }

            while (i < mid)
            {
                tmp.Add(arr[i++]);
            }

            while (j <= high)
            {
                tmp.Add(arr[j++]);
            }

            var start = low;
            foreach (var value in tmp)
            {
                arr[start++] = value;
            }

            return count;
        }

LeetCode OJ(C#) – Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution 1: DFS solution

        public int CountComponents(int n, int[,] edges)
        {
            int count = 0;
            var visited = new bool[n];
            var dict = new Dictionary<int, List>();
            for (int i = 0; i < n; i++)
            {
                dict[i] = new List();
            }

            for (int i = 0; i < edges.GetLength(0); i++)
            {
                var from = edges[i, 0];
                var to = edges[i, 1];

                dict[from].Add(to);
                dict[to].Add(from);
            }

            for (int i = 0; i < n; i++)
            {
                if (!visited[i])
                {
                    CountComponentsHelper(n, dict, i, visited);
                    count++;
                }                
            }

            return count;
        }
        private void CountComponentsHelper(int n, Dictionary<int, List> dict, int cur, bool[] visited)
        {
            if (visited[cur]) return;

            visited[cur] = true;

            foreach (var edge in dict[cur])
            {
                CountComponentsHelper(n, dict, edge, visited);
            }
        }

Solution 2: BFS solution

        private void CountComponentsHelper2(int n, Dictionary<int, List> dict, int cur, bool[] visited)
        {
            if (visited[cur]) return;

            var queue = new Queue();
            queue.Enqueue(cur);

            while (queue.Any())
            {
                var size = queue.Count;
                for (int i = 0; i < size; i++)
                {
                    var top = queue.Dequeue();
                    if (!visited[top])
                    {
                        visited[top] = true;
                        foreach (var edge in dict[top])
                        {
                            queue.Enqueue(edge);
                        }
                    }
                }
            }
        }

Solution 3: Union Find solution

        public int CountComponents2(int n, int[,] edges)
        {
            var index = Enumerable.Range(0, n).ToList();

            for (int i = 0; i < edges.GetLength(0); i++)
            {
                var from = edges[i, 0];
                var to = edges[i, 1];

                Union(index, from, to);
            }

            var count = 0;
            var rootset = new HashSet();
            for (int i = 0; i < n; i++)
            {
                if (rootset.Add(FindRoot(index, i)))
                {
                    count ++;
                }
            }

            return count;
        }

        private void Union(List index, int fr, int to)
        {
            var frRoot = FindRoot(index, fr);
            var toRoot = FindRoot(index, to);
            index[toRoot] = index[frRoot];
        }

        private int FindRoot(List index, int i)
        {
            while (index[i] != i)
            {
                i = index[i];
            }

            return i;
        }

LeetCode OJ(C#) – Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Solution :  if root.val > p.val; root can be possible answer, store it and go left

if root.val <= p.val; root can not be answer, go right.

    public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode res = null;
        while (root != null)
        {
            if(root.val <= p.val)
            {
                root = root.right;
            }
            else
            {
                res = root;
                root = root.left;
            }
        }

        return res;
    }

LeetCode OJ(C#) – N-Queens II

Tags

, ,

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Solution : use back trace. every time, add that point to the queens list. check if it is a solution. after that, remove that point from the queens list.

        private int totalNumber = 0;
        public int TotalNQueens(int n)
        {
            var queens = new List<Tuple<int, int>>();

            TotalNQueensRecursion(n, queens);

            return totalNumber;
        }

        private void TotalNQueensRecursion(int n, List<Tuple<int, int>> queens)
        {
            if (queens.Count == n)
            {
                totalNumber++;
                return;
            }

            for (int i = 0; i < n; i++)
            {
                if (queens.Count != i)
                {
                    continue;
                }

                for (int j = 0; j < n; j++)
                {
                    if (canAdd(queens, i, j))
                    {
                        queens.Add(new Tuple<int, int>(i, j));
                        TotalNQueensRecursion(n, queens);
                        queens.Remove(new Tuple<int, int>(i, j));
                    }
                }
            }
        }

        private bool canAdd(List<Tuple<int, int>> queens, int i, int j)
        {
            foreach (var queen in queens)
            {
                // check if it is in same row
                if (queen.Item1 == i)
                {
                    return false;
                }

                // check if it is in same column
                if (queen.Item2 == j)
                {
                    return false;
                }
                
                // check if it is same slope
                if (Math.Abs(queen.Item1 - i) == Math.Abs(queen.Item2 - j))
                {
                    return false;
                }
            }

            return true;
        }

LeetCode OJ(C#) – Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Solution : it can be solved by comparing the root value with p node value and q node value.

  • p value and q value are both less than root value, go to root.left
  • p value and q value are both large than root value, go to root.right
  • otherwise, return root
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        if (p.val < root.val && q.val < root.val) return LowestCommonAncestor(root.left, p, q);         
        if (p.val > root.val && q.val > root.val) return LowestCommonAncestor(root.right, p, q);
        return root;      
    }