[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)    

[LeetCode] Pascal's Triangle

Problem: Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Input: numRows = 1
Output: [[1]]

Approach: It's just simple implementation problem. Please have a look at implementation directly.

Implementation in C#:

    public IList<IList<int>> Generate(int numRows)

    {

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

        if (numRows == 0)

        {

            return result;

        }

        result.Add(new List<int> {1});

        if (numRows == 1)

        {

            return result;

        }

        result.Add(new List<int> {1, 1});

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

        {

            var currRow = new List<int>();

            var lastRow = result[i - 1];

            currRow.Add(1);

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

            {

                currRow.Add(lastRow[j - 1] + lastRow[j]);

            }

            currRow.Add(1);

            result.Add(currRow);

        }

        return result;

    }

Complexity: O(n^2)

[LeetCode] Online Stock Span

Problem: Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.

The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

• For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
• Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.

Implement the StockSpanner class:

• StockSpanner() Initializes the object of the class.
• int next(int price) Returns the span of the stock's price given that today's price is price.

Example:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

Approach: This is a monotonic stack problem. We keep popping the elements from stack till the current price is greater than or equal to the top of stack and return the difference of the sequences.

The problem here if we just record the the price and not the sequence in which the values are coming we will never be able to get the number of elements less than or equal to current price until we store every price. But instead of storing every price, we  can store the pair of price and the sequence number in the stack.

We just need to be careful while storing the price, we need to store the sequence number of the last popped price from stack. What it is indicating is that the current price is the maximum price till this particular sequence number (reversed).

That's all!

Implementation  in C#:

public class StackElement

{

    public int Value {get; set;}

    public int Sequence {get; set;}

    public StackElement(int val, int seq)

    {

        this.Value = val;

        this.Sequence = seq;

    }

}

public class StockSpanner

{

    public StockSpanner()

    {

        this.stack = new Stack<StackElement>();    

    }

   

    public int Next(int price)

    {

        int retVal = 1;

        ++this.seqNo;

        int seq = this.seqNo;

        StackElement se = null;

        while(stack.Count > 0 &&

              price >= stack.Peek().Value)

        {

            se = stack.Pop();

        }

        if (se != null)

        {

            retVal = seqNo - se.Sequence + 1;

            seq = se.Sequence;

        }

        stack.Push(new StackElement(price, seq));

        return retVal;

    }

    private Stack<StackElement> stack;

    private int seqNo;

}

Complexity: O(n)

[LeetCode] Search Suggestions System

Problem: You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Explanation: The only word "havana" will be always suggested while typing the search word.

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]
Explanation: No match at all

Approach: Given this search is kind of prefix search so it's intuitive that we will use Trie. However the TrieNode will have one more field which is going to be list of sorted suggestions. We will have these suggestions at every node and we will maintain it at every insertion so that we can quickly return these suggestions. That's all!

Implementation in C#:

public class TrieNode

{

    public TrieNode(char ch)

    {

        this.Value = ch;

        this.Children = new TrieNode[26];

        this.Suggestions = new List<string>();

    }

    public char Value {get; set;}

    public TrieNode[] Children {get; set;}

    public List<string> Suggestions {get; set;}

}

public class Trie

{

    private const char ENDOFWORD = '#';

   

    public Trie()

    {

        this.root = new TrieNode('X');

    }

    public void InsertWord(string word)

    {

        var node = this.root;

        foreach (char ch in word)

        {

            int index = ch - 'a';

            if (node.Children[index] == null)

            {

                node.Children[index] = new TrieNode('*');

            }

            node = node.Children[index];

            this.AdjustSuggestions(node, word);

        }

        node.Value = ENDOFWORD;

    }

    public IList<IList<string>> GetSuggestions(string searchWord)

    {

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

        var node = this.root;

        foreach (char ch in searchWord)

        {

            int index = ch - 'a';

            if (node.Children[index] == null)

            {

                break;

            }

            node = node.Children[index];

            result.Add(node.Suggestions);

        }

        int remainingElements = searchWord.Length - result.Count;

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

        {

            result.Add(new List<string>());

        }

        return result;

    }

    private void AdjustSuggestions(TrieNode node, string word)

    {

        // We can do better here, instead of assuming max number of

        // suggestions is 3

        int count = node.Suggestions.Count;

        if (count == 0)

        {

            node.Suggestions.Add(word);

        }

        else if (count == 1)

        {

            if (String.Compare(word, node.Suggestions[0]) < 0)

            {

                node.Suggestions.Insert(0, word);

            }

            else

            {

                node.Suggestions.Add(word);

            }

        }

        else if (count == 2)

        {

            this.HandleTwoSuggestions(node, word);

        }

        else

        {

            if (String.Compare(word, node.Suggestions[2]) < 0)

            {

                node.Suggestions.RemoveAt(node.Suggestions.Count - 1);

                this.HandleTwoSuggestions(node, word);

            }

        }

    }

    private void HandleTwoSuggestions(TrieNode node, string word)

    {

        if (String.Compare(word, node.Suggestions[0]) < 0)

        {

            node.Suggestions.Insert(0, word);

        }

        else if (String.Compare(word, node.Suggestions[1]) < 0)

        {

            node.Suggestions.Insert(1, word);

        }

        else

        {

            node.Suggestions.Add(word);

        }

    }

    private TrieNode root;

}

public class Solution

{

    public IList<IList<string>> SuggestedProducts(string[] products,

                                                  string searchWord)

    {

        var trie = new Trie();

        foreach (var product in products)

        {

            trie.InsertWord(product);

        }

        return trie.GetSuggestions(searchWord);

    }

}

Complexity: O(m * n + l) where m is number of products, n is length of largest string in products and l is length of search word. 

[LeetCode] Minimum Flips to Make a OR b Equal to c

Problem: Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).

Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

Input: a = 4, b = 2, c = 7
Output: 1

Input: a = 1, b = 2, c = 3
Output: 0

Approach: Let's try simple approach where we will simply see each bit of a | b and c and decide how many flips we need.

Let's take first example itself:

• a = 2 => 0 1 0
• b = 6 => 1 1 0
• c = 5 => 1 0 1

Let's take the left most bits:

• a => 0
• b => 0
• c => 1

To make a | b 1, we need to flip one of the bits, right so flips required is 1. Now, let's look at the remaining bits:

• a => 0 1
• b => 1 1
• c => 1 0

Again let's see how many flips required to make the left most bits same of a | b and c which are:

• a => 1
• b => 1
• c => 0

Obviously we need to make both a's and b's bits 0 to make it's OR 0 so the number of flips now increased by 2 so the flips required now is 3.

Now again take a look at the remaining bits:

• a => 0
• b => 1
• c => 1

Here if you see a | b is already equal to c. 0 | 1 = 1. That means here we don't need any flip so the final answer is 3.

That is all we are trying to do using coding :)

Implementation in C#:

    public int MinFlips(int a, int b, int c)

    {

        int flips = 0;

        while (a > 0 || b > 0 || c > 0)

        {

            int rightBitA = a & 1;

            int rightBitB = b & 1;

            int rightBitC = c & 1;

            if (rightBitC == 0)

            {

                flips += (rightBitA + rightBitB);

            }

            else

            {

                flips += rightBitA == 0 && rightBitB == 0 ? 1 : 0;

            }

            a >>= 1;

            b >>= 1;

            c >>= 1;

        }

        return flips;

    }

Complexity: O(log(Max(a, b, c))

[LeetCode] Koko Eating Bananas

Problem: Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example:

Input: piles = [3,6,7,11], h = 8
Output: 4

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Approach: This is again a binary search problem but how? Where is our sorted array? Sorted array is speed of eating banana which could be in range 1, 2, 3, ...., Max(piles). Right.

Now what to compare with mid? This is easy, we need to see if with mid speed, all the bananas can be eaten or not. If all the bananas can't be eaten then that means we need to increase the speed, right. This means start will become mid + 1;

If it can be eaten then with speed mid that means we just need to check if there is a speed which is less than mid with which all the bananas can still be eaten withn h hours. Remember we need to find the minimum speed with which all the bananas can be eaten within h hours so that means we need to go left side so end will become mid.

That's all!

Implementation in C#:

    public int MinEatingSpeed(int[] piles, int h)

    {

        int start = 1;

        int end = Enumerable.Max(piles);

        while (start < end)

        {

            int mid = start + (end - start) / 2;

            if (this.BananaCanBeEaten(piles, mid, h))

            {

                end = mid;

            }

            else

            {

                start  = mid + 1;

            }

        }

        return start;

    }

    private bool BananaCanBeEaten(int[] piles, int speed, int h)

    {

        long hours = 0;

        foreach(int pile in piles)

        {

            hours += (pile / speed);

            if (pile % speed != 0)

            {

                ++hours;

            }

        }

        return hours <= h;

    }

Complexity:  O(n + nlog(max(pile)))

[LeetCode] Successful Pairs of Spells and Potions

Problem: You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Example:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful. 
Thus, [2,0,2] is returned.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 10^10

Approach: We can use binary search here. We can simply sort the potions array and then for every spell, we try to get the first index in the potions which satisfy following condition:

spell * potions[index] >= success

Once we get this index, we can simply say that for a particular spell the number of successful pairs is m - index.

That's all!

Implementation in C#:

    public int[] SuccessfulPairs(int[] spells, int[] potions, long success)

    {

        Array.Sort(potions);

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

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

        {

            result[i] = this.GetNumOfPotions(spells[i], potions, success);

        }

        return result;

    }

    private int GetNumOfPotions(int spell, int[] potions, long success)

    {

        int start = 0, end = potions.Length - 1;

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            long currValue = (long)spell * potions[mid];

            if (currValue < success)

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return potions.Length - start;

    }

Complexity: O(mlogm + nlogm)