[LeetCode][Uber] Russian Doll Envelopes

Problem: You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll (put one inside other) given rotation is not allowed? 

Example(taken from leetcode):

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3 
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Approach: This is a longest increasing subsequence problem with the exception here that we don't have to follow any sequence here :). We can sort the input array first according to width and then according to height. Once we sort the array, we can apply LIS on it. That's all!

Implementation in C#:

        public static int MaxEnvelopes(int[][] envelopes)

        {

            if (envelopes?.Length <= 0)

            {

                return 0;

            }

            SortEnvelopes(envelopes);

            int[] lis = new int[envelopes.Length];

            lis[0] = 1;

            // Applying LIS

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

            {

                lis[i] = 1;

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

                {

                    if (envelopes[i][0] > envelopes[j][0] 

                        && envelopes[i][1] > envelopes[j][1]

                        && lis[i] < lis[j] + 1)

                    {

                        lis[i] = lis[j] + 1;

                    }

                }

            }

            return lis.Max();

        }

        private static void SortEnvelopes(int[][] envelopes)

        {

            System.Array.Sort(envelopes, (envlp1, envlp2) =>

            {

                int firstCompare = envlp1[0].CompareTo(envlp2[0]);

                return firstCompare != 0 ? firstCompare : envlp1[1].CompareTo(envlp2[0]);

            });

        }

Complexity: O(n^2)

[Uber] Top K Frequent Elements

Problem: Given a non-empty array of integers, return the k most frequent elements.

Example:

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

Approach: We can use the quick select approach which we used in our previous problem of getting the kth smallest number in an unsorted array. Here are the few points which we need to take care:

1. Partial sorting will be done based on frequency of the number so to efficiently get the frequency of a number, we can maintain a hash with key as element of input array and value as the frequency of this number.
2. Here we need to get rid of duplicates as we need to return the top k frequent elements, right. That means we need to apply quick select on an array containing unique numbers of input array.
3. We need to get the top k frequent elements that means we just need to find (n - k)th less frequent element. Once we get it, our answer will be unique[n-k...n] where unique is the array of unique numbers of input array.

That's all!

Implementation in C#:

    public int[] TopKFrequent(int[] nums, int k) 

    {

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

        foreach(int num in nums)

        {

            if (!frequencies.ContainsKey(num))

            {

                frequencies.Add(num, 0);

            }

            ++frequencies[num];

        }

        int[] uniqueNums = frequencies.Keys.ToArray();

        return this.FindKMostFrequentElements(uniqueNums, uniqueNums.Length - k + 1, 0, uniqueNums.Length - 1, frequencies, k);

    }

    

    private int[] FindKMostFrequentElements(int[] uniqueNums, int k, int start, int end, Dictionary<int, int> frequencies, int length)

    {

        if (k > 0 && k <= end - start + 1)

        {

            int pos = this.RandomPartition(uniqueNums, start, end, frequencies);

            if (pos - start + 1 == k)

            {

                return this.SubArray(uniqueNums, pos, length);

            }

            else if (pos - start + 1 > k)

            {

                return this.FindKMostFrequentElements(uniqueNums, k, start, pos - 1, frequencies, length);

            }

            return this.FindKMostFrequentElements(uniqueNums, k - (pos - start + 1), pos + 1, end, frequencies, length);

        }

        return new int[] { };

    }

    

    private int RandomPartition(int[] uniqueNums, int start, int end, Dictionary<int, int> frequencies)

    {

        int pivot = new Random().Next(start, end);

        this.SwapElements(uniqueNums, pivot, end);

        return this.Partition(uniqueNums, start, end, frequencies);

    }

    

    private int Partition(int[] uniqueNums, int start, int end, Dictionary<int, int> frequencies)

    {

        int x = uniqueNums[end];

        int i = start;

        for (int j = start; j < end; ++j)

        {

            if (frequencies[uniqueNums[j]] < frequencies[x])

            {

                this.SwapElements(uniqueNums, i, j);

                ++i;

            }

        }

        this.SwapElements(uniqueNums, i, end); 

        return i;

    }

    

    public void SwapElements(int[] arr, int i, int j)

    {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

    

    public int[] SubArray(int[] array, int startIndex, int length)

    {

        int[] subArray = new int[length];

        Array.Copy(array, startIndex, subArray, 0, length);

        return subArray;

    }

Complexity: O(n)

Integer Break for max product

Problem: Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example:

Input: 3
Output: 2
Explanation: 3 = 2 + 1, 2 × 1 = 1.

Approach: We can use DP here. We can maintain a 1D Table where Table[i] will tell the maximum product by breaking i into at least 2 part. Obviously Table[n] will be our answer. Here is how we can fill this table:

• Table[0] = Table[1] = 0
• At any number i we need to get the maximum product of every partition of i possible. That means we need to run another loop say j = 1 to i - 1. Now at every j, here are the four products (partitions) possible:
1. j * (i - j)
2. maxProduct(j) * (i - j)
3. j * maxProduct(i - j)
4. maxProduct(j) * maxProduct(i - j)
• Right so for every j we can take the maximum of all the above 4 products and that will be maximum product of partitions if divide i at j. Obviously the maximum of maximum products of all the 'j's will maximum product for number 'i'.
• Once we understand the above logic. It's easy to understand the algorithm now:
• FOR i = 2 to n
• maxProd = 0
• FOR j = 1 to i - 1
• currMaxProd = Max ( j * (i - j), Table[j] * (i - j), j * Table[i - j], Table[j] * Table[i - j] // Max of the 4 products
• maxProd = Max(currMaxProd, max)
• Table[i] = maxProd

Hopefully its clear now.

Implementation in C#:

        public static int IntegerBreak(int n)

        {

            int[] table = new int[n + 1];

            for (int i = 2; i <= n; ++i)

            {

                int maxProd = 0;

                for (int j = 1; j < i; ++j)

                {

                    int currMaxProd = Max(table[j] * table[i - j], j * table[i - j], table[j] * (i - j), j * (i - j));

                    maxProd = Math.Max(maxProd, currMaxProd);

                }

                table[i] = maxProd;

            }

            return table.Last();

         }

        public static int Max(params int[] values)

        {

            return Enumerable.Max(values);

        }

        

Complexity: O(n^2)

Count set bits of range 0 to n

Problem: Given a non negative integer number n. For every numbers i in the range 0 ≤ i ≤ n calculate the number of 1's (set bits) in their binary representation and return them as an array.

Example:

Input: 6
Output: [0,1,1,2,1,2,2]

Approach: One easy way to do it is to iterate through every number from 0 to n and count the set bits in each number and store it in the result array but it will take O(n * k) time where is k is the number of bits in an integer. Let's see how we can do it better.

We can use DP. We can maintain a 1D table where Table[i] will tell the number of set bits in number "i".  Let's see how we can fill this table for every i:

• i is even that means i % 2 == 0: Table[i] = Table[i >>1]. Let's see why; if i % 2 == 0 than we can say the right most bit will be 0. Take any example 2(10), 4(100), 6(110),...etc. Now if right most bit is 0 that means we can say that right most bit has no role in counting set bits and hence we can say the number of set bits in i >> 1 and i will be same.
• i is odd that means i % 2 == 1: Table[i] = Table[i>>1] + 1. If you see for any odd number the right most bit is 1 so we can say number of set bits in i will be equal to number of set bits in (i >> 1) + 1 as by doing i >> 1 we are omitting the right most set bit so we are adding 1. 

By looking at above 2 points. We can say:

Table[i] = ((i & 1) == 0) ? Table[i >> 1] : Table[i >> 1] + 1

  

Implementation in C#:

    public int[] CountBits(int n)

    {

        int[] result = new int[n + 1];

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

        {

            result[i] = result[i >> 1] + (i & 1);

        }

        return result;

    }

Complexity: O(n)

Maximum sum of nodes in Binary tree with no directly connected nodes

Problem: Get the maximum sum given a binary tree where you can't use directly connected nodes.

Example:

Input: 
     4
    / \
   2   3
    \   \ 
     3   2

Output: 9 
Explanation: Maximum sum with no directly connected nodes = 4 + 3 + 2 = 9.

Approach: We can use Post order traversal. Basically here we traverse the binary tree and at each node we will calculate two sums; 1) Max sum using the node 2) Max sum without using the node so basically the method will return an array which will contain [max_sum_using_node, max_sum_without_using_node].

At every node we will recursively call this method to get the above mentioned sums for left node of current node and right node of current node. Now our result will be: 

• SumUsingTheCurrentNode = node.Value + leftSum[1] + rightSum[1]. Basically if you see our return value, you will see that leftSum[1] = max_sum_without_using_left_node and rightSum[1] is max_sum_without_using_right_node. We are choosing index 1 because we don't want to use immideate left and right nodes given we are using the current node.
• SumWithOutUsingTheCurrentNode = Max(leftSum[0], leftSum[1]) + Max(rightSum[0], rightSum[1]). Here as we are not using current node, there are no restrictions. We can go for the maximum value of leftSum and rightSum to maximize the result.
• [SumUsingTheCurrentNode, SumWithOutUsingTheCurrentNode] will be returned

Now once we get the above array for the root, we can just return the maximum of [max_sum_using_node, max_sum_without_using_node].

Implementation in C#:

         public int MaxSumWithNoConnectedNode()

        {

            if (this.Root == null)

            {

                return 0;

            }

            int[] maxSums = this.MaxSumWithNoConnectedNode(this.Root);

            return Math.Max(maxSums[0], maxSums[1]);

        }

        // Returns [max_sum_using_node, max_sum_without_using_node]

        private int[] MaxSumWithNoConnectedNode(BinaryTreeNode node)

        {

            if (node == null)

            {

                return new int[] { 0, 0 };

            }

            int[] leftMaxSums = this.MaxSumWithNoConnectedNode(node.LeftNode);

            int[] rightMaxSums = this.MaxSumWithNoConnectedNode(node.RightNode);

            

            // Can't include leftMaxSum[0] and rightMaxSum[0] as current node is used

            int useThisNodeSum = node.Value + leftMaxSums[1] + rightMaxSums[1]; 

            

            // No restrictions here as current node is not used, just take the maximum

            int dontUseThisNodeSum = Math.Max(leftMaxSums[0], leftMaxSums[1]) + Math.Max(rightMaxSums[0], rightMaxSums[1]);

            return new int[] { useThisNodeSum, dontUseThisNodeSum };

        }

Complexity: O(n)

[Uber] Palindrome Pairs

Problem: Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

Example:

Input: words = ["abc","cba","nish","h","hhsin"]
Output: [[0,1],[1,0],[2,4]]
Explanation: The palindromes are ["abccba","cbaabc","nishhhsin"]

Approach: One brute-force approach would be to consider each pair one by one. If any pair forms a palindrome after concatenating them than add that pair to result. This will work but will take O(n^2 * k) time where n is the number of words and k is the maximum length of the pair checked for palindrome. 

Let's go to another approach which is much better in case number of words are way more than the average length of words (more real world scenario). Here is the algorithm:

• If you see we need to return the list of pair of indices so it is intuitive that we maintain a hash with key as word and value as it's index in the input list.
• Now we will iterate through each word of input:
• We will iterate through every 2 substrings possible for that word:
• SubStr1 = word[0...i]
• SubStr2 = word[i + 1....length of word] (For i = 0 to length of word)
• For each of these substrings we will check:
• IF SubStr1 is palindrome (means SubStr1 can be pivot)
• IF hash contains the reverse of SubStr2 AND hash[SubStr2] is not current index
• We will add hash[SubStr2] and current index to result
• IF  SubStr2 is palindrome (means SubStr2 can be pivot)  AND length of SubStr2 > 0 (To avoid duplicate)
• IF hash contains the reverse of SubStr1 AND hash[SubStr1] is not current index
• We will add current index and hash[SubStr1] to result

That's all!

Implementation in C#:

        public IList<IList<int>> PalindromePairs(string[] words)

        {

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

            if (words?.Length <= 1)

            {

                return result;

            }

            Dictionary<string, int> wordToIndexMap = new Dictionary<string, int>();

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

            {

                wordToIndexMap.Add(words[i], i);

            }

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

            {

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

                {

                    string subStr1 = words[i].Substring(0, j);

                    string subStr2 = words[i].Substring(j);

                    if (this.IsPalindrome(subStr1, 0, subStr1.Length - 1))

                    {

                        string subStr2Rev = subStr2.Reverse();

                        if (wordToIndexMap.ContainsKey(subStr2Rev) && wordToIndexMap[subStr2Rev] != i)

                        {

                            result.Add(new List<int> { wordToIndexMap[subStr2Rev], i });

                        }

                    }

                    if (subStr2.Length > 0 && this.IsPalindrome(subStr2, 0, subStr2.Length - 1))

                    {

                        string subStr1Rev = subStr1.Reverse();

                        if (wordToIndexMap.ContainsKey(subStr1Rev) && wordToIndexMap[subStr1Rev] != i)

                        {

                            result.Add(new List<int> { i, wordToIndexMap[subStr1Rev] });

                        }

                    }

                }

            }

            return result;

        }

        

        // start index and end index are not necessary as in this case it will always be 0 and length - 1

        private bool IsPalindrome(string s, int startIndex, int endIndex)

        {

            while(startIndex < endIndex)

            {

                if (s[startIndex++] != s[endIndex--])

                {

                    return false;

                }

            }

            return true;

        }

        

        // To use this extension as is, you need to put in a static class

        public static string Reverse(this string str)

        {

            char[] tempCharArr = str.ToCharArray();

            Array.Reverse(tempCharArr);

            return new string(tempCharArr);

        }

Complexity: O(n * k ^ 2)

Self Crossing

Problem: You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] meters to the north, then x[1] meters to the west, x[2] meters to the south, x[3] meters to the east and so on. In other words, after each move your direction changes counter-clockwise. Determine, if your path crosses itself, or not.

Example(Taken from leetcode):

┌───┐
│   │
└───┼──>
    │

Input: [2,1,1,2]
Output: true

Approach: Given the counter-clockwise restriction, there can be only following three unique cases of self crossing:

Once you understand these three conditions. The implementation is straight forward.

Implementation in C#:

        public bool IsSelfCrossing(int[] x)

        {

            if (x?.Length <= 3)

            {

                return false;

            }

            for (int i = 3; i < x.Length; ++i)

            {

                if (x[i-3] >= x[i - 1] && x[i] >= x[i - 2])

                {

                    return true;

                }

                if (i >= 4 && x[i - 4] + x[i] >= x[i - 2] && x[i - 3] == x[i - 1])

                {

                    return true;

                }

                if (i >= 5 

                    && x[i - 5] <= x[i - 3] 

                    && x[i - 4] <= x[i - 2] 

                    && x[i - 3] >= x[i - 1]

                    && x[i - 3] <= x[i - 5] + x[i - 1]

                    && x[i - 2] >= x[i]

                    && x[i - 2] <= x[i - 4] + x[i])

                {

                    return true;

                }

            }

            return false;

        }

Complexity: O(n)

Increasing Triplet Subsequence

Problem: Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example:

Input: nums = [2,1,9,8,4,7]
Output: true
Explanation: The triplet (1, 4, 5) is valid because nums[1] = 1 < nums[4] = 4 < nums[5] = 7.

Approach: The first thing which immediately comes to mind is to get the length of longest increasing subsequence in the array and if it is more than two then return true otherwise false but this will take O(n^2) time with linear extra space. Let's do better!

Here is the algorithm which is straight forward and really easy to understand:

• first = INT_MAX, second = INT_MAX
• FOR i = 0 to n:
• IF first >= nums[i] then first = nums[i]
• ELSE IF second >= nums[i] then second = nums[i]
• ELSE return true
• return false

That's all!

Implementation in C#:

        public bool IncreasingTriplet(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 2)

        {

            return false;

        }

        int first = int.MaxValue, second = int.MaxValue;

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

        {

            if (first >= nums[i])

            {

                first = nums[i];

            }

            else if (second >= nums[i])

            {

                second = nums[i];

            }

            else

            {

                return true;

            }

        }

        return false;

    }

Complexity: O(n)

Reconstruct Itinerary

Problem: Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

• If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
• All airports are represented by three capital letters (IATA code).
• You may assume all tickets form at least one valid itinerary.
• One must use all the tickets once and only once.

Example:

Input: [["EZE","AXA"],["TIA","ANU"],["ANU","JFK"],["JFK","ANU"],["ANU","EZE"], ["TIA","ANU"],["AXA","TIA"],["TIA","JFK"],["ANU","TIA"],["JFK","TIA"]]
Output: ["JFK","ANU","EZE","AXA","TIA","ANU","JFK","TIA","ANU","TIA","JFK"]

Approach: Basically we can make a graph from the given tickets and apply the DFS. There are two problems which we need to consider here:

1. In source to destinations mapping, we need to keep destinations in sorted order.
2. There could be duplicate tickets here like in the above example you can see ["TIA", "ANU"] came 2 times so if you are going to use DS like C# SortedSet to store destinations in sorted order. Don't do it!

 

Implementation in C#:

        public static IList<string> FindItinerary(IList<IList<string>> tickets)

        {

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

            const string startStation = "JFK";

            if (tickets?.Count == 0)

            {

                return result;

            }

            Dictionary<string, List<string>> sourceDestinationsMap = new Dictionary<string, List<string>>();

            foreach(var ticket in tickets)

            {

                if (!sourceDestinationsMap.ContainsKey(ticket.First()))

                {

                    sourceDestinationsMap.Add(ticket.First(), new List<string>());

                }

                sourceDestinationsMap[ticket.First()].Add(ticket.Last());

            }

            foreach (string key in sourceDestinationsMap.Keys)

            {

                sourceDestinationsMap[key].Sort();

            }

            FindItineraryDFS(startStation, sourceDestinationsMap, result);

            result.Reverse();

            return result;

        }

        private static void FindItineraryDFS(string source, Dictionary<string, List<string>> sourceDestinationsMap, List<string> result)

        {

            while(sourceDestinationsMap.ContainsKey(source) && sourceDestinationsMap[source].Count > 0)

            {

                string destination = sourceDestinationsMap[source].First();

                sourceDestinationsMap[source].Remove(destination);

                

                FindItineraryDFS(destination, sourceDestinationsMap, result);

            }

            result.Add(source);

        }

Complexity: O(nlogn)

Verify Preorder Serialization of a Binary Tree

Problem: One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as # or $. Check our previous problem here.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

Example:

Input: "1,2,3,#,#,4,#,#,5,#,6,#,#"
Output: true

Approach: We can keep trimming the leaves until there is no one to remove. If a sequence is like "3 # #", change it to "#" and continue. We can use stack to implement it easily. See by above example:

1 2 3 # # 4 # # 5 # 6 # #

       |___| |___|       |___|

1 2    #       #    5 #    #

   |_______|      |_____|

1       #                  #

|_______________|

    # 

(if in stack only # is remaining, return true else false)  

 

Implementation in C#:

        public static bool IsValidSerialization(string preorder)

        {

            if (string.IsNullOrWhiteSpace(preorder))

            {

                return false;

            }

            string[] nodesValueArr = preorder.Split(',');

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

            foreach(string nodeValue in nodesValueArr)

            {

                if (stack.Count == 0 || !nodeValue.Equals("#"))

                {

                    stack.Push(nodeValue);

                }

                else

                {

                    while(stack.Count > 0 && stack.Peek().Equals("#"))

                    {

                        stack.Pop();

                        if (stack.Count == 0)

                        {

                            return false;

                        }

                        else

                        {

                            stack.Pop();

                        }

                    }

                    stack.Push(nodeValue);

                }

            }

            return stack.Count == 1 && stack.Peek().Equals("#");

        }

Complexity: O(n)

Patching Array

Problem: Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example:

Input: nums = [1,4], n = 7
Output: 1 
Explanation:
Combinations of nums are [1], [4], [1, 4], which form possible sums of: 1, 4, 5.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [1, 2], [4], [1, 4], [2,4], [1,2,4].
Possible sums are 1, 2, 3, 4, 5, 6, 7 which now covers the range [1, 7].
So we only need 1 patch.

Approach:  It's a easy problem to solve. Let's understand the algorithm using an example say our input array is [1, 2, 5, 6, 20] and n = 50.

Let's take the element of array one by one (remember the array is already sorted) and see what is the range it can cover:

1. input[0] = 1 so it can cover range [1 - 1] with number_used = [1], number_added = []
2. input[1] = 2 so it can cover  range 1 -  (1 (previous max) + 2 (current number)) =  [1 - 3] with number_used = [1, 2], number_added = []
3. input[2] = 5  now 5 > 4 (next number to cover) so we need to add a new number to get 4 so let's add 4. After adding 4 it can cover range 1 - (3 + 4) =  [1 - 7] with number_used = [1, 2], number_added = [4]
4. input[2] = 5 and 5 < 8 (next number to cover) so now it can cover range 1 - (7 + 5) =  [1 - 12] with number_used = [1, 2, 5], number_added = [4]
5. input[3] = 6 and 6 < 13(next number to cover) so now it can cover 1 - (12 + 6) = [1, 18] with number_used = [1, 2, 5, 6], number_added = [4]
6. input[4] = 20 and 20 > 19 (next number to cover) so we need to add a new number to get 19. Optimally let's add 19. After adding 19 it can cover range 1 - (18 + 19) =  [1 - 37] with number_used = [1, 2, 5, 6], number_added = [4, 19]
7. input[4] = 20 and 20 < 38 (next number to cover) so now it can cover range 1- (37 + 20) = [1, 57] with number_used = [1, 2, 5, 6, 20], number_added = [4, 19]
8. Now since 57 > n (50) we are done here and we can see the count of numbers added/patched is 2 and that is our answer.

Hopefully our algorithm / approach is clear now and can be understood using the implementation itself. 

Implementation in C#:

        public int MinPatches(int[] nums, int n)

        {

            long maxReach = 0;

            int numOfPatchesRequired = 0;

            int i = 0;

            while (maxReach < n)

            {

                if (i < nums.Length && nums[i] <= maxReach + 1)

                {

                    maxReach += nums[i++];

                }

                else

                {

                    ++numOfPatchesRequired;

                    maxReach += (maxReach + 1);

                }

            }

            return numOfPatchesRequired;

        }

Complexity: O(n)

Longest Increasing Path in a Matrix

Problem: Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You are not allowed to move diagonally.

Example: (Taken from leetcode)

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Approach: A simple way to solve this problem is to use DFS by taking each and every cell as starting point, get the longest path for that cell and update the result if result is less than the recently found longest path but the time complexity will be very high (O(m^2 * n^2)). 

Let's see how we can make it better. We can use the dynamic programming. We can maintain a 2D Table where Table[i][j] will tell the longest increasing path if starting point of the DFS is (i, j), obviously Max of all the Table[i][j] is our answer. 

Now we can use this table while doing DFS. While doing DFS if we found at any cell (i, j), Table[i][j] is not 0 then we know that we have already processed this cell, now we can immediately return Table[i][j] and we don't need to traverse it further.

That's all!.

Implementation in C#:

        public int LongestIncreasingPathinMatrix(int[][] matrix)

        {

            if (matrix?.Length == 0)

            {

                return 0;

            }

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

            int result = 0;

            // Do DFS by assuming every cell as starting node

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

            {

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

                {

                    // if table[i, j] is not 0 i.e. it is already processed

                    if (table[i, j] == 0)

                    {

                        this.Dfs(matrix, i, j, table, int.MinValue);

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

                    }

                }

            }

            return result;

        }

        private int Dfs(int[][] matrix, int row, int col, int[,] table, int prevValue)

        {

            // Boundary and increasing path condition 

            if (row < 0 || row >= matrix.Length || col < 0 || col >= matrix[0].Length || matrix[row][col] <= prevValue)

            {

                return 0;

            }

            // Already processed then return, no need to traverse further

            if (table[row, col] != 0)

            {

                return table[row, col];

            }

            // Take the longest increasing path at all 4 direction

            int leftValue = this.Dfs(matrix, row, col - 1, table, matrix[row][col]);

            int rightValue = this.Dfs(matrix, row, col + 1, table, matrix[row][col]);

            int upValue = this.Dfs(matrix, row - 1, col, table, matrix[row][col]);

            int downValue = this.Dfs(matrix, row + 1, col, table, matrix[row][col]);

            // Assign the maximum of all

            table[row, col] = Max(leftValue, rightValue, upValue, downValue) + 1;

            return table[row, col];

        }

        private static int Max(params int[] values)

        {

            return Enumerable.Max(values);

        }

Complexity: O(mn)

Reverse Vowels of a String

Problem: Write a function that takes a string as input and reverse only the vowels of a string.

Example:

Input: "nishant"
Output: "nashint"

Approach: Problem is very easy to solve by using the two pointers string reverse approach. Here we just need to take care of some boundary conditions which we can understand by just looking at the code.

Implementation in C#:

        public string ReverseVowels(string s)

        {

            if (s?.Length <= 1)

            {

                return s;

            }

            char[] result = new char[s.Length];

            int i = 0, j = s.Length - 1;

            for (; i < j;)

            {

                while (i < s.Length && !IsVowel(s[i]))

                {

                    result[i] = s[i];

                    ++i;

                }

                while (j >= 0 && !IsVowel(s[j]))

                {

                    result[j] = s[j];

                    --j;

                }

                if (i < j)

                {

                    result[i] = s[j];

                    result[j] = s[i];

                    ++i;

                    --j;

                }               

            }

            if (i == j)

            {

                result[i] = s[i];

            }

            return new string(result);

        }

        private bool IsVowel(char ch)

        {

            ch = char.ToLower(ch);

            return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';

        }

Complexity: O(n)

Given an integer check if it is a power of four

Problem: Given an integer num, return true if it is a power of four. Otherwise, return false.

Example:

Input: num = 64
Output: true

Approach: Here are the points which we need to focus:

1. if input number is 0, it is not power of 4 (obviously).
2. Any number which is a power of 4 will definitely be a power of 2.
3. We know that num is power of 2 if if num & (nums - 1) is 0. 
4. Every number which is power of 2, is a power of 4 if num - 1 is divisible by 3. You can see this by examples or you can look at the proof by induction here. 

If you understood the above points. Solution can be easily understood by just looking at the implementation.

Implementation:

        public bool IsPowerOfFour(int num)

        {

            return num > 0 && (num & (num - 1)) == 0 && (num - 1) % 3 == 0;

        }

Complexity: O(1)

Odd Even Linked List

Problem: Given a singly linked list, group all nodes at odd position together followed by the nodes at even position.

Example:

Input: 1->2->3->4->5->6->NULL
Output: 1->3->5->2->4->6->NULL

Approach: It is a straight forward problem to solve. Not much to explain about the approach here as you can understand the approach by just looking at the code.

Implementation in C#:

        public ListNode OddEvenList(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode odd = head, even = head.next;

        ListNode evenHead = even;

        while (even != null)

        {

            odd.next = even.next;

            if (odd.next != null)

            {

                odd = odd.next;

            }

            even.next = odd.next;

            even = even.next;

        }

        odd.next = evenHead;

        return head;

    }

Complexity: O(n)

Count of Smaller Numbers After Self in an Array

Problem: You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: nums = [5,3,1,2]
Output: [3,2,0,0]
Explanation:
To the right of 5 there are 3 smaller elements (3, 1 and 2).
To the right of 3 there are 2 smaller element (1 and 2).
To the right of 1 there are no smaller element.
To the right of 1 there is 0 smaller element.

Approach: This is a clearly a problem of finding the number of inversions. Now here instead of finding total number of inversions, we need to find inversions per element/index in the array. We will use the same merge sort approach here but here for simplicity I am sorting indices instead of actual array as we need to fill result array according to how many numbers are less than on the right of the index. 

You can use original merge sort too. You can also use any balanced binary tree to solve this problem.  

Implementation in C#:

        public static IList<int> CountSmaller(int[] nums) 

        {

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

            int[] indexes = Enumerable.Range(0, nums.Length).ToArray();

            CountSmallerNumberUsingMergeSort(ref indexes, nums, result);

            return result.ToList();

        }

        private static void CountSmallerNumberUsingMergeSort(ref int[] indexes, int[] nums, int[] result)

        {

            if (indexes.Length <= 1)

            {

                return;

            }

            int[] leftArray = indexes.SubArray(0, indexes.Length / 2);

            int[] rightArray = indexes.SubArray(indexes.Length / 2, indexes.Length - indexes.Length / 2);

            CountSmallerNumberUsingMergeSort(ref leftArray, nums, result);

            CountSmallerNumberUsingMergeSort(ref rightArray, nums, result);

            indexes = CountSmallerWhileMerge(leftArray, rightArray, nums, result);

        }

        private static int[] CountSmallerWhileMerge(int[] leftArray, int[] rightArray, int[] nums, int[] result)

        {

            int lIndex = 0, rIndex = 0;

            int countOfSmallerNumber = 0;

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

            while (lIndex < leftArray.Length && rIndex < rightArray.Length)

            {

                if (nums[leftArray[lIndex]] > nums[rightArray[rIndex]])

                {

                    ++countOfSmallerNumber;

                    newIndexes.Add(rightArray[rIndex++]);

                }

                else

                {

                    result[leftArray[lIndex]] += countOfSmallerNumber;

                    newIndexes.Add(leftArray[lIndex++]);

                }

            }

            while(lIndex < leftArray.Length)

            {

                result[leftArray[lIndex]] += countOfSmallerNumber;

                newIndexes.Add(leftArray[lIndex++]);

            }

            while(rIndex < rightArray.Length)

            {

                newIndexes.Add(rightArray[rIndex++]);

            }

            return newIndexes.ToArray();

        }

        

        // Put this extension method in a static class if you want to use it as is

        public static T[] SubArray<T>(this T[] array, int startIndex, int length)

        {

            T[] subArray = new T[length];

            Array.Copy(array, startIndex, subArray, 0, length);

            return subArray;

        }

Complexity: O(nlogn)

Create Maximum Number From Two Array

Problem: Given two arrays which only contains digits 0 - 9 of lengths say m and n represents two numbers. Create the maximum number of length k <= m + n from digits of the input two arrays. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Example: 

Input:
nums1 = [6, 0, 1, 2]
nums2 = [6, 7, 3]
k = 5
Output:
[7, 6, 3, 1, 2]

Approach: Let's breakdown this problem into sub problems:

1. Given an array of length n, create the maximum number of length k. Basically instead of looking at 2 arrays, just look at one array:

This is straight forward, we can do it using the stack. Here is the algorithm:

• stack = empty stack
• FOREACH i from 0 to n:
• WHILE stack is not empty AND top of stack < array[i] AND n - i + number of elements in stack > k
• Pop from stack
• IF number of elements in stack < k
• Push array[i] to stack
• Add all the elements of the stack in an array in reverse order and return this array

Let me explain what exactly "WHILE stack is not empty AND top of stack < array[i] AND n - i + number of elements in stack > k" condition is checking; basically its saying pop the top of stack if it is smaller than array[i] until either stack is empty or the number of digits left in the array is not enough to fill the stack to size k.

2. Given two array say array1 and array2 of length m and n, create maximum number of length k = m + n: This problem is lot closer to the original problem with the exception that we will use all the digits we have. 

Let's say result is the array of size k which we want to return. We can use the approach similar to merge method of merge sort where we just fill the greater digit in result by comparing current element of array1 and current element of array2 and increment the index of the array from where we find the larger digit. This looks good and works until we find current digits of both the arrays are same. Which one we should choose here? In case of merge sort, it does not matter which one we choose but here it does matter. Let's see it by example. Say we have following 2 arrays:

1. [6, 0]
2. [6, 7]

Now in this case when current digit of both array is 6, we just can't take any 6, we need to take 6 from array 2 as then we will get the maximum number which is [6, 7, 6, 0] otherwise if we took the 6 from array 1 the number which we have gotten is [6, 6, 7, 0] which is clearly not the maximum number. That means in case of same digits we need to look further into both strings until we get different digits and choose the array where we get the greater digit. So you see our merge algorithm will be almost same as merge method of merge sort except here we will use a method say IsGreater (which will look further in both strings until we get the different digits) instead of usual greater than '>' operator. Here is the algorithm for merge method:

• result = []
• i = 0, j = 0
• FOR resultIndex = 0 To k
• IF IsGreater(array1, i, array2, j) 
• result[resultIndex] = array1[i]
• i = i + 1
• ELSE
• result[resultIndex] = array2[j]
• j = j + 1
• return result 

Now here is the algorithm for IsGreater method:

• WHILE array1[i] == array2[j] // Looking further till we get same digits
• i = i + 1
• j = j + 1
• return array1[i] > array2[i]

Of course we need to handle some boundary conditions which you can see in the implementation in the above algorithm. I did not put it here just to make core logic simple to understand.

Now given we have solved above subproblems we can go back to our original problem which will be fairly easy to solve using the solution of above subproblems:

1. First, we divide the k digits required into two parts; i and k-i. 
2. Find the maximum number of length i in one array and the maximum number of length k-i in the other array using the algorithm of subproblem 1. 
3. Merge the two results of step 2 in to one array using the algorithm of subproblem 2. 
4. Compare the current result with final result and assign the current result to final result if current result is greater than final result. We can use IsGreater method of subproblem 2 to identify which one is greater.

That's all!

Implementation in C#:

        public static int[] MaxNumberOfTwoArray(int[] nums1, int[] nums2, int k)

        {

            if ( k > nums1?.Length + nums2?.Length)

            {

                return null;

            }

            int[] maxNumber = new int[k];

            // Dividing k into i and k -i

            for (int i = Math.Max(0, k - nums2.Length); i <= k && i <= nums1.Length; ++i)

            {

                int[] currNumber = MergeMaxNumbers(MaxNumberOfOneArray(nums1, i), MaxNumberOfOneArray(nums2, k - i), k);

                if (IsGreater(currNumber, 0, maxNumber, 0))

                {

                    maxNumber = currNumber;

                }

            }

            return maxNumber;

        }

        private static int[] MaxNumberOfOneArray(int[] nums, int k)

        {

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

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

            {

                while (stack.Count > 0 && nums.Length - i + stack.Count > k && stack.Peek() < nums[i])

                {

                    stack.Pop();

                }

                if (stack.Count < k)

                {

                    stack.Push(nums[i]);

                }

            }

            int[] result = new int[k];

            for (int i = k - 1; i >= 0; --i)

            {

                result[i] = stack.Pop();

            }

            return result;

        }

        private static int[] MergeMaxNumbers(int[] nums1, int[] nums2, int k)

        {

            int[] result = new int[k];

            for (int nums1I = 0, nums2I = 0, resultI = 0; resultI < k; ++resultI)

            {

                result[resultI] = IsGreater(nums1, nums1I, nums2, nums2I) ? nums1[nums1I++] : nums2[nums2I++];

            }

            return result;

        }

        private static bool IsGreater(int[] nums1, int nums1I, int[] nums2, int nums2I)

        {

            while (nums1I < nums1.Length && nums2I < nums2.Length && nums1[nums1I] == nums2[nums2I])

            {

                ++nums1I;

                ++nums2I;

            }

            return nums2I == nums2.Length || (nums1I < nums1.Length && nums1[nums1I] > nums2[nums2I]);

        }

Complexity: O(k * (m + n)) where m is the size of nums1 and n is the size of nums2

Maximum Product of Word Lengths with no common characters

Problem: Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. It is given that each word only consists lower case letters. If no such two words exist, return 0.

Example:

Input: ["b","ab","abc","d","cd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Approach: There are multiple ways of solving this problem: 

1. One brute force approach is we take every pair of words and see if there are any common characters in these two words. If there are no common characters, we calculate the product of the lengths and see if it is more than max product which we have calculated till now if yes we assign current product to max product. That's it. This will work but the time complexity will be O(n^2 * m ^2) where n are total number of words and m is the length of the word. For simplicity I have assumed the all words are of same length that is m. This is really very inefficient.

2. Another way is we can maintain a hash of character to list of indices of the words which will tell us about all the words where a particular character (key) is present. This can help us greatly in identifying if two words have same set of common characters.

Now we can take every pair of words like in brute force say words[i] and words[j] and using the above generated hash we can look at each and every character of words[i] to see if for any character j exist in the hash or not. if not, we can take the product of lengths of words[i] and words[j], update the max product in case max product is less than currently calculated product.

This approach is good and is much more efficient than brute force. Let's see it's time complexity:

1. 1st loop to create the hash will take O(n * m).
2. 2nd loop to create bool matrix will take O(n^2 *m).

So overall complexity will be O(n*m) + O(n^2 * m)  ~= O(n^2*m). Yes there is an improvement here but can we do even better?

3. Let's see how to get much more efficient algorithm to solve this problem. The problem in above approach is the hash which we are creating is not enough to efficiently tell if two words have common characters or not. Ultimately we need to traverse through each character of words[i] or words[j] to see if in hash for any character, i and j both exist or not and this is the bottleneck here.

Let's use the fact that the input strings can only have lower case English characters. That means total number of character can't be more than 26. If we use bit to represent every character, we will be needing only 26 bits to represent each and every character. That means for hashing which was step 1 in 2nd approach we can use int and set its bit according to characters present in each word so basically we will create a bit map (int) for each input word.

Now for step 2 where we are checking if words[i] and words[j] have common characters or not we can safely say if bitmap[i] & bitmap[j] is 0 then they have no common characters and we can calculate product of lengths of words[i] and words[j] and update max product accordingly so now you see checking of common characters is now done at constant time.       

Implementation in C#:

Approach 2:

        public static int MaxProduct(string[] words)

        {

            if (words?.Length <= 1)

            {

                return 0;

            }

            Dictionary<char, HashSet<int>> charToWordsHash = new Dictionary<char, HashSet<int>>();

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

            {

                foreach(char ch in words[i])

                {

                    if (!charToWordsHash.ContainsKey(ch))

                    {

                        charToWordsHash.Add(ch, new HashSet<int>());

                    }

                    charToWordsHash[ch].Add(i);

                }

            }

            int maxProduct = 0;

            for (int i = 0; i < words.Length - 1; ++i)

            {

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

                {

                    bool isCommonChar = false;

                    foreach(char ch in words[i])

                    {

                        if (charToWordsHash[ch].Contains(j))

                        {

                            isCommonChar = true;

                            break;

                        }

                    }

                    if (!isCommonChar)

                    {

                        maxProduct = Math.Max(words[i].Length * words[j].Length, maxProduct);

                    }

                }

            }

            return maxProduct;

        }

Approach 3:

        public static int MaxProduct(string[] words)

        {

            if (words?.Length <= 1)

            {

                return 0;

            }

            int[] bitmap = new int[words.Length];

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

            {

                foreach (char ch in words[i])

                {

                    bitmap[i] |= (1 << (ch - 'a'));

                }

            }

            int maxProduct = 0;

            for (int i = 0; i < words.Length - 1; ++i)

            {

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

                {

                    if ((bitmap[i] & bitmap[j]) == 0)

                    {

                        maxProduct = Math.Max(words[i].Length * words[j].Length, maxProduct);

                    }

                }

            }

            return maxProduct; 

        }

Complexity: O(n^2) for approach #3.