[LeetCode] Rearrange Spaces Between Words

Problem: You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It's guaranteed that text contains at least one word.

Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.

Return the string after rearranging the spaces.

Example:

Input: text = "  this   is  a sentence "
Output: "this   is   a   sentence"
Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.

Input: text = " practice   makes   perfect"
Output: "practice   makes   perfect "
Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.

Input: text = "hello   world"
Output: "hello   world"

Input: text = "  walks  udp package   into  bar a"
Output: "walks  udp  package  into  bar  a "

Input: text = "a"
Output: "a"

Approach: An easy problem to solve. We can traverse the given text and count the number of words and spaces. Now our task becomes easy:

Number_Of_Spaces_Between_Words = Number_Of_Spaces / Number_Of_Words

Number_Of_Spaces_At_End = Number_Of_Spaces % Number_Of_Words

We just need to take care of some boundary conditions and we are done.

Implementation in C#:

    public string ReorderSpaces(string text) 

    {

        int numOfSpaces = 0;

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

        for (int i = 0; i < text.Length; )

        {

            if (text[i] == ' ')

            {

                ++numOfSpaces;

                ++i;

            }

            else

            {

                StringBuilder stringBuilder = new StringBuilder();

                while (i < text.Length && text[i] != ' ')

                {

                    stringBuilder.Append(text[i++]);

                }

                words.Add(stringBuilder.ToString());

            }

        }

        int spacesBetweenWords = 0;

        int spacesRemaining = numOfSpaces;

        if (words.Count > 1)

        {

            spacesBetweenWords = numOfSpaces / (words.Count - 1);

            spacesRemaining = numOfSpaces % (words.Count - 1);

        }

        StringBuilder spaceStringBuilder = new StringBuilder();

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

        {

            spaceStringBuilder.Append(' ');

        }

        StringBuilder spaceRemainingBuilder = new StringBuilder();

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

        {

            spaceRemainingBuilder.Append(' ');

        }

        return string.Join(spaceStringBuilder.ToString(), words) + spaceRemainingBuilder.ToString();

    }

Complexity: O(n)

[Indeed Question][LeetCode] Moving Average from Data Stream

Problem: Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window size.
• double next(int val) Returns the moving average of the last size values of the stream.

Example:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

Approach: We can solve this question easily by using a queue. Please look at the implementation to understand the approach.

 

Implementation in C#:

public class MovingAverage 

{

    public MovingAverage(int size) 

    {

        this.windowSize = size;

        this.queue = new Queue<int>();

        this.currSum = 0;

    }

    

    public double Next(int val) 

    {

        this.currSum += val;

        this.queue.Enqueue(val);

        if (this.queue.Count > this.windowSize)

        {

            this.currSum -= this.queue.Dequeue();

        }

        return (double)this.currSum / this.queue.Count;

    }

    

    private int currSum;

    private Queue<int> queue;

    private int windowSize;

}

Complexity: O(1)

[Apple Question][LeetCode] Logger Rate Limiter

Problem: Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

• Logger() Initializes the logger object.
• bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example:

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

Approach: Problem looks straight forward. We can maintain a hash with key as message and value as timestamp to solve this problem. Have a look at implementation to understand the approach.

Implementation in C#:

public class Logger 

{

    public Logger() 

    {

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

    }

    

    public bool ShouldPrintMessage(int timestamp, string message) 

    {

        if (this.messageTimestampDict.ContainsKey(message) && timestamp - this.messageTimestampDict[message] < 10)

        {

            return false;

        }

        this.messageTimestampDict[message] = timestamp;

        return true;  

    }

    

    Dictionary<string, int> messageTimestampDict;

}

Complexity: O(1)

[Google Question][LeetCode] Sentence Screen Fitting

Problem: Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

1. A word cannot be split into two lines.
2. The order of words in the sentence must remain unchanged.
3. Two consecutive words in a line must be separated by a single space.
4. Total words in the sentence won't exceed 100.
5. Length of each word is greater than 0 and won't exceed 10.
6. 1 ≤ rows, cols ≤ 20,000.

Example:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

Approach: Let's try the simple approach first. The approach is simple where we try to fit as many words on the row and when we find that we can't have more words on current row, we went to next row. Whenever we reach to the end of sentence array, we start from the first word of the sentence. Not much to explain, you can directly go to implementation and understand the approach.

Let's move to our second which is bit complex solution. Basically if you see we are trying to fit words into row in our first approach. In this approach we first form an string say 'words' by joining all the words in the sentence with a space and then see on every row what is the max total valid characters of words can put. We already know that we can have at most 'cols' characters. We add it to total_valid_length. Now if we find words[total_valid_length % length of words] is space (' '), then we know that we have added valid words but if it is not space then we have to decrease total_valid_length till we get the space because we can only adjust these many words in the row. In the end total_valid_length % length of words is our answer.

That's all!

Implementation in C#:

Approach 1: Brute force

    public int WordsTyping(string[] sentence, int rows, int cols) 

    {    

        int len = sentence.Length;

        int[] sentenceLength = new int[len];

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

        {

            sentenceLength[index] = sentence[index].Length;

        }

        int i = 0, row = 0, spaceRemaining = cols, cycle = 0;

        while (row < rows)

        {

            while (sentenceLength[i] <= spaceRemaining)

            {

                spaceRemaining -= sentenceLength[i] + 1;

                ++i;

                if (i == len)

                {

                    i = 0;

                    ++cycle;

                }

            }            

            ++row;

            spaceRemaining = cols;

        }  

        return cycle;

    }

Approach 2: Joining the words and then look for valid length

    public int WordsTyping(string[] sentence, int rows, int cols) 

    {    

        string words = string.Join(' ', sentence) + ' ';

        int wordsLen = sentences.Length;

        int totalProcessedLen = 0;

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

        {

            totalProcessedLen += cols;

            if (words[totalProcessedLen % wordsLen] == ' ')

            {

                ++totalProcessedLen;

            }

            else

            {

                while (totalProcessedLen >= 0 && words[totalProcessedLen % wordsLen] != ' ')

                {

                    --totalProcessedLen;

                }

                ++totalProcessedLen;

            }

        }

        return totalProcessedLen / wordsLen;

    }

Complexity: Approach 1: O(rows * cols), Approach 2: O(rows * length of the word with maximum length in the sentence)

[Google][LeetCode] Daily Temperatures

Problem: Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Example:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Approach: We can use stack here. We will keep pushing the index of temperature into the stack till we find lesser temperature then the top of the stack otherwise we just found the next greater temperature and we keep popping the temperatures which are less than the current temperature. While popping we just take the difference between current_index and popped index and write it to output array's current_index.

Implementation in C#:

    public int[] DailyTemperatures(int[] temperatures)

    {

        int length = temperatures?.Length ?? 0;

        if (length == 0)

        {

            return new int[] {};

        }

        if (length == 1)

        {

            return new int[] {0};

        }

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

        int[] result = new int[length];

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

        {

            while (stack.Count > 0 &&

                   temperatures[stack.Peek()] <= temperatures[i])

            {

                stack.Pop();

            }

            if (stack.Count == 0)

            {

                result[i] = 0;  

            }

            else

            {

                result[i] = stack.Peek() - i;

            }  

            stack.Push(i);

        }

        return result;

    }

Complexity: O(n)

[Google Question][LeetCode] Validate Stack Sequences

Problem: Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Approach: We can use stack itself :) to see if the sequence of pushes and pops are valid or not. Once we use stack, the approach is straight forward. It looks like:

• popIndex = 0
• FOR i = 0 to n - 1
• Stack.Push(pushed[i])
• WHILE Stack not empty AND Stack.Top == popped[popIndex]
• Stack.Pop()
• popIndex = popIndex + 1
• RETURN popIndex == n

That's all!

Implementation in C#:

    public bool ValidateStackSequences(int[] pushed, int[] popped) 

    {

        int j = 0;

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

        foreach (int num in pushed)

        {

            stack.Push(num);

            while (stack.Count > 0 && stack.Peek() == popped[j])

            {

                stack.Pop();

                ++j;

            }

        }

        return j == popped.Length;

    }

Complexity: O(n)

[Facebook Question][LeetCode] Backspace String Compare

Problem: Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Approach: This can be easily solved using the stack but obviously the downside is extra space. You can see the implementation. 

Let's try to reduce space. We can't traverse the string from start to end as whenever we see a backspace we need to remove the character and it will be expensive so instead of start to end, we will traverse the string from end to start. Whenever we see '#' we increase the count of backspace by 1 and if we see a character then we check if backspace count is 0 then we put the character in the result otherwise we reduce the backspace count by 1.  

That's all!

Implementation in C#:

Approach 1: Parsing string from the end to start

    public bool BackspaceCompare(string S, string T) 

    {    

        string SChas = this.GetResultString(S);

        string TChars = this.GetResultString(T);

        return SChas == TChars;

    }

    

    private string GetResultString(string str)

    {

        int bkSpCount = 0;

        StringBuilder stringBuilder = new StringBuilder();

        for (int i = str.Length - 1; i >= 0; --i)

        {

            if (str[i] == '#')

            {

                ++bkSpCount;

            }

            else

            {

                if (bkSpCount == 0)

                {

                    stringBuilder.Append(str[i]);

                }

                else

                {

                    --bkSpCount;

                }

            }

        }

        return stringBuilder.ToString();

    }

Approach 2: Using Stack

    public bool BackspaceCompare(string S, string T) 

    {

        char[] SChars = this.GetResultString(S);

        char[] TChars = this.GetResultString(T);

        if (SChars.Length != TChars.Length)

        {

            return false;

        }

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

        {

            if (SChars[i] != TChars[i])

            {

                return false;

            }

        }

        return true;

    }

    

    private char[] GetResultString(string str)

    {

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

        foreach (char ch in str)

        {

            if (ch == '#')

            {

                if (stack.Count > 0)

                {

                    stack.Pop();

                }

            }

            else 

            {

                stack.Push(ch);

            }

        }

        char[] result = new char[stack.Count];

        for (int i = result.Length - 1; i >= 0; --i)

        {

            result[i] = stack.Pop();

        }  

        return result;

    }

Complexity: O(n)

Remove Duplicates from Sorted Array

Problem: Given a sorted array, remove the duplicates in-place such that each element appears only once and returns the new length.

Example:

Input: nums = [1,1,2,2,2,3,3,3,3,4]
Output: 4, nums = [1,2,3,4,...]
Explanation: Your function should return length = 4, with the first four elements of nums being modified to 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Approach: Nothing to explain here. Ju    st look at the implementation to understand the approach as it is fairly easy.

Implementation in C#:

    public int RemoveDuplicates(int[] nums) 

    {

        if (nums?.Length == 0)

        {

            return 0;

        }    

        int j = 1;

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

        {

            if (nums[i] != nums[i - 1])

            {

                nums[j++] = nums[i];

            }

        }

        return j;

    }

Complexity: O(n)

[Microsoft Question] Shortest Unsorted Continuous Subarray

Problem: Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

Example:

Input: nums = [2,3,1,4,5]
Output: 3
Explanation: You need to sort [2,3,1] in ascending order to make the whole array sorted in ascending order.

Approach: The intuition is that the correct position of the minimum element in the unsorted subarray is the required left boundary. Similarly, the correct position of the maximum element in the unsorted subarray is the required right boundary.

One way to achieve it is first we create a copy of the original array say sortedNums and then sort it. Now for every i = 0 to n - 1 whenever we find num[i] != sortedNums[i] first time we know that this is the minimum element which is not in correct order so we mark 'i' as the left boundary. 

To get the right boundary, we could parse in reverse order i.e. i = n - 1 to 0 and whenever we find num[i] != sortedNums[i] first time we know that this is the maximum element which is not in correct order so we mark 'i' as the right boundary. Now we can return right - left + 1.

This approach will work but it will take O(nlogn) time for sorting. Let's try to do better; Can we find the min and max element of unsorted subarray without sorting? Once we find the min and max element, its easy to find the indexes where these min and max should be placed.

Let's see how to find the min number in the unsorted subarray. For every i = 1 to n - 1 whenever we find that nums[i] < nums[i - 1] that mean at 'i' unsorted subarray is started and now we can find the min of subarray nums[i...n-1] which is our minimum number.

Similarly, to get the max number we can have a loop from i = n - 2 to 0 and whenever we find nums[i] > nums[i + 1] that means we get the end of unsorted subarray. Now we can find the max of subarray nums[0...i] and which will tell us the maximum number of the unsorted subarray.

Now we just traverse the array from i = 0 to n - 1 and whenever we see that nums[i] > min then we know that this is the right position for min and hence 'i' is our left boundary. Similarly we traverse the array in reverse order i.e. j = n - 1 to 0 and whenever we find that nums[j] < max then we can say 'j' is our right boundary. Now we can return right - left + 1.

That's all!

Implementation in C#:

Approach 1: With Sorting:

    public int FindUnsortedSubarray(int[] nums) 

    {

        int[] sortedNums = (int[]) nums.Clone();

        Array.Sort(sortedNums);

        int left = -1, right = 0;

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

        {

            if (nums[i] != sortedNums[i])

            {

                left = i;

                break;

            }

        }

        // Already sorted

        if (left == -1)

        {

            return 0;

        }        

        for (int i = nums.Length - 1; i >= 0; --i)

        {

            if (nums[i] != sortedNums[i])

            {

                right = i;

                break;

            }

        }        

        return right - left + 1; 

    }

Approach 2: Without Sorting:

    public int FindUnsortedSubarray(int[] nums) 

    {

        int min = int.MaxValue, max = int.MinValue;

        bool isSorted = true;

        int len = nums.Length;

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

        {

            if (nums[i] < nums[i - 1])

            {

                isSorted = false;

            }  

            if (!isSorted)

            {

                min = Math.Min(min, nums[i]);

            }

        }

        if (isSorted)

        {

            return 0;

        }

        isSorted = true;

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

        {

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

            {

                isSorted = false;

            }

            if (!isSorted)

            {

                max = Math.Max(max, nums[i]);

            }

        }

        int left = 0, right = len - 1;

        for (; left < len; ++left)

        {

            if (nums[left] > min)

            {

                break;

            }

        }   

        for (; right >= 0; --right)

        {

            if (nums[right] < max)

            {

                break;

            }

        }        

        return right - left + 1;

    }

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

[Google Question][LeetCode] Find And Replace in String

Problem: To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously.  It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example:

Input: S = "abcd", indexes = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Input: S = "abcd", indexes = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" starts at index 0 in S, so it's replaced by "eee".
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Approach: Basically we just can't apply replacement whenever we have a match as it will disturb the original indexes of input string and because of that we might miss further replacement / matches. That means we first need to mark the valid replacements. We can have a hash table with key as index (staring index) where we need to make replacement and value as source and target string. 

If we look closely we can just string the indexes of source and replacement string in the sources and targets array which are same and also instead of hash table we can just have integer array of length of S as we just need to mark that at this index we need to replace the num characters where num is the length of ith source string with ith target string where 0 <= i < length of sources/targets. Basically we can just put "i" at a marker index where we get the match.

That's all!

 

Implementation in C#:

        public static string FindReplaceString(string S, int[] indexes, string[] sources, string[] targets)

        {

            int[] marker = new int[S.Length];

            Array.Fill(marker, -1);

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

            {

                int subStrStartIndex = indexes[i];

                int subStrLength = sources[i].Length;

                if (S.Substring(subStrStartIndex, subStrLength) == sources[i])

                {

                    marker[subStrStartIndex] = i;

                }

            }

            StringBuilder result = new StringBuilder();

            int index = 0;

            while (index < S.Length)

            {

                if (marker[index] >= 0)

                {

                    result.Append(targets[marker[index]]);

                    index += sources[marker[index]].Length;

                }

                else

                {

                    result.Append(S[index++]);

                }

            }

            return result.ToString();

        }

Complexity: O(n*maxLenOfSource + m) where n is the number of sources, m length of S.

[Google Question]First missing positive interger

Problem: Given an unsorted integer array, find the smallest missing positive integer. Please note that 0 is not a missing positive integer.

Example:

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

Approach: We can do it using external hash table / binary tree / heap or we can use sorting but it will be expensive in terms of space and time. We can use the input array itself for hashing. Please look at the two different approaches in the implementation.

Implementation in C#:

Approach 1: Using long.MaxValue for indicating that number exist

        public int FirstMissingPositive(int[] nums)

        {

            int len = nums.Length;

            long[] longCopyNums = new long[len];

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

            {

                longCopyNums[i] = nums[i];

            }

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

            {

                if (longCopyNums[i] <= 0)

                {

                    continue;

                }

                long j = longCopyNums[i];

                while (j > 0 && j <= len)

                {

                    long index = longCopyNums[j - 1];

                    longCopyNums[j - 1] = long.MaxValue;

                    j = index;

                }

            }

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

            {

                if (longCopyNums[i] != long.MaxValue)

                {

                    return i + 1;

                }

            }

            return len + 1;

        }

Approach 2: Using negative value to indicate the number exist

        public int FirstMissingPositive(int[] nums)

        {

            int len = nums.Length;

            bool containsOne = false;

            foreach(int num in nums)

            {

                if (num == 1)

                {

                    containsOne = true;

                    break;

                }

            }

            if (!containsOne)

            {

                return 1;

            }

            if (len == 1)

            {

                return 2;

            }

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

            {

                if (nums[i] <= 0 || nums[i] > len)

                {

                    nums[i] = 1;

                }

            }

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

            {

                int index = Math.Abs(nums[i]) - 1;

                if (nums[index] > 0)

                {

                    nums[index] = -nums[index];

                }

            }

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

            {

                if (nums[i] > 0)

                {

                    return i + 1;

                }

            }

            return len + 1;

        }

Complexity: O(n)

[Google Question][LeetCode] Score of Parentheses

Problem: Given a balanced parentheses string S, compute the score of the string based on the following rule:

• ( ) has score 1
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

Example:

Input: "()"
Output: 1

Input: "(())"
Output: 2

Input: "()()"
Output: 2

Input: "(()(()))"
Output: 6

Approach: We can use stack here. The approach is straight forward and you can understand it by just looking at the code. This approach will solve the problem in linear time (ignoring int to string and string to int conversions) but it will take extra space. Let's try to do better.

If you look at the problem closely, you will understand the result is sum of power of 2s. Let's see through examples:

• ( ) => 2 ^ 0 = 1
• ( ) ( ) => 2 ^0 +  2^0 = 2
• ( ( ) ) =>  2^1 = 2
• ( ( ( ) ) ) =>  2^2 = 4
• ( ( ) ) ( ( ( ) ) ) => 2^1 + 2^2 = 6

Basically inner '( )' means increment in power of 2. With this intuition just look at the implementation of approach 2 which is fairly straight forward.

Implementation in C#:

Approach 1:

    public int ScoreOfParentheses(string S) 

    {

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

        foreach (char ch in S)

        {

            if (ch == '(')

            {

                stack.Push(ch.ToString());

            }

            else

            {

                int result = 0;

                while (stack.Count > 0 && stack.Peek() != "(")

                {

                    result += int.Parse(stack.Pop());

                }

                stack.Pop();

                if (result == 0)

                {

                    stack.Push("1");

                }

                else

                {

                    stack.Push((result * 2).ToString());

                }

            }

        }

        int answer = 0;

        while (stack.Count > 0)

        {

            answer += int.Parse(stack.Pop()); 

        }

        return answer;

    }

Approach 2:

    public int ScoreOfParentheses(string S) 

    {    

        int powOfTwo = 0;

        int result = 0;

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

        {

            if (S[i] == '(')

            {

                ++powOfTwo;

            }

            else

            {

                --powOfTwo;

                if (S[i - 1] == '(')

                {

                    result += (1 << powOfTwo);

                }

            }

        }  

        return result;

    }

Complexity: O(n)

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

[Google Question][LeetCode] Linked List Components

Problem: We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Approach: A value 'val' in G is itself a connected component if the value of next node of the node with value 'val' does not exist in G. Right! Otherwise both the values are in the same connected component. We can solve this problem in many ways. 

One of the way is to start with an assumption that every value in G is a separate component and whenever we find that the value of next node of node with a value in G exist in G, we reduced the count of number of components. Here is how our algorithm will look like:

• node = head
• WHILE node != null
• hashMapList.Add(node.Value => node)
• node = node.Next
• for i = 0 to G.Length - 1
• hashSetG.Add(G[i])
• totalComponents = G.Length
• for i = 0 to G.Length - 1
• IF hashMapList[G[i]].next != null AND hashSetG.Contains(hashMapList[G[i]].next)
• totalComponents = totalComponents - 1
• RETURN totalComponents

This approach is fine and will work in linear time which we can't improve but here we are using two hashes; a hashmap and a hashset. Let's try to reduce the space.

Let's start with an assumption that we don't have any component. Now as per our definition, if a value exist in G and the value of the node which is next of node with same value does not exist in G then we have one connected component so if we traverse the list and see if current node's value does exist in G but its next node's value does not exist then we can increase the number of components by 1 so this approach will look like:

• for i = 0 to G.Length - 1
• hashSetG.Add(G[i])
• totalComponents = 0
• node = head
• WHILE node != null
• IF hashSetG.Contains(node.Value) AND (node.Next == null OR !hashSetG.Contains(node.Next.Value))
• totalComponents = totalComponents + 1
• node = node.Next
• RETURN totalComponents

If you see we are using less space and also we have reduced the number of loops

Implementation in C#:

Approach 1:

    public int NumComponents(ListNode head, int[] G) 

    {

        Dictionary<int, ListNode> listhash = new Dictionary<int, ListNode>();

        ListNode itr = head;

        while (itr != null)

        {

            listhash[itr.val] = itr;

            itr = itr.next;

        }

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

        foreach(int i in G)

        {

            gHash.Add(i);

        }

        int totalComponents = G.Length;

        foreach (int i in G)

        {

            if (listhash[i].next != null && gHash.Contains(listhash[i].next.val))

            {

                --totalComponents;

            }

        }

        return totalComponents;

    }

Approach 2:

    public int NumComponents(ListNode head, int[] G) 

    {

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

        foreach(int i in G)

        {

            gHash.Add(i);

        }

        int totalComponents = 0;

        ListNode itr = head;

        while (itr != null)

        {

            if (gHash.Contains(itr.val) && (itr.next == null || !gHash.Contains(itr.next.val)))

            {

                ++totalComponents;

            }

            itr = itr.next;

        }

        return totalComponents;

    }

Complexity: O(n)

[Facebook Question] Add two numbers represented by strings

Problem: Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Example:

Input: num1 = "99" num2 = "9"
Output: "108"

Approach: Nothing to explain here. Just look at the implementation as the approach is straight forward.

Implementation in C#:

        public string AddStrings(string num1, string num2)

        {

            char[] result = new char[Math.Max(num1.Length, num2.Length) + 1];

            int i = num1.Length - 1, j = num2.Length - 1, resultIndex = result.Length - 1, carry = 0;

            while (i >= 0 && j >= 0)

            {

                int sum = (num1[i--] - '0') + (num2[j--] - '0') + carry;

                carry = sum / 10;

                sum = sum % 10;

                result[resultIndex--] = (char)(sum + '0');

            }

            if (i >= 0)

            {

                this.SumOneNumWithCarry(result, num1, i, resultIndex, carry);

            }

            else if (j >= 0)

            {

                this.SumOneNumWithCarry(result, num2, j, resultIndex, carry);

            }

            else if (carry > 0)

            {

                result[0] = (char)(carry + '0');

            }

            return result[0] != 0 ? new string(result) : new string(result, 1, result.Length - 1);

        }

        private void SumOneNumWithCarry(char[] result, string num, int index, int resultIndex, int carry)

        {

            int resultItr = resultIndex;

            int numItr = index;

            while (numItr >= 0)

            {

                result[resultItr--] = num[numItr--];

            }

            if (carry == 1)

            {

                while (index >= 0)

                {

                    if (num[index] == '9')

                    {

                        result[resultIndex--] = '0';

                        --index;

                    }

                    else

                    {

                        ++result[resultIndex];

                        return;

                    }

                }

                result[0] = '1';

            }

        }

Complexity: O(Max(length of num1, length of num2))    

[Google Question][LeetCode] Optimal Account Balancing

Problem: A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

Note:

1. A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.
2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.

Example:

Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.

Approach: This is complex problem to solve. Basically first we need to get all the debts (negative or positive) on every person. Once we get all the debts, we need to find every settlement combination and then we need to find the combination with minimum length among these combinations.

Getting debts on every person is easy, we can use hashing to get it but to get all the combinations and then get the minimum of those we need to use backtracking / DFS.

Implementation in C#:

    public int MinTransfers(int[][] transactions) 

    {

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

        foreach(int[] transaction in transactions)

        {

            int sender = transaction[0], receiever = transaction[1], amount = transaction[2];

            if (!debtsMap.ContainsKey(sender))

            {

                debtsMap[sender] = 0;

            }

            if (!debtsMap.ContainsKey(receiever))

            {

                debtsMap[receiever] = 0;

            }

            debtsMap[sender] -= amount;

            debtsMap[receiever] += amount;

        }

        List<int> debtsList = debtsMap.Values.Where(am => am != 0).ToList();

        return this.GetMinTransactionsToSettle(debtsList, 0);

    }

    

    private int GetMinTransactionsToSettle(List<int> debtsList, int currIndex)

    {

        // No point in processing with 0 debt   

        while (currIndex < debtsList.Count && debtsList[currIndex] == 0)

        {

            ++currIndex;

        }

        // Done here, we get one of the combination

        if (currIndex == debtsList.Count)

        {

            return 0;

        }

        int currAmount = debtsList[currIndex];

        int minTransactions = int.MaxValue;

        for (int i = currIndex + 1; i < debtsList.Count; ++i)

        {

            int nextAmount = debtsList[i];

            // An optimization: there is no point in process '+' and  '+' or '-' and '-'

            if (currAmount * nextAmount < 0)

            {

                debtsList[i] = currAmount + nextAmount;

                minTransactions = Math.Min(minTransactions, this.GetMinTransactionsToSettle(debtsList, currIndex + 1) + 1);

                debtsList[i] = nextAmount;

                // This is an optimization

                if (currAmount + nextAmount == 0)

                {

                    break;

                }

            }

        }

        return minTransactions;

    }

Complexity: O(n^2)

[Google Question] Merge K Sorted Lists

Problem: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example:

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

Approach: One simple approach would be to first look for the first nodes in all the lists, whichever has the minimum value, add that node to output and move this node to its next node. Repeat this till we have traversed all the nodes that means, all the nodes in the lists are null. Our algorithm will look like:

• MergeLists(lists)
• minNode = null;
• minIndex = -1
• For i = 0  to n - 1
• IF lists[i] != null
• IF minNode == null || minNode.Value > lists[i].Value
• minNode = lists[i];
• minIndex = i
• IF minNode != null
• lists[minIndex] = lists[minIndex].Next
• minNode.Next = MergeLists(lists)
• RETURN minNode

This will work and we can apply an optimization that if we found there in only one list is not null just return minNode in that case but its complexity is O(k * n) where k is the number of list and n is number of total nodes. Let's try to do better.

If you see to get the node with minimum value we are actually taking k steps. What if we use a Min-Heap /  Priority Queue of these k values. With the usage of min heap our algorithm will look like:

• For i = 0 to n-1
• IF lists[i] != null
• MinHeap.Add({lists[i].Value => lists[i]})
• head = null
• itr = head
• WHILE MinHeap not empty
• node = MinHeap.RemoveTop().Value
• IF head == null
• head = node
• itr = head
• ELSE
• itr.next = node
• itr = itr.next
• IF node.Next != null
• heap.Add({node.Next.Value => node.Next})
• itr.next = null
• RETURN head

I am using SortedDictionary in my implementation as C# has no default Heap. That's all!

Implementation in C#:

    public ListNode MergeKLists(ListNode[] lists) 

    {

        if (lists?.Length == 0)

        {

            return null;

        }

        SortedDictionary<int, List<ListNode>> heap = new SortedDictionary<int, List<ListNode>>();

        foreach (ListNode list in lists)

        {

            if (list != null)

            {

                if (!heap.ContainsKey(list.val))

                {

                    heap.Add(list.val, new List<ListNode>());

                }

                heap[list.val].Add(list);

            }

        }

        ListNode head = null;

        ListNode itr = null;

        while (heap.Count > 0)

        {

            List<ListNode> nodes = heap.First().Value;

            ListNode node = nodes.Last();

            nodes.RemoveAt(nodes.Count - 1);

            if (nodes.Count == 0)

            {

                heap.Remove(node.val);

            }

            if (head == null)

            {

                head = node;

                itr = head;

            }

            else

            {

                itr.next = node;

                itr = itr.next;

            }

            if (node.next != null)

            {

                if (!heap.ContainsKey(node.next.val))

                {

                    heap.Add(node.next.val, new List<ListNode>());

                }

                heap[node.next.val].Add(node.next);

            }

        }

        if (itr != null)

        {

            itr.next = null;

        }

        return head;

    }

Complexity: O(nlogk)