[Amazon][GFG] Flattening a Linked List

Problem: Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:

1. a next pointer to the next node,
2. a bottom pointer to a linked list where this node is head.

Each of the sub-linked-list is in sorted order.

Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order. 

Note: The flattened list will be printed using the bottom pointer instead of the next pointer.

Example:

Input:
5 -> 10 -> 19 -> 28
|     |     |     | 
7     20    22   35
|           |     | 
8          50    40
|                 | 
30               45
Output:  5-> 7-> 8- > 10 -> 19-> 20->
22-> 28-> 30-> 35-> 40-> 45-> 50.
Explanation:
The resultant linked lists has every 
node in a single level.
(Note: | represents the bottom pointer.)

Input:
5 -> 10 -> 19 -> 28
|          |                
7          22   
|          |                 
8          50 
|                           
30              
Output: 5->7->8->10->19->22->28->30->50
Explanation:
The resultant linked lists has every
node in a single level.

(Note: | represents the bottom pointer.)

Approach: We can treat every node as separate list where next pointer is bottom pointer. Now this will just become the problem of merging sorted lists.

That's all!

Implementation in Java:

    Node flatten(Node root)

    {

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

    {

        return root;

    }

    root.next = flatten(root.next);

    return merge(root, root.next);

    }

    

    private Node merge(Node node1, Node node2)

    {

        if (node1 == null)

        {

            return node2;

        }

        if (node2 == null)

        {

            return node1;

        }

        Node result = null;

        if (node1.data <= node2.data)

        {

            result = node1;

            result.bottom = merge(node1.bottom, node2);

        }

        else

        {

            result = node2;

            result.bottom = merge(node1, node2.bottom);

        }

        result.next = null;

        return result;

    }

Complexity: O(n) where n is total number of nodes in the list including the bottom nodes.

[Amazon][LeetCode] Best Time to Buy and Sell Stock

Problem: You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Approach: One way to do it is we can maintain an array leftMin where leftMin[i] will give the minimum value in the prices[0...i]. Similarly we can maintain an array rightMax where rightMax[i] will give the maximum of prices[i...n-1]. It is obvious that maximum of all the rightMax[i] - leftMin[i] where i = 0...n-1 will be our answer.

The above approach is a big optimiztion over brute force approach but it's still doing three iterations and moreover the space is 2*n. Let's try to do better.

Instead of maintaining rightMax array we can have a variable maxElement which gives at any ith index the maximum of prices[i...n-1] and then we can just return the max of maxElement - leftMin[i] for i = 0...n-1. See now we have just save n space and also we are saving one iteration.

If we see like maxElement, we can maintain a minElement which gives at ith index the min of pices[0...i], so now do we need to actually need to create any addition array? No right. Actually we don't need maxElement from right. At any i (i = 0...n-1), if we have Min(prices[0...i]) which is our minElement, we can say the max profit using prices[i] will be prices[i] - minElement so if we take max of all prices[i] - minElement for every i = 0...n-1 then we will have our answer.

That's all!

Implementation in C#:

Using left min array:

    public int MaxProfit(int[] prices)

    {

        int length = prices?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int[] leftMinArr = new int[length];

        leftMinArr[0] = prices[0];

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

        {

            leftMinArr[i] = Math.Min(leftMinArr[i - 1], prices[i]);

        }

        int maxElement = prices[length - 1];

        int maxProfit = Math.Max(0, maxElement - leftMinArr[length - 1]);

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

        {

            maxElement = Math.Max(maxElement, prices[i]);

            maxProfit = Math.Max(maxProfit, maxElement - leftMinArr[i]);

        }

        return maxProfit;

    }

Without using extra space:

    public int MaxProfit(int[] prices)

    {

        int length = prices?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int minElement = prices[0];

        int maxProfit = 0;

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

        {

            minElement = Math.Min(minElement, prices[i]);

            maxProfit = Math.Max(maxProfit, prices[i] - minElement);

        }

        return maxProfit;

    }

Complexity: O(n)    

[Amazon][LeetCode] Rotting Oranges

Problem: You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Approach: This is another BFS problem. We treat this matrix as graph where a cell is connected to another cell if they are neighbour of each other (except diagonal neighbours). We start our BFS with all the initial rotten oranges (grid[x][y] == 2) cells enqueued in a queue.

We keep incrementing the number of minutes at every iteration and make all the fresh oranges neighbours 2 (rotten). Once the BFS ends, we just need to check if there is a cell with fresh orange, if yes then we will return -1 otherwise we return the number of minutes.

Implementation in C#:

    public int OrangesRotting(int[][] grid) {

        int rows = grid?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = grid[0].Length;

        Queue<int[]> queue = new Queue<int[]>();

        int numOfFreshCells = this.GetFreshCellsAndAddRottenCellsToQueue(grid,

                                                                         queue);

        if (numOfFreshCells == 0)

        {

            return 0;

        }

        int minutes = 0;

        while (queue.Count > 0)

        {

            int size = queue.Count;

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

            {

                var cell = queue.Dequeue();

                this.AddNeighbourFreshCellsToQueue(cell,

                                                   grid,

                                                   queue,

                                                   ref numOfFreshCells);

            }

            if (queue.Count > 0)

            {

                ++minutes;

            }

        }

        return numOfFreshCells != 0 ? - 1 : minutes;

    }

    private bool IsFreshCellRemaining(int[][] grid)

    {

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

        {

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

            {

                if (grid[i][j] == 1)

                {

                    return true;

                }

            }

        }

        return false;

    }

    private void AddNeighbourFreshCellsToQueue(int[] cell,

                                               int[][] grid,

                                               Queue<int[]> queue,

                                               ref int numOfFreshCells)

    {

        // Left cell

        if (this.IsValidAndFreshCell(cell[0], cell[1] - 1, grid))

        {

            grid[cell[0]][cell[1] - 1] = 2;

            queue.Enqueue(new int[] {cell[0], cell[1] - 1});

            --numOfFreshCells;

        }

        // Right cell

        if (this.IsValidAndFreshCell(cell[0], cell[1] + 1, grid))

        {

            grid[cell[0]][cell[1] + 1] = 2;

            queue.Enqueue(new int[] {cell[0], cell[1] + 1});

            --numOfFreshCells;

        }

        // Up cell

        if (this.IsValidAndFreshCell(cell[0] - 1, cell[1], grid))

        {

            grid[cell[0] - 1][cell[1]] = 2;

            queue.Enqueue(new int[] {cell[0] - 1, cell[1]});

            --numOfFreshCells;

        }

        // Down cell

        if (this.IsValidAndFreshCell(cell[0] + 1, cell[1], grid))

        {

            grid[cell[0] + 1][cell[1]] = 2;

            queue.Enqueue(new int[] {cell[0] + 1, cell[1]});

            --numOfFreshCells;

        }

    }

    private bool IsValidAndFreshCell(int row, int col, int[][] grid)

    {

        return row >= 0 &&

               row < grid.Length &&

               col >= 0 &&

               col < grid[0].Length &&

               grid[row][col] == 1;

    }

    private int GetFreshCellsAndAddRottenCellsToQueue(int[][] grid,

                                                      Queue<int[]> queue)

    {

        int numOfFreshCells = 0;

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

        {

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

            {

                if (grid[i][j] == 1)

                {

                    ++numOfFreshCells;

                }

                else if (grid[i][j] == 2)

                {

                    queue.Enqueue(new int[] {i, j});

                }

            }

        }

        return numOfFreshCells;

    }

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

[Amazon Question] Maximum Average Subtree

Problem: Given the root of a binary tree, find the maximum average value of any subtree of that tree. 

A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.

Example:

Input: Input = [5,6,1]
Output: 6
Explanation: 
For the subtree with root as 5, the average is (5 + 6 + 1) / 3 = 4
For the subtree with root as 6, the average is 6 / 1 = 6 and similarly for subtree with root as 1, the average is 1.
The answer is 6 as it is the maximum of all the above 3 averages.

Approach: We can use post-order traversal here as if we go by bottom-up approach, we will get the average at each and every node and then we can just store the maximum of all the averages. We need to write a function which will return the sum and the number of nodes (of the subtree) but we can have a ref parameter which can then be used for maintaining the maximum average.

Implementation in C#:

    public double MaximumAverageSubtree()

    {

        if (this.Root == null)

        {

            return 0;

        }

        double maxAverage = 0;        

        this.MaximumAverageSubtree(this.Root, ref maxAverage);

        return maxAverage;

    }

    

    private double[] MaximumAverageSubtree(BinaryTreeNode node, ref double maxAverage)

    {

        if (node == null)

        {

            return new double[] {0, 0};

        }

        double[] leftSumAndCount = this.MaximumAverageSubtree(node.LeftNode, ref maxAverage);

        double[] rightSumAndCount = this.MaximumAverageSubtree(node.RightNode, ref maxAverage);

        double sum = leftSumAndCount[0] + rightSumAndCount[0] + node.Value;

        double count = leftSumAndCount[1] + rightSumAndCount[1] + 1;

        double average = sum / count;

        if (average > maxAverage)

        {

            maxAverage = average;

        }        

        return new double[] {sum, count};

    }

Complexity: O(n)

[Amazon Question] Largest Unique Number in an array

Problem: Given an array of integers, return the largest integer that only occurs once. If no integer occurs once, return -1.

Example:

Input: [2,5,3,7,4,7,2,3]
Output: 5
Explanation: The maximum integer in the array is 7 but it is repeated. The number 5 occurs only once, so it's the answer.

Approach: We can solve it using hashing easily. Just look at the implementation to understand the approach.

Implementation in C#:

    public int LargestUniqueNumber(int[] nums) 

    {

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

        foreach(int num in nums)

        {

            if (!freqMap.ContainsKey(num))

            {

                freqMap[num] = 0;

            }

            ++freqMap[num];

        }

        int max = int.MinValue;

        foreach(var kv in freqMap)

        {

            if (kv.Value == 1 && kv.Key > max)

            {

                max = kv.Key;

            }

        }        

        return max == int.MinValue ? -1 : max;

    }

Complexity: O(n)

[Amazon Question] Best Time to Buy and Sell Stock with Transaction Fee

Problem: You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note that you can't engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[4] = 10
The total profit is (10 - 1 - 3) = 6.

Approach: Like any other Buy and sell stock problem before, we are going to use DP here too. We are going to maintain two variables:

1. maxProfitByHoldingStock: The maximum profit we can have if we hold a stock.
2. maxProfitWithNoStock: The maximum profit we can have if we don't have any stock.

At 0th day, the values of these variables will be:

• maxProfitByHoldingStock = -prices[0] // Buy a stock
• maxProfitWithNoStock = 0 // Can't sell if didn't buy anything.

Now at any ith day, we can either sell a stock or buy a stock:

• Sell a stock: maxProfitWithNoStock  = MAX(maxProfitWithNoStock, maxProfitByHoldingStock + prices[i] - fee)
• Buy a stock: maxProfitByHoldingStock = MAX(maxProfitByHoldingStock, maxProfitWithNoStock - prices[i])

In the end, it is obvious that maxProfitWithNoStock  will be our answer.

Implementation in C#:

    public int MaxProfit(int[] prices, int fee)

    {

        int length = prices?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int maxProfitWithNoStocks = 0;

        int maxProfitWithStocks = -prices[0];

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

        {

            maxProfitWithNoStocks = Math.Max(maxProfitWithNoStocks,

                                             maxProfitWithStocks + prices[i] - fee);

            maxProfitWithStocks = Math.Max(maxProfitWithStocks,

                                           maxProfitWithNoStocks - prices[i]);

        }

        return maxProfitWithNoStocks;

    }

Complexity: O(n)

[Amazon Question] Top K frequent Words

Problem: Given an array of strings. Return the top k frequent strings in the input array in descending order. If frequency matches then the word with lower alphabetical order should come first.

Example:

Input: ["i", "love", "cricket", "i", "love", "tennis"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 1
Output: ["i"]

Approach: Its similar to the problem of getting top k frequent integers. We will use quick select here too but in the end we need to sort the output of quick select to make sure in case of frequency matches, word with lower alphabetical comes first.

Implementation in C#:

    public IList<string> TopKFrequent(string[] words, int k) 

    {

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

        foreach (string word in words)

        {

            if (!frequencyMap.ContainsKey(word))

            {

                frequencyMap[word] = 0;

            }

            ++frequencyMap[word];

        }

        string[] uniqueWords = frequencyMap.Keys.ToArray();

        string[] kFrequentWords = this.TopKFrequentQuickSelect(uniqueWords, uniqueWords.Length - k + 1, 0, uniqueWords.Length - 1, frequencyMap, k);

        Array.Sort(kFrequentWords, (w1, w2) => {

            int firstCompare = frequencyMap[w2].CompareTo(frequencyMap[w1]);

            if (firstCompare != 0)

            {

                return firstCompare;

            }

            return w1.CompareTo(w2);

        });

        return new List<string>(kFrequentWords);

    }

    

    private string[] TopKFrequentQuickSelect(string[] uniqueWords, int k, int start, int end, Dictionary<string, int> frequencyMap, int length)

    {

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

        {

            int pos = this.RandomPartition(uniqueWords, start, end, frequencyMap);

            if (pos - start + 1 == k)

            {

                return this.Subarray(uniqueWords, pos, length);

            }

            else if (pos - start + 1 > k)

            {

                return this.TopKFrequentQuickSelect(uniqueWords, k, start, pos - 1, frequencyMap, length);

            }

            return this.TopKFrequentQuickSelect(uniqueWords, k - (pos - start + 1), pos + 1, end, frequencyMap, length);

        }

        return new string[] {};

    }

    

    private int RandomPartition(string[] uniqueWords, int start, int end, Dictionary<string, int> frequencyMap)

    {

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

        this.SwapElements(uniqueWords, index, end);

        return this.Partition(uniqueWords, start, end, frequencyMap);

    }

    

    private int Partition(string[] uniqueWords, int start, int end, Dictionary<string, int> frequencyMap)

    {

        string x = uniqueWords[end];

        int i = start;

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

        {

            if ((frequencyMap[uniqueWords[j]] < frequencyMap[x]) 

                || (frequencyMap[uniqueWords[j]] == frequencyMap[x] && string.Compare(uniqueWords[j], x) > 0))

            {

                this.SwapElements(uniqueWords, i, j);

                ++i;

            }

        }

        this.SwapElements(uniqueWords, i, end);

        return i;

    }

    

    private void SwapElements(string[] uniqueWords, int i, int j)

    {

        string temp = uniqueWords[i];

        uniqueWords[i] = uniqueWords[j];

        uniqueWords[j] = temp;

    }

    

    private string[] Subarray(string[] uniqueWords, int start, int length)

    {

        string[] subArray = new string[length];

        Array.Copy(uniqueWords, start, subArray, 0, length);

        return subArray;

    }

Complexity: O(n + klogk)

[Amazon Question][LeetCode] 24 Game

Problem: You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

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

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Approach: This problem is kind of backtracking / DFS problem where we need to try every combination and see if it is giving the desired result or not. If not then we return false otherwise true.

Given that we can apply '( and ')', we just don't need to care about the sequence. Basically we take two cards and then replace these cards with all the possible results one by one in the array and see if we can get the value 24 so you see at every step we are reducing the number of cards by 1. Hence our decision condition / end of recursion condition will be when cards just have length 1. When we have only one card, we can check if the card is equal to 24 or not and return accordingly.

The possible results of two cards c1 and c2 could be:

1. c1 + c2
2. c1 - c2
3. c2 - c1
4. c1 * c2
5. c1 / c2 here c2 must not be 0
6. c2 / c1 here c1 must not be 0

Please also note that '/' is floating point operator here so at the final check we should consider some div error like .001 or .0001.

Implementation in C#:

        public static bool JudgePoint24(int[] nums)

        {

            List<double> cards = new List<double>();

            foreach (int num in nums)

            {

                cards.Add((double)num);

            }

            return CanGetValue(cards);

        }

        private static bool CanGetValue(List<double> cards)

        {

            int len = cards.Count;

            if (len == 1)

            {

                return Math.Abs(cards[0] - 24) < 1e-2;

            }

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

            {

                double card1 = cards[i];

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

                {

                    double card2 = cards[j];

                    List<double> possibleResults = new List<double> { card1 + card2, card1 - card2, card2 - card1, card1 * card2 };

                    if (card1 != 0)

                    {

                        possibleResults.Add(card2 / card1);

                    }

                    if (card2 != 0)

                    {

                        possibleResults.Add(card1 / card2);

                    }

                    List<double> nextCards = new List<double>();

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

                    {

                        if (k == i || k == j)

                        {

                            continue;

                        }

                        nextCards.Add(cards[k]);

                    }

                    foreach (double result in possibleResults)

                    {

                        nextCards.Add(result);

                        if (CanGetValue(nextCards))

                        {

                            return true;

                        }

                        nextCards.RemoveAt(nextCards.Count - 1);

                    }

                }

            }

            return false;

        }

Complexity: O(1) as you see there will be at max 4C2 * 4 * 3C2 * 4 * 2C2 * 4  = 12 * 4 * 6 * 4 * 2 * 4 = 9216 iterations. However if we want to generalize it, It will be:

nC2 * 4 * (n-1)C2 * 4 * (n-2)C2 * 4....2C2 * 4

= 4*(n-1)* ( n*(n-1) * (n-1)*(n-2) * (n-2)*(n-3) *....*2)

= 4 * (n - 1) * ((n * (n - 1) * (n -2) * (n - 3)...* 2) * ((n - 1) * (n - 2) * (n - 3) * ... * 2)))

 = 4 * (n - 1) * (!n * !n-1)

= O(n * !n * !n -1)

[Amazon Question] Reorganize String

Problem: Given a string, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Example:

Input: str = "aabc"
Output: "abac"

Approach: Basically here we are using greedy approach. First we build a heap/priority queue of characters of string based on their number of occurrences / frequencies. 

Once we build this heap, we can have a loop till the heap has 2 or more elements. In this loop we do following steps:

• firstMaxChar = heap.Pop()
• secondMaxChar = heap.Pop()
• Append firstMaxChar into result
• Append secondMaxChar into result
• Reduce the frequencies of firstMaxChar and secondMaxChar by 1.
• if frequency of firstMaxChar is more than 0 then add firstMaxChar back to the heap with the reduced frequency
• if frequency of secondMaxChar is more than 0 then add secondMaxChar back to the heap with the reduced frequency

After this loop we can have at max 1 element in the heap. If heap contains an element then we can append this last character to result if it's frequency is 1. If frequency is more than 1 then we know that we can't build the string as we will have repeated neighbors so we should return empty string.

The other simple approach would be to get the character with the maximum frequency and place it first on alternate indices. Now take the other characters and place it in the same way. That's too greedy right but it works :)

Implementation in C#:

Approach 1:

Implementation of Priority Queue is given here,

        public class TupleComparer : IComparer<Tuple<char, int>>

        {

            public int Compare([AllowNull] Tuple<char, int> x, [AllowNull] Tuple<char, int> y)

            {

               return y.Item2 - x.Item2;

            }

        }

        public static string ReorganizeString(string str)

        {

            int[] frequencies = new int[26];

            int uniqueChars = 0;

            foreach (char ch in str)

            {

                if (frequencies[ch - 'a'] == 0)

                {

                    ++uniqueChars;

                }

                ++frequencies[ch - 'a'];

            }

            PriorityQueue<Tuple<char, int>> priorityQueue = new PriorityQueue<Tuple<char, int>>(uniqueChars, new TupleComparer());

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

            {

                if (frequencies[i] > 0)

                {

                    if (frequencies[i] > (str.Length + 1) / 2)

                    {

                        return string.Empty;

                    }

                    priorityQueue.Push(new Tuple<char, int>((char)('a' + i), frequencies[i]));

                }

            }

            string result = string.Empty;

            while (priorityQueue.Count > 1)

            {

                char firstMaxChar = priorityQueue.Top.Item1;

                priorityQueue.Pop();

                char secondMaxChar = priorityQueue.Top.Item1;

                priorityQueue.Pop();

                result += firstMaxChar;

                result += secondMaxChar;

                --frequencies[firstMaxChar - 'a'];

                if (frequencies[firstMaxChar - 'a'] > 0)

                {

                    priorityQueue.Push(new Tuple<char, int>(firstMaxChar, frequencies[firstMaxChar - 'a']));

                }

                --frequencies[secondMaxChar - 'a'];

                if (frequencies[secondMaxChar - 'a'] > 0)

                {

                    priorityQueue.Push(new Tuple<char, int>(secondMaxChar, frequencies[secondMaxChar - 'a']));

                }

            }

            if (priorityQueue.Count > 0)

            {

                char lastChar = priorityQueue.Top.Item1;

                if (frequencies[lastChar - 'a'] > 1)

                {

                    return string.Empty;

                }

                result += lastChar;

            }

            return result;

        }

Approach 2:

        public string ReorganizeString(string s)

    {

        int maxFreq = 1;

        int[] freqMap = new int[26];

        char maxChar = s[0];

        foreach (char ch in s)

        {

            freqMap[ch - 'a']++;

            if (maxFreq < freqMap[ch - 'a'])

            {

                maxFreq = freqMap[ch - 'a'];

                maxChar = ch;

            }

        }

        if (maxFreq == 1)

        {

            return s;

        }

        if (maxFreq > (s.Length + 1) / 2)

        {

            return string.Empty;

        }

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

        int writeIndex = 0;

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

        {

            tempResult[writeIndex] = maxChar;

            writeIndex += 2;

            --freqMap[maxChar - 'a'];

        }

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

        {

            while (freqMap[i] > 0)

            {

                if (writeIndex >= s.Length)

                {

                    writeIndex = 1;

                }

                tempResult[writeIndex] = (char)(i + 'a');

                writeIndex += 2;

                --freqMap[i];

            }

        }

        return new string(tempResult);

    }

Complexity: Approach 1: O(nlogn), Approach 2: O(n)

[Amazon Question][LeetCode] Valid Sudoku

Problem: Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

• Each row must contain the digits 1-9 without repetition.
• Each column must contain the digits 1-9 without repetition.
• Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

Example:

Input: (Above image)board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Approach: We can use three hashsets here to validate if a number is repeated in the same row or column or in the box. The only problem here is how to calculate the box index. Here is how we can get it:

box_index = (row / 3) * 3 + col / 3

 That's all!

Implementation in C#:

    public bool IsValidSudoku(char[][] board)

    {

        HashSet<char>[] rowNums = new HashSet<char>[9];

        HashSet<char>[] colNums = new HashSet<char>[9];

        HashSet<char>[] boxNums = new HashSet<char>[9];

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

        {

            rowNums[i] = new HashSet<char>();

            colNums[i] = new HashSet<char>();

            boxNums[i] = new HashSet<char>();

        }

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

        {

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

            {

                char num = board[i][j];

                if (num != '.')

                {

                    int boxIndex = (i / 3) * 3 + j / 3;                    

                    if (!rowNums[i].Add(num) ||

                        !colNums[j].Add(num) ||

                        !boxNums[boxIndex].Add(num))

                    {

                        return false;

                    }

                }

            }

        }        

        return true;    

    }

Complexity: O(n^2) where n is number of rows and column. We can say it is constant complexity too as n is always 9 here.