[LeetCode] Maximum Average Subarray I

Problem: You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

Approach: This is clearly a sliding window problem. We can take sum of first k elements say 'sum' and then we slide the window by one i.e. remove first element of window from sum and add new element of the slided window to sum and record the max sum so far so every step looks like:

• sum = sum - nums[start] + nums[i] 
• start++
• max_sum = MAX(sum, max_sum)

Implementation in C#:

        public double FindMaxAverage(int[] nums, int k)

    {

        int length = nums?.Length ?? 0;

        if (length < k)

        {

            return 0;

        }

        long sum = 0;

        int i = 0, start = 0;

        for (; i < k; ++i)

        {

            sum += nums[i];

        }

        long maxSum = sum;

        for (i = k; i < length; ++i)

        {

            sum = sum - nums[start++] + nums[i];

            maxSum = sum > maxSum ? sum : maxSum;

        }

        return (double)maxSum / k;

    }

Complexity: O(n)

[LeetCode] Kids With the Greatest Number of Candies

Problem: There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

Example:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false] 
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Approach: A simple problem to solve. Get the maximum of the given candies first. Once we get it, we just need to compare candies[i] + extraCandies with max of candies. If it is equal to or more than max of candies then add true to result otherwise add false.

Implementation in C#:

    public IList<bool> KidsWithCandies(int[] candies, int extraCandies)

    {

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

        int maxCandy = this.findMaxCandy(candies);

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

        {

            result.Add(candies[i] + extraCandies >= maxCandy);

        }

        return result;

    }

    private int findMaxCandy(int[] candies)

    {

        int maxCandy = candies[0];

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

        {

            if (maxCandy < candies[i])

            {

                maxCandy = candies[i];

            }

        }

        return maxCandy;

    }

Complexity: O(n)

[LeetCode] Greatest Common Divisor of Strings

Problem: For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Approach: A simple approach would be to check for every prefix of the smaller string and check if the prefix is such that 

prefix + prefix + prefix + ... + prefix = str1

prefix + prefix + prefix + ... + prefix = str2

We can do some optimization like choosing a prefix such that the length of prefix is divisor of lengths of both str1 and str2 and may be more but whatever optimization we will do the complexity is going to be on higher side i.e. O(m^2 + n^2).

Let's try to see problem from different view, sometimes looking at the examples really help. If you see closely, you can find GCD of str1 and str2 can exist only if 

str1 + str2 = str2 + str1

Why? Let's say GCD of both strings is gcd then:

str1 = gcd + gcd + gcd + ... m times

str2 = gcd + gcd + gcd + ... n times

str1 + str2 = gcd + gcd + gcd + ... (m + n) times

str2 + str1 = gcd + gcd + gcd + ... (n + m) times

so you see str1 + str2 is equal to str2 + str1.

Now that we know when GCD exist, what is GCD of both strings? Just look at the example closely and you will quickly find that GCD is the prefix of length of GCD(Length(str1), Length(str2).

That's all!

Implementation in C#:

Brute-force:

    public string GcdOfStrings(string str1, string str2)

    {

        string gcd = string.Empty;

        int str1Len = str1.Length;

        int str2Len = str2.Length;

        int minStrLen = Math.Min(str1Len, str2Len);

        int currLen = 1;

        if (!string.IsNullOrEmpty(str1) && !string.IsNullOrEmpty(str2))

        {

            while (currLen <= minStrLen)

            {

                if (str1Len % currLen == 0 && str2Len % currLen == 0)

                {

                    string prefix = str1.Substring(0, currLen);

                    if (str2.StartsWith(prefix))

                    {

                        if (this.isStrRepetitionOfPrefix(str1, prefix)

                            && this.isStrRepetitionOfPrefix(str2, prefix))

                        {

                            gcd = prefix;

                        }

                    }

                }

                ++currLen;

            }

        }

        return gcd;

    }

    private bool isStrRepetitionOfPrefix(string str, string prefix)

    {

        int i = prefix.Length;

        while(i < str.Length)

        {

            if (str.Substring(i, prefix.Length) != prefix)

            {

                return false;

            }

            i += prefix.Length;

        }

        return true;

    }

Optimized:

    public string GcdOfStrings(string str1, string str2)

    {

        if (str1 + str2 != str2 + str1)

        {

            return string.Empty;

        }

        int maxLength = str1.Length;

        int minLength = str2.Length;

        if (maxLength < minLength)

        {

            minLength = maxLength;

            maxLength = str2.Length;

        }

        int gcdLength = this.getGCD(maxLength, minLength);

        return str1.Substring(0, gcdLength);

    }

    private int getGCD(int a, int b)

    {

        while (b != 0)

        {

            int temp = b;

            b = a % b;

            a = temp;

        }

        return a;

    }

Complexity: Solution 1: O(m^2 + n^2)

                      Solution 2: O(m + n)

[LeetCode] Merge Strings Alternately

Problem: You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d

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

    

Implementation in C#:

    public string MergeAlternately(string word1, string word2)

    {

        // Safety checks

        if (string.IsNullOrEmpty(word1) && string.IsNullOrEmpty(word2))

        {

            return word1;

        }

        if (string.IsNullOrEmpty(word1))

        {

            return word2;

        }

        if (string.IsNullOrEmpty(word2))

        {

            return word1;

        }

        int i = 0, j = 0;

        StringBuilder sb = new StringBuilder();

        while (i < word1.Length && j < word2.Length)

        {

            sb.Append(word1[i++]);

            sb.Append(word2[j++]);

        }

        if (i < word1.Length)

        {

            this.AppendAllChars(sb, i, word1);

        }

        if (j < word2.Length)

        {

            this.AppendAllChars(sb, j, word2);

        }

        return sb.ToString();

    }

    private void AppendAllChars(StringBuilder sb, int index, string word)

    {

        while (index < word.Length)

        {

            sb.Append(word[index++]);

        }

    }

Complexity: O(n)

[LeetCode] Pancake Sorting

Problem: Given an array of integers arr, sort the array by performing a series of pancake flips.

In one pancake flip we do the following steps:

• Choose an integer k where 1 <= k <= arr.length.
• Reverse the sub-array arr[0...k-1] (0-indexed).

For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.

Return an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.

Example:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

Input: arr = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= arr.length
• All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

Approach: We can try something like bubble sort approach where we put the maximum element at the end of the array. But how we do it? We are not allowed to swap, Right? We can only apply above Flip operation which basically reverse the sub array  [0...k - 1].

Let's see how we can use Flip. We find the index of maximum number say 'i'. Once we got it, we flip [0...i]. Now our maximum number is at the head. Now simply we can flip the whole array to take maximum number to last index.

Now we keep doing it for rest of the elements in descending order and apply these Flips. Please note that not every time we Flip the whole array as we know the maximum number is already in place so we decrease the last index by 1 every time we place the element to its right position.

That's all!

Implementation in C#:

    public IList<int> PancakeSort(int[] arr)

    {

        if (arr == null || arr.Length <= 1)

        {

            return new List<int>();

        }

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

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

        {

            int index = this.FindIndex(arr, i);

            if (index == i - 1)

            {

                continue;

            }

            if (index != 0)

            {

                result.Add(index + 1);

                this.Flip(arr, index);

            }

            result.Add(i);

            this.Flip(arr, i - 1);

        }

        return result;

    }

    private void Flip(int[] arr, int index)

    {

        int start = 0, end = index;

        while (start < end)

        {

            int temp = arr[start];

            arr[start] = arr[end];

            arr[end] = temp;

            ++start;

            --end;

        }

    }

    private int FindIndex(int[] arr, int element)

    {

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

        {

            if (arr[i] ==  element)

            {

                return i;

            }

        }

        return -1;

    }

Complexity: O(n^2)

[LeetCode] Design Underground System

Problem: An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

• void checkIn(int id, string stationName, int t)
• A customer with a card ID equal to id, checks in at the station stationName at time t.
• A customer can only be checked into one place at a time.
• void checkOut(int id, string stationName, int t)
• A customer with a card ID equal to id, checks out from the station stationName at time t.
• double getAverageTime(string startStation, string endStation)
• Returns the average time it takes to travel from startStation to endStation.
• The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
• The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
• There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.

Example:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

Constraints:

1. 1 <= id, t <= 106
2. 1 <= stationName.length, startStation.length, endStation.length <= 10
3. All strings consist of uppercase and lowercase English letters and digits.
4. There will be at most 2 * 104 calls in total to checkIn, checkOut, and getAverageTime.
5. Answers within 10-5 of the actual value will be accepted.

Approach: This is fairly straight forward problem to solve. We can use two hash tables; one to keep track of customer travel and another one is to keep track of route travel history. 

Have a look at the implementation to understand the approach.

Implementation in C#:

public class CustomerTravelDetail {

    public string CheckinStation {get; set;}

    public string CheckoutStation {get; set;}

    public int CheckinTime {get; set;}

    public int CheckoutTime {get; set;}

}

public class StationsTravelHistory {

    public double Sum {get; set;}

    public int Count {get; set;}

}

public class UndergroundSystem {

    private Dictionary<string, StationsTravelHistory> travelDictionary;

    private Dictionary<int, CustomerTravelDetail> custDictionary;

    public UndergroundSystem() {

        this.travelDictionary = new Dictionary<string, StationsTravelHistory>();

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

    }

   

    public void CheckIn(int id, string stationName, int t) {

        this.custDictionary[id] = new CustomerTravelDetail {

            CheckinStation = stationName,

            CheckinTime = t };

    }

   

    public void CheckOut(int id, string stationName, int t) {

        if (this.custDictionary.ContainsKey(id)) {

            this.custDictionary[id].CheckoutStation = stationName;

            this.custDictionary[id].CheckoutTime = t;

            this.UpdateStationTravelHistory(this.custDictionary[id]);

        }

    }

   

    public double GetAverageTime(string startStation, string endStation) {

        string route = this.GetTravelHistoryKey(startStation, endStation);

        return this.travelDictionary[route].Sum / this.travelDictionary[route].Count;

    }

    private void UpdateStationTravelHistory(CustomerTravelDetail detail) {

        string route = this.GetTravelHistoryKey(detail.CheckinStation, detail.CheckoutStation);

        if (!this.travelDictionary.ContainsKey(route))

        {

            this.travelDictionary[route] = new StationsTravelHistory();

        }

        this.travelDictionary[route].Sum += (detail.CheckoutTime - detail.CheckinTime);

        ++this.travelDictionary[route].Count;

    }

    private string GetTravelHistoryKey(string start, string end) {

        return start + "-" + end;

    }

}

Complexity: O(1) for every method.