Friday, January 29, 2021

[LeetCode] Pacific Atlantic Water Flow

Problem: Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).


Approach: Let's just solve a subproblem first, what if only one ocean was given. How would we have solved this question then. If you see the water can flow from one cell to another connected cell if the height of the next cell is less than the current cell. If you look closely, its a graph where one node node1(i, j) is connected to another node node2(k, l) if matrix[i][j] <= matrix[k][l] and k = i + 1 or k = i - 1 and j = l or k = i and l = j + 1 or l = j - 1.

Once we build the graph, we can apply DFS to see whether there is a path exist from cell (i, j) to (0, 0) or not. If yes then we can say that from (i, j) water can flow to pacific.

Now given that we have two oceans here. What we can do is we can maintain two 2D Boolean tables of size m x n to say pacific and atlantic. pacific[i][j] will be true only if there is a path exist from (i, j) to (0, 0) that is water can flow to pacific and atlantic[i][j] will be true only if there is a path exist from (i, j) to (m-1, n-1) that is water can flow to atlantic.

In the end we can just return the all the cells (i, j) where pacific[i][j] and atlantic[i][j] are true.


Implementation in C#:

        public static IList<IList<int>> PacificAtlantic(int[][] matrix)

        {

            List<IList<int>> result = new List<IList<int>>();

            int numRows = matrix.Length;

            if (numRows == 0)

            {

                return result;

            }

            int numCols = matrix[0].Length;

            bool[,] pacific = new bool[numRows, numCols];

            bool[,] atlantic = new bool[numRows, numCols];

            

            // Top and Bottom boundary

            for (int col = 0; col < numCols; ++col)

            {

                PacificAtlanticDFS(matrix, 0, col, matrix[0][col], pacific);

                PacificAtlanticDFS(matrix, numRows - 1, col, matrix[numRows - 1][col], atlantic);

            }


            // Left and right boundary

            for (int row = 0; row < numRows; ++row)

            {

                PacificAtlanticDFS(matrix, row, 0, matrix[row][0], pacific);

                PacificAtlanticDFS(matrix, row, numCols - 1, matrix[row][numCols - 1], atlantic);

            }

            for (int i = 0; i < numRows; ++i)

            {

                for(int j = 0; j < numCols; ++j)

                {

                    if (pacific[i, j] && atlantic[i, j])

                    {

                        List<int> point = new List<int>();

                        point.Add(i);

                        point.Add(j);

                        result.Add(point);

                    }

                }

            }

            return result;

        }


        private static void PacificAtlanticDFS(int[][] matrix, int row, int col, int prevHeight, bool[,] ocean)

        {

            if (row < 0 

                || row >= matrix.Length

                || col < 0

                || col >= matrix[0].Length

                || matrix[row][col] < prevHeight

                || ocean[row, col])

            {

                return;

            }

            ocean[row, col] = true;

            PacificAtlanticDFS(matrix, row + 1, col, matrix[row][col], ocean);

            PacificAtlanticDFS(matrix, row - 1, col, matrix[row][col], ocean);

            PacificAtlanticDFS(matrix, row, col + 1, matrix[row][col], ocean);

            PacificAtlanticDFS(matrix, row, col - 1, matrix[row][col], ocean);

        }


Complexity: O(m*n) where m = number of rows, n = number of columns

[LeetCode] Construct Quad Tree

Problem: Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid. Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer. 

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

  • val: True if the node represents a grid of 1's or False if the node represents a grid of 0's. 
  • isLeaf: True if the node is leaf node on the tree or False if the node has the four children.

class QuadTreeNode {
    public boolean val;
    public boolean isLeaf;
    public QuadTreeNode topLeft;
    public QuadTreeNode topRight;
    public QuadTreeNode bottomLeft;
    public QuadTreeNode bottomRight;
}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

  1. If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
  2. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
  3. Recurse for each of the children with the proper sub-grid.


If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example:

Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
Input: grid = [[1,1],[1,1]]
Output: [[1,1]]
Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output: [[0,1],[1,1],[1,0],[1,0],[1,1]]

Constraints:

  • n == grid.length == grid[i].length
  • n == 2^x where 0 <= x <= 6


Approach: The approach is straight forward. We are going to use recursion here. You can just look at the implementation to understand the approach.

Implementation in C#:

        public QuadTreeNode Construct(int[][] grid)

        {

            return BuildQuadTree(grid, 0, 0, grid.Length);

        }


        private QuadTreeNode BuildQuadTree(int[][] grid, int row, int col, int length)

        {

            QuadTreeNode qNode = new QuadTreeNode();

            int sum = 0;

            for (int i = row; i < row + length; ++i)

            {

                for (int j = col; j < col + length; ++j)

                {

                    sum += grid[i][j];

                }

            }

            if (sum == length * length) // All 1s

            {

                qNode.isLeaf = true;

                qNode.val = true;

            }

            else if (sum == 0) // All 0s

            {

                qNode.isLeaf = true;

            }

            else

            {

                int halfLength = length / 2;

                qNode.topLeft = BuildQuadTree(grid, row, col, halfLength);

                qNode.topRight = BuildQuadTree(grid, row, col + halfLength, halfLength);

                qNode.bottomLeft = BuildQuadTree(grid, row + halfLength, col, halfLength);

                qNode.bottomRight = BuildQuadTree(grid, row + halfLength, col + halfLength, halfLength);

            }

            return qNode;

        }


Complexity: O(n^4)

Convert Decimal Number to Hexadecimal

Problem: Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Example:

Input:
18

Output:
"12"3
Input:
-2

Output:
"fffffffe"


Approach: Basically we will convert every 4 bits to appropriate hexadecimal digit. We can use 0xF mask to get these four bits and then we will right shift the number by 4. We will do it till the given number becomes 0.

The only problem with this approach is the negative number as while shifting right the system adds 1 to fill the left part. Because of it we can have an infinite loop. We can use a count variable to solve this problem as if you see we are right shifting by 4 bits so at max we need to right shift (32/4=) 8 times or sizeof(int) * 2 times.

That's all! 


Implementation in C#:

        public static string ToHex(int num)

        {

            if (num == 0)

            {

                return "0";

            }

            string result = string.Empty;

            int count = 0; // To handle negative numbers

            while (num != 0 && count < 8)

            {

                ++count;

                int targetNum = num & 0xf;

                result = GetHexDigit(targetNum) + result;

                num >>= 4;

            }

            return result;

        }


        private static char GetHexDigit(int num)

        {

            if (num >= 0 && num <= 9)

            {

                return (char)(num + '0');

            }

            return (char)((num - 10) + 'a');

        }


Complexity: O(num of bits)

[LeetCode] Number of Boomerangs

Problem: You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters). Return the number of boomerangs.

Example:

Input: points = [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].
Input: points = [[1,1],[2,2],[3,3]]
Output: 2
Input: points = [[1,1]]
Output: 0


Approach: This problem is straight forward to solve. Basically we take every point in points one by one and calculate it's distance from every other point. Whenever we got number of points >= 2 for a particular distance, we know that we get nP2(order does matter) boomerangs. We can use hashing to maintain number of points for a particular distance.


Implementation in C#:

        public int NumberOfBoomerangs(int[][] points)

        {

            int result = 0;

            for(int i = 0; i < points.Length; ++i)

            {

                Dictionary<int, int> distances = new Dictionary<int, int>();

                for (int j = 0; j < points.Length; ++j)

                {

                    if (i != j)

                    {

                        int distance = (int)(Math.Pow(points[j][0] - points[i][0], 2) + Math.Pow(points[j][1] - points[i][1], 2));

                        if (!distances.ContainsKey(distance))

                        {

                            distances.Add(distance, 0);

                        }

                        ++distances[distance];

                    }

                }

                foreach(int distance in distances.Keys)

                {

                    int count = distances[distance];

                    result += count * (count - 1);

                }

            }

            return result;

        }


Complexity: O(n^2)

Thursday, January 28, 2021

Delete a node of BST

Problem: Given a Binary Search Tree and a value key. Remove the node from tree whose value is equal to the given key.


Approach: You can refer the Binary Search Tree section for approach. I am just giving implementation in C#.


Implementation in C#:

        public void Remove(int key)

        {

            if (this.Root != null)

            {

                this.Root = this.RemoveNode(this.Root, key);

            }

        }


        private BinaryTreeNode RemoveNode(BinaryTreeNode node, int key)

        {

            if (node == null)

            {

                return null;

            }

            if (key < node.Value)

            {

                node.LeftNode = this.RemoveNode(node.LeftNode, key);

            }

            else if (key > node.Value)

            {

                node.RightNode = this.RemoveNode(node.RightNode, key);

            }

            else

            {

                if (node.RightNode == null)

                {

                    return node.LeftNode;

                }

                else if (node.LeftNode == null)

                {

                    return node.RightNode;

                }

                else 

                {

                    node.Value = this.FindMin(node.RightNode);

                    node.RightNode = this.RemoveNode(node.RightNode, node.Value);

                }

            }

            return node;

        }


        private int FindMin(BinaryTreeNode node)

        {

            while(node.LeftNode != null)

            {

                node = node.LeftNode;

            }

            return node.Value;

        }


Complexity: O(h) where h is height of the tree

Add two numbers represented by LinkedList

Problem: You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. 

Note: The two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (1 -> 2 -> 3 -> 4) + (5 -> 6 -> 7)
Output: 1 -> 8 -> 0 -> 1


Approach: We can solve it recursively but I am using two stacks here. Approach is straight forward and can be understood by just looking at the implementation.


Implementation in C#:

    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) 

    {

        Stack<int> l1Stack = new Stack<int>();

        Stack<int> l2Stack = new Stack<int>();

        while(l1 != null)

        {

            l1Stack.Push(l1.val);

            l1 = l1.next;

        }

        while(l2 != null)

        {

            l2Stack.Push(l2.val);

            l2 = l2.next;

        }        

        ListNode head = null;        

        int carry = 0;

        while(l1Stack.Count > 0 && l2Stack.Count > 0)

        {

            int l1Num = l1Stack.Pop();

            int l2Num = l2Stack.Pop();

            int result = l1Num + l2Num + carry;

            head = new ListNode(result % 10, head);

            carry = result / 10;

        }        

        if (l1Stack.Count > 0)

        {

            AddSingleNumWithCarry(l1Stack, ref head, carry);        

        }

        else if (l2Stack.Count > 0)

        {

            AddSingleNumWithCarry(l2Stack, ref head, carry); 

        }

        else if (carry > 0)

        {

            AddSingleNumWithCarry(null, ref head, carry);

        }        

        return head;        

    }

    

    private void AddSingleNumWithCarry(Stack<int> stack, ref ListNode head, int carry)

    {

        if (stack != null)

        {

            while (stack.Count > 0)

            {

                int result = stack.Pop() + carry;

                head = new ListNode(result % 10, head);

                carry = result / 10;

            }

        }        

        if (carry > 0)

        {

            head = new ListNode(carry, head);

        }

    }


Complexity: O(n)

[LeetCode] Smallest String With A Given Numeric Value

Problem: The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters' numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.
Input: n = 5, k = 73
Output: "aaszz"


Approach: To get the smallest string we know that we need to have as small values as possible in the beginning of the string. For example, for n = 3 and k = 27, "aay" and "abx" both are valid string but "aay" is smallest because it has "aa" in the begining.

With the above thought, we can come up with a greedy approach where we will put the maximum value possible at the end. That's all about the approach.

 

Implementation in C#:

        public static string GetSmallestString(int n, int k)

        {

            char[] result = new char[n];

            Array.Fill(result, 'a'); // We have the smallest string possible

            k -= n;

            while(k != 0)

            {

                int value = Math.Min(k, 25); // Maximum possible

                result[--n] += (char)value;

                k -= value;

            }

            return new string(result);

        }


Complexity: O(n)

Wednesday, January 27, 2021

String compression

Problem: Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

  • If the group's length is 1, append the character to s.
  • Otherwise, append the character followed by the group's length.

We need to modify the input array itself. After you are done with modifications, return the new length of the array.

Example:

Input: chars = ["a","a","b","b","b","b","b"]
Output: Return 4 as the first 4 characters of input array will become: ["a","2","b","5"]
Explanation: The groups are "aa" and "bbbbb". This compresses to "a2b5".


Approach: Approach is straight forward. We are using two pointers here one is for read and second is for write. You can understand the approach by just looking at the implementation.


Implementation in C#:

        public int Compress(char[] chars)

    {
        int length = chars?.Length ?? 0;
        if (length <= 1)
        {
            return length;
        }
        int currCharCount = 1;
        int writeIndex = 1;
        for (int i = 1; i < length; ++i)
        {
            if (chars[i] == chars[i - 1])
            {
                ++currCharCount;
            }
            else
            {
                if (currCharCount > 1)
                {
                    this.AddCountToResult(chars, ref writeIndex, currCharCount);
                }
                currCharCount = 1;
                chars[writeIndex++] = chars[i];
            }
        }
        if (currCharCount > 1)
        {
            this.AddCountToResult(chars, ref writeIndex, currCharCount);
        }
        return writeIndex;
    }

    private void AddCountToResult(char[] chars, ref int writeIndex, int currCharCount)
    {
        string countStr = currCharCount.ToString();
        for (int j = 0; j < countStr.Length; ++j)
        {
            chars[writeIndex++] = countStr[j];
        }
    }


Complexity: O(n)

Find All Duplicates in an Array

Problem: Given an array of integers arr, 1 ≤ arr[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array.

Example:

Input:
[1,4,2,2,5,1]

Output:
[1,2]


Approach: We can use sorting, we can use hashing to solve this problem easily. Here is another method using which we can solve this problem in linear time without using extra space:

We can use the fact that all elements will be in the range (1, n), so if you see we can use our input array for hashing. Following is the idea:

index = Abs(arr[i]) - 1

arr[index] = -arr[index]

Now if you see if we find arr[index] which is already negative, we came to know that this index has come before so we can add index + 1 to the result.


Implementation in C#:

    public IList<int> FindDuplicates(int[] nums) 

    {

        List<int> result = new List<int>();        

        for (int i = 0; i < nums.Length; ++i)

        {

            int index = Math.Abs(nums[i]) - 1;

            if (nums[index] < 0)

            {

                result.Add(index + 1);

            }

            else

            {

                nums[index] = -nums[index];

            }

        }

        return result;

    }


Complexity: O(n)

K-th Smallest in Lexicographical Order

Problem: Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Example:

Input:
n: 14   k: 8

Output:
3

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9], so the 8th smallest number is 3.


Approach: First approach which directly come to mind is create an array of size n, insert numbers 1...n,  sort the array in lexicographical Order and just return element at the (k - 1)th index. This will surely work but it will be expensive in terms of time. It will take at least nlogn time given string comparison is taking constant time.

Let's think about this problem differently. If you look closely this is kind of forming a tree which each node is having <= 10 children. For our example, the tree will look like following:


Once we understood its structure, we can see we can apply DFS to to solve this question. That's all!


Implementation in C#:

        public static int FindKthNumber(int n, int k)

        {

            return (int)FindKthNumberDFS(1, n, k);

        }


        private static long FindKthNumberDFS(long start, long end, long k)

        {

            if (k == 1)

            {

                return start;

            }

            long childrenCount = GetNumberOfChildren(start, end);

            return childrenCount < k ? FindKthNumberDFS(start + 1, end, k - childrenCount) : FindKthNumberDFS(start * 10, end, k - 1);

        }


        private static long GetNumberOfChildren(long start, long end)

        {

            long rightSibling = start + 1;

            long childrenCount = 0;

            while(start <= end)

            {

                childrenCount += Math.Min(end + 1, rightSibling) - start;

                start *= 10;

                rightSibling *= 10;

            }

            return childrenCount;

        }


Complexity: O(logn)

[Uber][LeetCode] Find All Anagrams in a String

Problem: Given a string s and a non-empty pattern p, find all the start indices of p's anagrams in s.

Example:

Input:
s: "abca" p: "abc"

Output:
[0, 1]

Explanation:
The substring with start index = 0 is "abc", which is an anagram of "abc".
The substring with start index = 2 is "bca", which is an anagram of "abc".


Approach: We can use sliding window approach here. We can maintain a hash of pattern p with key as characters in p and value as frequencies of those characters. We also have to maintain the unique character counts to verify if actually an anagram is found or not. 

Rest of the approach, you can understand by just looking at the code.


Implementation in C#:

        public IList<int> FindAnagrams(string s, string p)

        {

            Dictionary<char, int> pCountDict = new Dictionary<char, int>();           

            foreach(char ch in p)

            {

                if (!pCountDict.ContainsKey(ch))

                {

                    pCountDict.Add(ch, 0);

                }

                ++pCountDict[ch];

            }

            int uniqueCharcount = pCountDict.Count;

            int start = 0, end = 0;

            List<int> result = new List<int>();

            while (end < s.Length)

            {

                if (pCountDict.ContainsKey(s[end]))

                {

                    --pCountDict[s[end]];

                    if (pCountDict[s[end]] == 0)

                    {

                        --uniqueCharcount;

                    }

                }

                if (end - start + 1 == p.Length)

                {

                    if (uniqueCharcount == 0)

                    {

                        result.Add(start);

                    }

                    if (pCountDict.ContainsKey(s[start]))

                    {

                        ++pCountDict[s[start]];

                        if (pCountDict[s[start]] == 1)

                        {

                            ++uniqueCharcount;

                        }

                    }

                    ++start;

                }

                ++end;

            }

            return result;

        }


Another Implementation:

        public IList<int> FindAnagrams1(string s, string p)

        {

            if (s?.Length < p?.Length)

            {

                return new List<int>();

            }

            int[] pCount = new int[26];

            int[] sCount = new int[26];

            for (int i = 0; i < p.Length; ++i)

            {

                ++pCount[p[i] - 'a'];

                ++sCount[s[i] - 'a'];

            }

            var result = new List<int>();

            if (pCount.SequenceEqual(sCount))

            {

                result.Add(0);

            }

            int start = 0;

            for (int i = p.Length; i < s.Length; ++i)

            {

                --sCount[s[start++] - 'a'];

                ++sCount[s[i] - 'a'];

                if (pCount.SequenceEqual(sCount))

                {

                    result.Add(start);

                }

            }

            return result;

        }


Complexity: O(n)

Find number of paths whose sum is equal to K in a Binary Tree

Problem: You are given a binary tree in which each node contains an integer value positive or negative. Find the number of paths that sum to a given value K. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Example:

K = 3

      1
     /  \
    2   -3
   / \    \
  7  -3    5
       \
        4

Return 3. The paths that sum to 3 are:

1 -> 2
2 -> -3 -> 4
1 -> -3 -> 5


Approach: We can solve it using Pre-Order traversal with hashing. Just look at the implementation to understand the approach. It's fairly straight forward.

 

Implementation in C#:

        public int PathSum(TreeNode root, int targetSum)

    {
        if (root == null)
        {
            return 0;
        }
        var sumMap = new Dictionary<long, int>();
        sumMap[0] = 1;
        return this.FindNumOfPaths(root, targetSum, 0, sumMap);
    }

    private int FindNumOfPaths(TreeNode node,
                               int targetSum,
                               long currSum,
                               Dictionary<long, int> sumMap)
    {
        if (node == null)
        {
            return 0;
        }
        currSum += node.val;
        int numOfPaths = 0;
        if (sumMap.ContainsKey(currSum - targetSum))
        {
            numOfPaths += sumMap[currSum - targetSum];
        }
        if (!sumMap.ContainsKey(currSum))
        {
            sumMap[currSum] = 0;
        }
        ++sumMap[currSum];
        numOfPaths += this.FindNumOfPaths(node.left,
                                         targetSum,
                                         currSum,
                                         sumMap) +
                      this.FindNumOfPaths(node.right,
                                         targetSum,
                                          currSum,
                                          sumMap);
        // This node is no more in the path
        --sumMap[currSum];
        if (sumMap[currSum] == 0)
        {
            sumMap.Remove(currSum);
        }
        return numOfPaths;
    }


Complexity: O(n)

[LeetCode] Find Right Interval

Problem: You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.
Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.


Approach: We can apply brute force approach by comparing every interval with each other but it will take O(n^2) time. If you see we need to find start time efficiently so what we can do is we can sort the intervals based on the start time and then we can apply binary search for every end time. 

The problem is if we apply the sorting we will loose our original index so what we can do is we can take another 2D array which will contain the start times and the original index. Then we can sort this new array based on the start times. 

That's all! Please note that in the implementation I am using Tuple instead of 2D array.


Implementation in C#:

        public static int[] FindRightInterval(int[][] intervals)

        {

            Tuple<int, int>[] sortedIntervals = new Tuple<int, int>[intervals.Length];

            for (int i = 0; i < intervals.Length; ++i)

            {

                sortedIntervals[i] = new Tuple<int, int>(intervals[i][0], i);

            }

            Array.Sort(sortedIntervals, (sI1, sI2) =>

            {

                return sI1.Item1.CompareTo(sI2.Item1);

            });

            int[] result = new int[intervals.Length];

            for (int i = 0; i < intervals.Length; ++i)

            {

                result[i] = FindRightIntervalBinarySearch(intervals[i][1], sortedIntervals);

            }

            return result;

        }


        private static int FindRightIntervalBinarySearch(int value, Tuple<int, int>[] sortedIntervals)

        {

            if (sortedIntervals[sortedIntervals.Length - 1].Item1 < value)

            {

                return -1;

            }

            int start = 0, end = sortedIntervals.Length - 1;

            while(start <= end)

            {

                int mid = start + (end - start) / 2;

                if (sortedIntervals[mid].Item1 >= value)

                {

                    end = mid - 1;

                }

                else

                {

                    start = mid + 1;

                }

            }

            return sortedIntervals[start].Item2;

        }


Complexity: O(nlogn)

[LeetCode] Concatenation of Consecutive Numbers

Problem: Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9 + 7.

Example:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11". After concatenating them, we have "11011", which corresponds to the decimal value 27.


Approach: We are going to use the approach which we took in our previous problem of Concatenating binary representation of two numbers. Let's take an example say n = 3 to understand the approach. 

n = 1 then answer is obviously 1

n = 2  what we will do is we will left shift answer by number of bits in 2 and add 2 in the answer so answer will be 1 * 2 ^ 2 + 2 = 6

n = 3, 6 * 2^2 + 3 = 27

answer = previous_answer * 2 ^ (num_of_bits_in_current_number) + current_number 

This is the core logic obviously we need to take modulo of 10^9 + 7 which is given to avoid overflow. 

That's all!


Implementation in C#:

        public int ConcatenatedBinary(int n)

        {

            ulong result = 0;

            ulong modValue = 1000000007;

            int numOfBits = 1;            

            for (ulong i = 1; i <= (ulong)n; ++i)

            {

                result = (((result << numOfBits) % modValue) + i) % modValue;

                if ((i & (i + 1)) == 0)

                {

                    ++numOfBits;

                }

            }

            return (int)result;

        }


Complexity: O(n)

Concatenation of binary representation of two numbers

Problem: Given two integers x and y the task is to find the number formed by concatenating the binary equivalents of x and y.

Example:

Input: x = 1, y = 2
Output: 6
Explanation: 1's in binary representation is 1 and 2's binary representation is 10. After concatenation it will become 110 which is 6.   


Approach: We can binary shift the x with the number of bits in y and then OR it with y. Say x is 1 and y is 2. The number of bits in y is 2. So we will shift x by 2. Now x will become:

x << 2 = 1 << 2 = 100

x OR y = 100 OR 10 = 110 = 6


Implementation in C#:

        public int Concat(int x, int y)

        {

            int numOfBits = this.NumOfBits(y);

            x <<= numOfBits;

            return x | y;

        }


        private int NumOfBits(int num)

        {

            int numOfBits = 0;

            while(num != 0)

            {

                num /= 2;

                ++numOfBits;

            }

            return numOfBits;

        }


Complexity: O(log(y))

Monday, January 25, 2021

[Google Question] Non-overlapping interval

Problem: Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example:

Input: [[1,2],[2,3],[2,4]]
Output: 1
Explanation: [2,3] or [2,4] can be removed to make intervals non-overlapping.


Approach: We can sort the intervals based on start point of interval. Once we sort this array, the problem becomes simpler. We can maintain two pointers compareIndex and iterator. \ We can then follow below steps:

  • result = 0
  • compareIndex = 0;
  • FOR iterator = 1 to n
    • IF intervals[compareIndex ][1] > intervals[iterator ][0] // overlap
      • result = result + 1
      • IF intervals[compareIndex ][1] > intervals[iterator ][1] // Remove the record with bigger end
        • compareIndex = iterator
    • ELSE
      • compareIndex = iterator
  • RETURN result

That's all!


Implementation in C#:

    public int EraseOverlapIntervals(int[][] intervals) 

    {

        if (intervals?.Length <=  1)

        {

            return 0;

        }

        Array.Sort(intervals, (i1, i2) => {

           return i1[0].CompareTo(i2[0]);

        });

        int compareIndex = 0;

        int count = 0;                

        for (int i = 1; i < intervals.Length; ++i)

        {

            if (intervals[compareIndex][1] > intervals[i][0])

            {

                ++count;

                if (intervals[compareIndex][1] > intervals[i][1])

                {

                    compareIndex = i;

                }

            }

            else

            {

                compareIndex = i;

            }

        }

        return count;

    }


Complexity: O(nlogn)

Design Data Structure with increment, decrement, max and min at O(1)

Problem: Implement a data structure supporting the following operations:

  • Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
  • Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
  • GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string.
  • GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string.


Approach: We can solve this problem using hash and Doubly Linked List. We can maintain three members:

  1. LinkedList<int> countList : It will maintain all the unique counts in sorted order.
  2. Dictionary<int, HashSet<string>> buckets: This will maintain buckets of strings corresponding to their count. 
  3. Dictionary<string, LinkedListNode<int>> keyValueHash: This is our primary hash which will contain the input string as key and value as the node of countList with the count of the input string.

For example if "A"'s value is 4, "B"'s value is 4 and "C"'s value is 2 then 

countList: [{Node1}: 2] -> [{Node2}: 4] // Node1 and Node2 are address of the node 

buckets: {{4 => "A", "B}, {2 => "C"}}

keyValueHash: {{"A" => Node2},  {"B" => Node2}, {"C" => Node1}}

Now let's see the algorithm of the methods, we need to support:

1. Inc(key) : 

  • IF key does not exist in keyValueHash
    • IF buckets does not contains 1
      • countList.AddAtFirst(1)
    • buckets[1].Add(key)
    • keyValueHash[key] = countList.Head
  • ELSE
    • node = keyValueHash[key]
    • oldCount = node.Value
    • newCount = oldCount  + 1
    • IF buckets does not contain newCount
      • countList.AddAfter(node, newCount) // Maintaining sorted order
    • buckets[newCount].Add(key)
    • keyValueHash[key] = node.Next
    • buckets[oldCount].Remove(key)
    • IF buckets[oldCount] is empty
      • buckets.Remove(oldCount)
      • countList.Remove(node)

2. Dec(key):

  • IF key does not exits in keyValueHash
    • RETURN
  • ELSE
    • node = keyValueHash[key]
    • oldCount = node.Value
    • newCount = oldCount - 1
    • IF newCount > 0 // We need to remove the key if count becomes 0
      • IF buckets does not contain newCount
        • countList.AddBefore(node, newCount) // Maintaining sorted order
      • buckets[newCount].Add(key)
      • keyValueHash[key] = node.Prev
    • buckets[oldCount].Remove(key)
    • IF buckets[oldCount] is empty
      • buckets.Remove(oldCount)
      • countList.Remove(node)
    • IF newCount is 0
      • keyValueHash.Remove(key)

3. GetMax():

  • IF countList is empty:
    • RETURN empty string
  • ELSE
    • RETURN buckets[value at tail of countList].First
4. GetMin()

  • IF countList is empty:
    • RETURN empty string
  • ELSE
    • RETURN buckets[value at head of countList].First


Implementation in C#:

    public class AllOne

    {

        private Dictionary<string, LinkedListNode<int>> keyValueHash;

        private Dictionary<int, HashSet<string>> buckets;

        private LinkedList<int> countList;


        public AllOne()

        {

            this.keyValueHash = new Dictionary<string, LinkedListNode<int>>();

            this.buckets = new Dictionary<int, HashSet<string>>();

            this.countList = new LinkedList<int>();

        }


        public void Inc(string key)

        {

            if (!this.keyValueHash.ContainsKey(key))

            {

                this.AddKey(key);    

            }

            else

            {

                this.ModifyKey(key);

            }

        }


        private void ModifyKey(string key)

        {

            LinkedListNode<int> node = this.keyValueHash[key];

            int currCount = node.Value;

            int newCount = currCount + 1;

            if (!this.buckets.ContainsKey(newCount))

            {

                this.buckets.Add(newCount, new HashSet<string>());

                this.countList.AddAfter(node, newCount);

            }

            this.buckets[newCount].Add(key);

            this.keyValueHash[key] = node.Next;

            this.buckets[currCount].Remove(key);

            if (this.buckets[currCount].Count == 0)

            {

                this.buckets.Remove(currCount);

                this.countList.Remove(node);

            }

        }


        private void AddKey(string key)

        {

            if (!buckets.ContainsKey(1))

            {

                buckets.Add(1, new HashSet<string>());

                countList.AddFirst(1);

            }

            buckets[1].Add(key);

            this.keyValueHash.Add(key, countList.First);

        }


        public void Dec(string key)

        {

            if (this.keyValueHash.ContainsKey(key))

            {

                this.DecreaseKey(key);

            }

        }


        private void DecreaseKey(string key)

        {

            LinkedListNode<int> node = this.keyValueHash[key];

            int currCount = node.Value;

            int newCount = currCount - 1;

            if (newCount > 0)

            {

                if (!this.buckets.ContainsKey(newCount))

                {

                    this.buckets.Add(newCount, new HashSet<string>());

                    this.countList.AddBefore(node, newCount);

                }

                this.buckets[newCount].Add(key);

                this.keyValueHash[key] = node.Previous;

            }

            this.buckets[currCount].Remove(key);

            if (this.buckets[currCount].Count == 0)

            {

                this.buckets.Remove(currCount);

                this.countList.Remove(node);

            }

            if (newCount == 0)

            {

                this.keyValueHash.Remove(key);

            }

        }


        public string GetMaxKey()

        {

            if (this.countList.Last == null)

            {

                return string.Empty;

            }

            return this.buckets[this.countList.Last.Value].First();

        }


        public string GetMinKey()

        {

            if (this.countList.First == null)

            {

                return string.Empty;

            }

            return this.buckets[this.countList.First.Value].First();

        }

    }


Complexity: O(1) for all operations.

[LeetCode] Minimum Genetic Mutation

Problem: A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

Note:

  1. Starting point is assumed to be valid, so it might not be included in the bank.
  2. If multiple mutations are needed, all mutations during in the sequence must be valid.
  3. You may assume start and end string is not the same.

Example:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1
start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2
start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3


Approach: This problem is similar to Word Ladder where to we need to find the length of shortest transformation sequence from beginWord to endWord. This problem is simpler as substitution character are limited which are A, C, G and T only so we don't need to maintain a hash. We will use BFS here too.


Implementation in C#:

        public static int MinMutation(string start, string end, string[] bank)

        {

            HashSet<string> bankSet = new HashSet<string>(bank);

            bankSet.Remove(start);

            Queue<string> queue = new Queue<string>();

            queue.Enqueue(start);

            char[] geneChars = new char[] { 'A', 'C', 'G', 'T' };

            int count = -1;

            while(queue.Count > 0)

            {

                ++count;

                int size = queue.Count;

                for (int i = 0; i < size; ++i)

                {

                    string currStr = queue.Dequeue();

                    if (currStr == end)

                    {

                        return count;

                    }

                    char[] currStrArr = currStr.ToCharArray();

                    for (int j = 0; j < currStrArr.Length; ++j)

                    {

                        char origChar = currStrArr[j];

                        for (int k = 0; k < geneChars.Length; ++k)

                        {

                            if (origChar == geneChars[k])

                            {

                                continue;

                            }

                            currStrArr[j] = geneChars[k];

                            string newUpdatedString = new string(currStrArr);

                            if (bankSet.Contains(newUpdatedString))

                            {

                                queue.Enqueue(newUpdatedString);

                                bankSet.Remove(newUpdatedString);

                            }

                        }

                        currStrArr[j] = origChar;

                    }

                }


            }

            return -1;

        }


Complexity: O(n * 8 * 4) =  O(32 * n) =~ O(n)