[LeetCode] Find the City With the Smallest Number of Neighbors at a Threshold Distance

Problem: There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.

Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.

Example:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

• 2 <= n <= 100
• 1 <= edges.length <= n * (n - 1) / 2
• edges[i].length == 3
• 0 <= fromi < toi < n
• 1 <= weighti, distanceThreshold <= 10^4
• All pairs (fromi, toi) are distinct.

Approach: This is clearly a Floyd-Warshall problem as we can do BFS here but the complexity will be n^n. Once we get the dist matrix from Floy Warshall algorithm, things becomes simpler. Now we know that we have the shortest path matrix 'dist' with us so we just need to traverse this matrix:

• For every node i from 0...n-1: 
• Check if dist[i][j] <= distanceThreshold then we know j is reachable from i.

Now in this way we just need to calculate the number of cities reachable from every city i and return the city with minimum number of connected cities.

Implementation in C#:

public class Solution

{

    public int FindTheCity(int n,

                           int[][] edges,

                           int distanceThreshold)

    {

        int[,] dist = this.FloydWarshall(edges, n);

        int minCount = INF;

        int minCity = -1;

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

        {

            int currCount = 0;

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

            {

                if (i != j)

                {

                    if (dist[i, j] <= distanceThreshold)

                    {

                        ++currCount;

                    }

                }

            }

            if (currCount <= minCount)

            {

                minCount = currCount;

                minCity = i;

            }

        }

        return minCity;

    }

    private int[,] FloydWarshall(int[][] edges, int n)

    {

        int[,] dist = this.InitDist(edges, n);

        for (int k = 0; k < n; ++k)

        {

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

            {

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

                {

                    if (dist[i, j] > dist[i, k] + dist[k, j])

                    {

                        dist[i, j] = dist[i, k] + dist[k, j];

                    }

                }

            }

        }

        return dist;

    }

    private int[,] InitDist(int[][] edges, int n)

    {

        int[,] dist = new int[n, n];

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

        {

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

            {

                dist[i, j] = i == j ? 0 : INF;

            }

        }

        foreach (var edge in edges)

        {

            dist[edge[0], edge[1]] = edge[2];

            dist[edge[1], edge[0]] = edge[2];

        }

        return dist;

    }

    // Max sum could be 10^4 * 10^2 = 10^6

    private const int INF = 9999999;

}

Complexity: O(n^3)

Floyd Warshall Algorithm

Description: As per wiki, in computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. 

Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. 

Algorithm: Given a graph Graph[][] with nodes 1...N, we need to evaluate the matrix say shortestPathMatrix[][] where shortestPathMatrix[ni][nj] tells the shortest path between nodes ni and nj.

The algorithm uses dynamic programming to evaluate the above matrix. It relies on a obvious thing that the shortest path between n1 and n2 will have a intermediate node say nk:

 

That means, we can say for every intermediate node k:

shortestPathMatrix[i][j] = MIN (shortestPathMatrix[i][k] + shortestPathMatrix[k][j], shortestPathMatrix[i][j]

So the steps are now simple:

• Initialize shortestPathMatrix to Graph.
• FOR k = 0 TO n:
• FOR i = 0 TO n:
• FOR j = 0 TO n:
• shortestPathMatrix[i][j] = MIN (shortestPathMatrix[i][k] + shortestPathMatrix[k][j], shortestPathMatrix[i][j])

 

That's all!

Implementation in C#:

class Graph

{

    public Graph(int[,] adjMat)

    {

        this.adjacencyMatrix = adjMat;

    }

    

    public int[,] FloydWarshall()

    {

        int n = this.adjacencyMatrix?.GetLength(0) ?? 0;

        if (n == 0)

        {

            return null;

        }

        int[,] dist = this.InitDistance();

        

        for (int k = 0; k < n; ++k)

        {

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

            {

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

                {

                    if (dist[i, k] + dist[k, j] < dist[i, j])

                    {

                        dist[i, j] = dist[i, k] + dist[k, j];

                    }

                }

            }

        }

        return dist;

    }

    

    private int[,] InitDistance()

    {

        int n = this.adjacencyMatrix.GetLength(0);

        int[,] dist = new int[n, n];

        Console.WriteLine(n);

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

        {

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

            {

                dist[i, j] = this.adjacencyMatrix[i, j] >= 0 ?

                             this.adjacencyMatrix[i, j] :

                             Graph.INF;

            }

        }

        return dist;

    }

    

    private int[,] adjacencyMatrix;

    private const int INF = 9999;

}

Complexity: O(n^3)

[Microsoft][GFG] Tree Boundary Traversal in anticlockwise direction

Problem: Given a Binary Tree, find its Boundary Traversal. The traversal should be in the following order: 

• Left boundary nodes: defined as the path from the root to the left-most node ie- the leaf node you could reach when you always travel preferring the left subtree over the right subtree. 
• Leaf nodes: All the leaf nodes except for the ones that are part of left or right boundary.
• Reverse right boundary nodes: defined as the path from the right-most node to the root. The right-most node is the leaf node you could reach when you always travel preferring the right subtree over the left subtree. Exclude the root from this as it was already included in the traversal of left boundary nodes.

Note: If the root doesn't have a left subtree or right subtree, then the root itself is the left or right boundary. 

Example:

Input:
        1 
      /   \
     2     3  
    / \   / \ 
   4   5 6   7
      / \
     8   9
   
Output: 1 2 4 8 9 6 7 3
Explanation:

Input:
            1
           /
          2
        /  \
       4    9
     /  \    \
    6    5    3
             /  \
            7     8

Output: 1 2 4 6 5 7 8
Explanation:













As you can see we have not taken the right subtree.

Approach: We can solve this problem in four steps given the nature of the problem:

1. Add root to result.
2. Preorder traversal of left subtree. If left child is available then do not go for right child. Ignore the leaves.
3. Inorder traversal of leaves if root is not leaf.
4. Postorder traversal of right subtre. If right child is available then do not go for left child. Ignore the leaves.

That's all!

Implementation in C#:

class BinaryTreeNode

{

    public BinaryTreeNode Left {get; set;}

    public BinaryTreeNode Right {get; set;}

    public int Value {get; set;}

    public BinaryTreeNode(int val,

                                           BinaryTreeNode left = null,

                                           BinaryTreeNode right = null)

    {

        this.Left = left;

        this.Right = right;

        this.Value = val;

    }

}

class BinaryTree

{

    public List<int> BoundaryTraversal()

    {

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

        if (this.Root == null)

        {

            return result;

        }

        result.Add(this.Root.Value);

        this.TraverseLeftBoundary(this.Root.Left, result);

        // Avoid leaf traversing if root itself is leaf

        if (this.Root.Left != null || this.Root.Right != null)

        {

            this.TraverseLeaves(this.Root, result);

        }

        this.TraverseRightBoundary(this.Root.Right, result);

        return result;

    }

    

    private void TraverseLeftBoundary(BinaryTreeNode node,

                                                              List<int> result)

    {

        if (node == null ||

            (node.Left == null && node.Right == null))

        {

            return;

        }

        if (node.Left != null)

        {

            result.Add(node.Value);

            this.TraverseLeftBoundary(node.Left, result);

        }

        else

        {

            result.Add(node.Value);

            this.TraverseLeftBoundary(node.Right, result);

        }

    }

    

    private void TraverseLeaves(BinaryTreeNode node,

                                                   List<int> result)

    {

        if (node == null)

        {

            return;

        }

        this.TraverseLeaves(node.Left, result);

        if (node.Left == null && node.Right == null)

        {

            result.Add(node.Value);

        }

        this.TraverseLeaves(node.Right, result);

    }

    

    private void TraverseRightBoundary(BinaryTreeNode node,

                                                                List<int> result)

    {

        if (node == null ||

            (node.Left == null && node.Right == null))

        {

            return;

        }

        if (node.Right != null)

        {

            this.TraverseRightBoundary(node.Right, result);

            result.Add(node.Value);

        }

        else

        {

            this.TraverseRightBoundary(node.Left, result);

            result.Add(node.Value);

        }

    }

    public BinaryTreeNode Root {get; set;}

}

Complexity: O(n)

[LeetCode] Longest Continuous Increasing Subsequence

Problem: Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly increasing.

Approach: It's a simple implementation problem. You can directly look at the implementation to understand the approach.

Implementation in C#:

    public int FindLengthOfLCIS(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        int maxCISLength = 1;

        int currCISLength = 1;

        int prevIndex = 0;

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

        {

            if (nums[i] > nums[prevIndex])

            {

                ++currCISLength;

                if (currCISLength > maxCISLength)

                {

                    maxCISLength = currCISLength;

                }

            }

            else

            {

                currCISLength = 1;

            }

            prevIndex = i;

        }

        return maxCISLength;

    }

Complexity: O(n)

[LeetCode] Shortest Completing Word

Problem: Given a string licensePlate and an array of strings words, find the shortest completing word in words.

A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.

For example, if licensePlate = "aBc 12c", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef", "caaacab", and "cbca".

Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.

Example:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.

Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.

Approach: This is a simple problem to solve. We can easily solve it using using two hash maps. Directly look at the implementation to understand the approach.

Implementation in C#:

    public string ShortestCompletingWord(string licensePlate, string[] words)

    {

        var plateCharsMap = new int[26];

        foreach(char ch in licensePlate)

        {

            if (Char.IsLetter(ch))

            {

                ++plateCharsMap[Char.ToLower(ch) - 'a'];

            }

        }

        string result = null;

        foreach (string word in words)

        {

            int length = word.Length;

            var wordCharMap = new int[26];

            foreach (char ch in word)

            {

                ++wordCharMap[ch - 'a'];

            }

            if (this.IsCompleteWord(plateCharsMap, wordCharMap))

            {

                if (result == null || length < result.Length)

                {

                    result = word;

                }

            }

        }

        return result;

    }

    private bool IsCompleteWord(int[] plateCharsMap, int[] wordCharMap)

    {

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

        {

            if (plateCharsMap[i] > wordCharMap[i])

            {

                return false;

            }

        }

        return true;

    }

Complexity: O(m*n) where m is number of words and n is length of largest word.

[LeetCode] Card Flipping Game

Problem: You are given two 0-indexed integer arrays fronts and backs of length n, where the ith card has the positive integer fronts[i] printed on the front and backs[i] printed on the back. Initially, each card is placed on a table such that the front number is facing up and the other is facing down. You may flip over any number of cards (possibly zero).

After flipping the cards, an integer is considered good if it is facing down on some card and not facing up on any card.

Return the minimum possible good integer after flipping the cards. If there are no good integers, return 0.

Example:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation:
If we flip the second card, the face up numbers are [1,3,4,4,7] and the face down are [1,2,4,1,3].
2 is the minimum good integer as it appears facing down but not facing up.
It can be shown that 2 is the minimum possible good integer obtainable after flipping some cards.

Input: fronts = [1], backs = [1]
Output: 0
Explanation:
There are no good integers no matter how we flip the cards, so we return 0.

Approach: The problem description is little confusing but if you don't look at like a game instead you just look at the problem, you will understand a fact that if 

fronts[i] = backs[i]

then this number can' be a good integer as no matter how many times you flip the card the number will always be facing up. Other than these kind of integers, all other integers in both the arrays are good integers. We just need to find the minimum of these integers.

We can use HashSet to store all the not good integers in one iteration and in the second iteration we can get the minimum of all the good integers.

Implementation in C#:

    public int Flipgame(int[] fronts, int[] backs)

    {

        int length = fronts?.Length ?? 0;

        if (length  == 0)

        {

            return 0;

        }

        HashSet<int> sameFacesSet = new HashSet<int>();

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

        {

            if (fronts[i] == backs[i])

            {

                sameFacesSet.Add(fronts[i]);

            }

        }

        int minGoodInt = int.MaxValue;

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

        {

            if (!sameFacesSet.Contains(fronts[i]))

            {

                minGoodInt = Math.Min(minGoodInt, fronts[i]);

            }

            if (!sameFacesSet.Contains(backs[i]))

            {

                minGoodInt = Math.Min(minGoodInt, backs[i]);

            }

           

        }

        return minGoodInt == int.MaxValue ? 0 : minGoodInt;

    }

Complexity: O(n)

[LeetCode] Maximum Frequency Stack

Problem: Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

• FreqStack() constructs an empty frequency stack.
• void push(int val) pushes an integer val onto the top of the stack.
• int pop() removes and returns the most frequent element in the stack.
• If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

Example:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

Explanation
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].

Constraints:

• 0 <= val <= 109
• At most 2 * 104 calls will be made to push and pop.
• It is guaranteed that there will be at least one element in the stack before calling pop.

Approach: We can use two hash maps to solve this problem:

1. FrequencyMap: This map will have frequency as key and corresponding list of elements as values.
2. ElementsMap: This map will have elements as key and it's frequency as value.

Once we have two maps in our class along with a member integer say max_frequncy, We can apply following operations at push and pop:

Push: 

    ElementsMap[val] = ElementsMap[val] + 1

    curr_freq = ElementsMap[val]

    FrequencyMap[curr_freq].AddAtLast(val)

    max_freq = MAX(curr_freq, max_freq)

Pop:

    val = FrequencyMap[max_freq].GetLast()

    FrequencyMap[max_freq].RemoveLast()

    IF ISEMPTY(FrequencyMap[max_freq])):

        FrequencyMap.Remove(max_freq)

        --max_freq

    ElementsMap[val] = ElementsMap[val] - 1

    RETURN val

That's all!

Implemetation in C#:

public class FreqStack

{

    public FreqStack()

    {

        this.freqMap = new Dictionary<int, List<int>>();

        this.elementsMap = new Dictionary<int, int>();

        this.maxFreq = 0;

    }

   

    public void Push(int val)

    {

        if (!elementsMap.ContainsKey(val))

        {

            elementsMap[val] = 0;

        }

        ++elementsMap[val];

        int currFreq = elementsMap[val];

        if (!freqMap.ContainsKey(currFreq))

        {

            freqMap[currFreq] = new List<int>();

        }

        freqMap[currFreq].Add(val);

        if (currFreq > this.maxFreq)

        {

            this.maxFreq = currFreq;

        }

    }

   

    public int Pop()

    {

        int maxFreqListCount = this.freqMap[this.maxFreq].Count;

        int val = this.freqMap[this.maxFreq][maxFreqListCount - 1];

        this.freqMap[this.maxFreq].RemoveAt(maxFreqListCount - 1);

        if (this.freqMap[this.maxFreq].Count == 0)

        {

            this.freqMap.Remove(this.maxFreq);

            --this.maxFreq;

        }

        --this.elementsMap[val];

        if (this.elementsMap[val] == 0)

        {

            this.elementsMap.Remove(val);

        }

        return val;

    }

    private Dictionary<int, List<int>> freqMap;

    private Dictionary<int, int> elementsMap;

    int maxFreq;

}

Complexiy: O(1) for push and pop.