Summary Ranges

Problem: You are given a sorted unique integer array. Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of input array is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in input array.

Each range [a,b] in the list should be output as:

• "a->b" if a != b
• "a" if a == b

Example:

Input: nums = [3,4,5,9,12,13]
Output: ["3->5","9","12->13"]
Explanation: The ranges are:
[3, 5] --> "3->5"
[9, 9] --> "9"
[12, 13] --> "12->13"

Approach: Not much to discuss here. Its a straight forward problem. You can easily understand the solution by looking at the code.

Implementation in C#:

        public static IList<string> SummaryRanges(int[] nums)

        {

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

            if (nums?.Length == 0)

            {

                return result;

            }

            string currRange = nums[0].ToString();

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

            {

                if (nums[i] > nums[i - 1] + 1)

                {

                    if (int.Parse(currRange) != nums[i - 1])

                    {

                        currRange += $"->{nums[i - 1]}";

                    }

                    result.Add(currRange);

                    currRange = nums[i].ToString();

                }

            }

            if (int.Parse(currRange) != nums[nums.Length - 1])

            {

                currRange += $"->{nums[nums.Length - 1]}";

            }

            result.Add(currRange);           

            return result;

        }

Complexity: O(n)

Calculator II

Problem: This problem is similar to our previous Calculator problem with difference here is the expression string contains only non-negative integers, +, -, *, / operators and empty spaces.

Example:

Input: " 4 *3+5 / 2 "
Output: 14

Approach: We will take the same approach which we have taken in the previous problem. We will use the stack only. We just need to take care of precedence of operators here i.e. '*' and '/' are going to be executed first. 

What we can do is we will keep push operands in stack, if there is a '-' operator we will push "-operand" to stack to take care of subtraction . If we see '*' or '/ ' operator then we apply the operation on top of stack and current number and will push the result to stack.

In the end we will add all the number in the stack and that will be our answer.

Implementation in C#:

        public static int CalculateII(string s)

        {

            if (string.IsNullOrWhiteSpace(s))

            {

                return 0;

            }

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

            int operand = 0;

            char operation = '+';

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

            {

                if (char.IsDigit(s[i]))

                {

                    operand = operand * 10 + (s[i] - '0');

                }

                if ((!char.IsDigit(s[i]) && !char.IsWhiteSpace(s[i])) || i == s.Length - 1)

                {

                    if (operation == '+')

                    {

                        stack.Push(operand);

                    }

                    else if (operation == '-')

                    {

                        stack.Push(-operand);

                    }

                    else if (operation == '*')

                    {

                        int operand1 = stack.Pop();

                        stack.Push(operand1 * operand);

                    }

                    else if (operation == '/')

                    {

                        int operand1 = stack.Pop();

                        stack.Push(operand1 / operand);

                    }

                    operation = s[i];

                    operand = 0;

                }

            }

            int result = 0;

            while (stack.Count > 0)

            {

                result += stack.Pop();

            }

            return result;

        }

Complexity: O(n)

Invert a binary tree

Problem: Given the root of a binary tree, invert the tree, and return its root.

Example: 

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Approach: Using Post order traversal (Bottom up approach).

Implementation in C#:

        public void Invert()

        {

            if (this.Root == null)

            {

                return;

            }

            this.Root = this.Invert(this.Root);

        }

        private BinaryTreeNode Invert(BinaryTreeNode node)

        {

            if (node == null)

            {

                return null;

            }

            BinaryTreeNode left = this.Invert(node.LeftNode);

            BinaryTreeNode right = this.Invert(node.RightNode);

            node.LeftNode = right;

            node.RightNode = left;

            return node;

        }

Complexity: O(n)

Implement Stack using Queues

Problem: Implement a stack using queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Approach: A simple approach will be to use two queues say queue1 and queue2. Here are the algorithms for different operations:

• Push: 
• IF queue1.Empty 
• queue1.Enqueue(element)
• WHILE NOT queue2.Empty
• queue1.Enqueue(queue2.Dequeue())
• ELSE IF queue2.Empty
• queue2.Enque(element)
• WHILE NOT queue1.Empty
• queue2.Enqueue(queue1.Dequeue())
• Pop:
• Returns Dequeue of queue1 / queue2 whichever is not empty
• Top:
• Returns Peek of queue1 / queue2 whichever is not empty
• Empty:
• Returns queue1.Empty AND queue2.Empty

That's all and it will work fine. The only problem is here we are using two queues. Can we reduce it? Answer is yes. How? Please look closely on the definition of Push operation, what we are trying to do is to push elements in reverse order using two queues. What if we can do it using one queue only? Here is how we can do it:

• Push: 
• queue.Enqueue(element)
• size = queue.Size
• WHILE size > 1 // Not going to enqueue current element again
• queue.Enqueue(queue.Deque())
• size = size - 1

You see we did the same thing using the same one queue. Rest of the operations are straight forward:

• Pop:
• Returns queue.Deque()
• Top:
• Returns queue.Peek()
• Empty:
• Returns queue.Empty()

Implementation in C#:

    public class MyStack

    {

        public MyStack()

        {

            this.queue = new Queue<int>();

        }

        public void Push(int x)

        {

            this.queue.Enqueue(x);

            int currQSize = this.queue.Count;

            

            // Re push every element except the current

            while(currQSize > 1)

            {

                this.queue.Enqueue(this.queue.Dequeue());

                --currQSize;

            }

        }

       public int Pop()

        {

            if (this.queue.Count > 0)

            {

                return this.queue.Dequeue();

            }

            return -1;

        }

        public int Top()

        {

            if (this.queue.Count > 0)

            {

                return this.queue.Peek();

            }

            return -1;

        }

        public bool Empty()

        {

            return this.queue.Count == 0;

        }

        private Queue<int> queue;

    }

Complexity: O(n) for Push and O(1) for rest of the operations.

Calculator

Problem: Implement a basic calculator to evaluate a simple expression string. The expression string may contain open '(' and closing parentheses ')', the plus '+' or minus sign '-', non-negative integers and empty spaces.

Example:

Input: " (3-1) + 4 - 1"
Output: 5

Approach: The problem description immediately gives hint of using stack. Given we need to evaluate sub expressions too because of parentheses so it looks like we have to delay our processing but if you see we just can't simply use stack as expression may contain '-' and subtraction is neither associative nor commutative i.e. A-B-C != C-B-A and (A-B) - C != A - (B - C).

If we look closely reading the string in reverse will easily solve our problem so here is our algorithm:

• Iterate the expression string in reverse order one character at a time. Since we are reading the expression character by character, we need to be careful when we are reading digits and non-digits.
• The operands could be formed by multiple characters. A string "123" would mean a numeric 123, which could be formed as: 123 >> 120 + 3 >> 100 + 20 + 3. Thus, if the character read is a digit we need to form the operand by multiplying a power of 10 to the current digit and adding it to the overall operand.
• Once we encounter a character which is not a digit, we push the operand onto the stack.
• When we encounter an opening parenthesis (, this means an expression just ended. (reading string in reverse). This calls for evaluation of the expression by popping operands and operators off the stack till we pop corresponding closing parenthesis. The final result of the expression is pushed back onto the stack.
• Push the other non-digits onto to the stack.
• Do this until we get the final result. It's possible that we don't have any more characters left to process but the stack is still non-empty. This would happen when the main expression is not enclosed by parenthesis. So, at the end, we can check if the stack is not empty. If it is, we treat the elements in it as one final expression and evaluate it the same way we would if we had encountered an opening bracket.

Implementation in C#:

        public static int Calculate(string s)

        {

            if (string.IsNullOrWhiteSpace(s))

            {

                return 0;

            }

            Stack<Object> stack = new Stack<object>();

            int operand = 0;

            int pow = 0;

            for (int i = s.Length - 1; i >= 0; --i)

            {

                if (char.IsDigit(s[i]))

                {

                    operand += (int)Math.Pow(10, pow) * (int)(s[i] - '0');

                    ++pow;

                }

                else if (s[i] != ' ')

                {

                    if (pow > 0)

                    {

                        stack.Push(operand);

                        pow = 0;

                        operand = 0;

                    }

                    if (s[i] == '(')

                    {

                        int result = EvaluateExpression(stack);

                        stack.Pop();

                        stack.Push(result);

                    }

                    else

                    {

                        stack.Push(s[i]);

                    }

                }

            }

            if (pow > 0)

            {

                stack.Push(operand);

            }

            return EvaluateExpression(stack);

        }

        private static int EvaluateExpression(Stack<Object> stack)

        {

            int result = 0;

            if (stack.Count > 0)

            {

                result = (int)stack.Pop();

            }

            while (stack.Count > 0 && (char)stack.Peek() != ')')

            {

                char sign = (char)stack.Pop();

                if (sign == '+')

                {

                    result += (int)stack.Pop();

                }

                else

                {

                    result -= (int)stack.Pop();

                }

            }

            return result;

        }

Complexity: O(n)

Given a 2D binary matrix filled with 0's and 1's, return the area of the largest square containing only 1's.

Example (Taken from leetcode):

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Approach: Using DP. We can maintain a 2D table where Table[i][j] will tell the the side length of the maximum square whose bottom right corner is the cell with index (i, j) in the input matrix. We can maintain a maxSquareLength variable which will store the max length i.e. Max(maxSquareLength, Table[i][j]). Obviously maxSquareLength^2 will be our answer. Here is how we will fill the table:

Table[i][j] = Min ( Table[i][j - 1], Table[i - 1][j], Table[i-1][j-1]) + 1

We just need to take care of corner conditions while filling the table. 

Implementation in C#:

        public int MaximalSquare(char[][] matrix)

        {

            int[,] table = new int[matrix.Length, matrix[0].Length];

            int maxSquareLength = 0;

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

            {

                for (int j = 0; j < matrix[0].Length; ++j)

                {

                    if (i == 0 || j == 0)

                    {

                        table[i, j] = matrix[i][j] == '1' ? 1 : 0;

                    }

                    else if (matrix[i][j] == '1')

                    {

                        table[i, j] = Min(table[i - 1, j], table[i, j - 1], table[i - 1, j - 1]) + 1;

                    }

                    maxSquareLength = Math.Max(maxSquareLength, table[i, j]);

                }

            }

            return maxSquareLength * maxSquareLength;

        }

        

        public static int Min(params int[] values)

        {

            return Enumerable.Min(values);

        }

Complexity: O(m*n)

Contains nearby duplicate

Problem: Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is not more than k.

Example:

Input: nums = [19, 20, 22, 19, 17], k = 3
Output: true

Approach: Its not a complex problem to solve. We just need to maintain a hash which will have value as key and index as value. We will keep adding this pair to hash; hash[nums[i]] = i. In case of collision we just need to check if i - hash[nums[i]] <= k, if yes return true.

Implementation in C#:

        public bool ContainsNearbyDuplicate(int[] nums, int k)

        {

            if (nums?.Length <= 1)

            {

                return false;

            }

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

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

            {

                if (hash.ContainsKey(nums[i]))

                {

                    if (i - hash[nums[i]] <= k)

                    {

                        return true;

                    }

                    hash[nums[i]] = i;        

                }

                else

                {

                    hash.Add(nums[i], i);

                }

            }

            return false;

        }

Complexity: O(n)