[Uber] Minimum candies required to distribute among children with ratings

Problem: There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example:

Input: [2, 1, 0, 2, 3, 1, 6]
Output: 14
Explanation: You can allocate 3, 2, 1, 2, 3, 1, 2 candies respectively.

Approach: Looks like Trapping water problem. We can use the same approach here.

Implementation in C#:

    public int Candy(int[] ratings)

    {

        int length = ratings?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        int[] candies = new int[length];

        Array.Fill(candies, 1);

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

        {

            if (ratings[i] > ratings[i - 1])

            {

                candies[i] = candies[i - 1] + 1;

            }

        }

        int totalCandies = candies[length - 1];

        for (int i = length - 2; i >= 0; --i)

        {

            if (ratings[i] > ratings[i + 1])

            {

                candies[i] = Math.Max(candies[i], candies[i + 1] + 1);

            }

            totalCandies += candies[i];

        }

        return totalCandies;

    }

Complexity: O(n)

[Google Question] Gas Station

Problem: There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Example (taken from leetcode): 

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Approach: First approach that come to our mind is to treat every index as starting point and see if we can complete the tour but it will be expensive as it will take O(n^2) time. Here is how this approach looks like:

• FOR i = 0  To n - 1
• currGas = 0
• j = i
• isPossibleToMove = gas[i] >= cost[i]
• WHILE (isPossibleToMove)
• currGas = currGas + (gas[j] - cost[j])
• isPossibleToMove = currGas >= 0
• j = (j + 1) % n
• IF j == i AND isPossibleToMove
• RETURN i
• RETURN -1

Let's try to do better. We know that if Sum(gas) is grater than or equal to Sum(cost) then we can definitely complete the tour. We don't know where the starting point is but we are sure that there must exist at least one starting point from where we can complete the tour.

We also know that if gas[i] < cost[i] for any i then we can't start from i. We can generalize this fact as if currGasAmount at any station 'i' is less than 0 then we can say that one can't reach this station so we mark this as starting station. 

Please note that currGasAmount is the Sum(gas[0..i]) - Sum(cost[0...i]). Here is how this approach looks like:

• startStation = 0
• totalGas = 0
• currGas = 0
• FOR i = 0 to n-1
• totalGas = totalGas + (gas[i] - cost[i])
• currGas = currGas + (gas[i] - cost[i])
• IF currGas < 0
• startStation = i + 1
• currGas = 0
• IF totalGas < 0
• RETURN -1
• RETURN startStation

Now there might be a question in your mind that how we can say that starting station is k + 1 if currGas till kth station is negative. Let's prove it by contradiction:

Let's say our starting station is S(i). The algorithm above ensures that it is possible to go from S(i) to S(n) so we can say that there exist a station S(k) where 0 < k < i such that one can't reach S(k) from S(i).

Let's define a variable Gas(i) which is equals to gas[i]-cost[i]. 

First thing of which we are sure here is:

Sum(Gas(0)...Gas(n)) >= 0

We can write the above statement as:

Sum(Gas(0)...Gas(k)) + Sum(Gas(k+1)...Gas(i-1)) + Sum(Gas(i)+...Gas(n)) >= 0   (1)

Now we know that Sun(Gas(k + 1)...Gas(i-1)) is negative that's why our starting station is S(i). It could be 0 in case of k = i - 1. So we can say:

Sum(Gas(k + 1)...Gas(i - 1)) <= 0 (2)

According to (1) and (2):

Sum(Gas(0)...Gas(k)) + Sum(Gas(i)...Gas(n)) >= 0 (3)

Now because S(k) is unreachable from S(i), we can say:

Sum(Gas(i)...Gas(n) + Sum(Gas(0)...Gas(k)) < 0 (4)

If you look at (3) and (4), its a contradiction. Therefore the assumption that there exist a station S(k) where 0 < k < i such that one can't reach S(k) from S(i) is false.

That's all!

     

Implementation in C#:

    public int CanCompleteCircuit(int[] gas, int[] cost)

    {

        int length = gas?.Length ?? 0;

        if (length <= 1)

        {

            return length - 1;

        }

        int totalGas = 0;

        int currGas = 0;

        int startPoint = 0;

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

        {

            totalGas += (gas[i] - cost[i]);

            currGas += (gas[i] - cost[i]);

            if (currGas < 0)

            {

                startPoint = (i + 1);

                currGas = 0;

            }

        }

        return totalGas >= 0 ? startPoint : -1;

    }

Complexity: O(n)

Given a reference of a node in a connected undirected graph. Create a clone of the graph.

Approach: Use DFS with hash (node value as key and graph node as value). In case of DFS we do not traverse the node if it is already visited and here we do the same return the node from the hash.

        public GraphNode CloneGraph(GraphNode node)

        {

            if (node == null)

            {

                return null;

            }

            // Assuming every node has unique value.

            Dictionary<int, GraphNode> visited = new Dictionary<int, GraphNode>();

            return this.CloneGraph(node, visited);

        }

        private GraphNode CloneGraph(GraphNode sourceNode, Dictionary<int, GraphNode> visited)

        {

            if (visited.ContainsKey(sourceNode.Value))

            {

                return visited[sourceNode.Value];

            }

            GraphNode destNode = new GraphNode(sourceNode.Value, new List<GraphNode>());

            visited[sourceNode.Value] = destNode;

            foreach (GraphNode node in sourceNode.Neighbors)

            {

                destNode.Neighbors.Add(this.CloneGraph(node, visited));

            }

            return destNode;

        }

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example:

Input: "abcbm"
Output:
[
  ["a","bcb","m"],
  ["a","b","c","b","m"]
]

Approach: Its kind of permutation problem but here we only go to next index if sub-string is palindrome.

        public IList<IList<string>> PalindromPartitions(string s)

        {

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

            if (s?.Length <= 0)

            {

                return result;

            }

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

            this.PalindromPartitionsInternal(s, result, currResult, 0);

            return result;

        }

        private void PalindromPartitionsInternal(string s, List<IList<string>> result, List<string> currResult, int startIndex)

        {

            if (startIndex == s.Length)

            {

                result.Add(currResult);

                return;

            }

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

            {

                if (this.IsPalindrome(s, startIndex, i))

                {

                    currResult.Add(s.Substring(startIndex, i - startIndex + 1));

                    this.PalindromPartitionsInternal(s, result, currResult, i + 1);

                    currResult.RemoveAt(currResult.Count - 1);

                }

            }

        }

Palindrome Partitioning

Problem: Given a string s, partition s such that every sub-string of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. 

Example: 

Input: s = "abcbm"
Output: 2
Explanation: The palindrome partitioning ["a","bcb", "m"] could be produced using 2 cut.

Approach: Use DP here. Maintain a 2D table say IsPlaindrome where IsPlaindrome [i][j] is true, only if sub-string s[i...j] is palindrome. Once it is filled, we can have another 1D table say MinCuts where MinCuts[i] will give the minimum number of cuts required to solve this problem for sub-string s[0...i].

Here is how we can fill MinCuts -

1. If s[0..i] is palindrome i.e. IsPlaindrome[0][i] is true then MinCuts[i] = 0.
2. if not then for each j = 0...i, take the min of 1 + C[j] and assign it to C[i]. Basically check by cutting at each and every index and take the minimum. We can optimize it bit with checking only if s[j+1...i] is palindrome.

        public int MinPalindromeCut(string s)

        {

            bool[,] isPlaindrome = new bool[s.Length, s.Length];

            // Every substring of length 1 is a palindrome

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

            {

                isPlaindrome[i, i] = true;

            }

            // Initialize Palindrome table to according to s[i...j] is palindrome or not

            for (int length = 2; length <= s.Length; ++length)

            {

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

                {

                    int j = i + length - 1; // end index

                    isPlaindrome[i, j] = length == 2 ? s[i] == s[j] : s[i] == s[j] && isPlaindrome[i + 1, j - 1];

                }

            }

            int[] minCut = new int[s.Length];

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

            {

                // If till s[0...i] is palindrome then no cut is required

                if (isPlaindrome[0, i])

                {

                    minCut[i] = 0;

                }

                else

                {

                    minCut[i] = int.MaxValue;

                    // Checking for each cut

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

                    {

                        if (isPlaindrome[j + 1, i] && minCut[j] + 1 < minCut[i])

                        {

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

                        }

                    }

                }

            }

            return minCut[minCut.Length - 1];

        }

Complexity: O(n^2)

[LeetCode] Surrounded Regions

Problem: Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. 

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example:

X X X X
X O O X
X X O X
X O X X

Will become - 

X X X X
X X X X
X X X X
X O X X

Approach: This looks like Flood Fill problem with new color as 'X' and previous color as 'O'. The only exception is  that a ‘O’ is not replaced by ‘X’ if it lies in region that ends on a boundary so we just have to work around it. Here are the steps which we can follow -

1. Traverse the matrix and replace all 'O' with a special character say '#'.
2. Traverse all the four edges and call FloodFill('#', 'O') for every '#' on edges as we don't want to replace those with 'X'. (Previous Color - '#', New Color - 'X').
3. Traverse the matrix and replace all remaining '#' with 'X' using FloodFill('#', 'X'). (Previous color '#' and New color - 'X')

Implementation in C#:

        public void SolveRegions(char[][] board)

        {

            if (board?.Length <= 0)

            {

                return;

            }

            // Step 1: Replace all 'O' with '#' 

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

            {

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

                {

                    if (board[i][j] == 'O')

                    {

                        board[i][j] = '#';

                    }

                }

            }

            // Step 2: Replace all boundary '#' with 'O' as we don't want to change those

            // Top Boundary

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

            {

                if (board[0][i] == '#')

                {

                    this.FloodFill(board, 0, i, '#', 'O');

                }

            }

            // Bottom Boundary

            int bottomRow = board.Length - 1;

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

            {

                if (board[bottomRow][i] == '#')

                {

                    this.FloodFill(board, bottomRow, i, '#', 'O');

                }

            }

            // Left Boundary

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

            {

                if (board[i][0] == '#')

                {

                    this.FloodFill(board, i, 0, '#', 'O');

                }

            }

            // Right Boundary

            int rightColumn = board[0].Length - 1;

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

            {

                if (board[i][rightColumn] == '#')

                {

                    this.FloodFill(board, i, rightColumn, '#', 'O');

                }

            }

            // Step 3: Replace all remaining '#' with 'X'

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

            {

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

                {

                    if (board[i][j] == '#')

                    {

                        this.FloodFill(board, i, j, '#', 'X');

                    }

                }

            }

        }

        private void FloodFill(Char[][] board, int x, int y, char previousChar, char newChar)

        {

            if (x < 0 || x >= board.Length || y < 0 || y >= board[0].Length || board[x][y] != previousChar)

            {

                return;

            }

            board[x][y] = newChar;

            this.FloodFill(board, x - 1, y, previousChar, newChar);

            this.FloodFill(board, x + 1, y, previousChar, newChar);

            this.FloodFill(board, x, y - 1, previousChar, newChar);

            this.FloodFill(board, x, y + 1, previousChar, newChar);

        }

Complexity: O(m x n) where m is number of rows and n is number of columns.

Flood fill Algorithm

Problem: Given a 2D screen (matrix), location of a pixel in the screen and a color, replace color of the given pixel and all adjacent same colored pixels with the given color. (Like what MS Paint does for flood fill)

Approach: Use of recursion for every neighbor pixel.

        public void FloodFill(int[,] screen, int x, int y, int newColor)

        {

            int previousColor = screen[x, y];

            this.FloodFill(screen, x, y, previousColor, newColor);

        }

        private void FloodFill(int[,] screen, int x, int y, int previousColor, int newColor)

        {

            if (x < 0 || x >= screen.GetLength(0) || y < 0 || y >= screen.GetLength(1) || screen[x,y] != previousColor)

            {

                return;

            }

            screen[x, y] = newColor;

            this.FloodFill(screen, x - 1, y, previousColor, newColor);

            this.FloodFill(screen, x + 1, y, previousColor, newColor);

            this.FloodFill(screen, x, y - 1, previousColor, newColor);

            this.FloodFill(screen, x, y + 1, previousColor, newColor);

        }