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

[LeetCode] Add Binary

Problem: Given two binary strings a and b, return their sum as a binary string.

Example:

Input: a = "11", b = "1"
Output: "100"

Input: a = "1010", b = "1011"
Output: "10101"

Approach: Nothing much to discuss here. Its an easy problem to solve. Just look at the implementation to understand the approach.

Implementation in C#:

    public string AddBinary(string a, string b)

    {

        int lenA = a.Length;

        int lenB = b.Length;

        int maxLen = Math.Max(lenA, lenB);

        char[] res = new char[maxLen];

        int i = lenA - 1, j = lenB - 1;

        int k = maxLen - 1;

        int carry = 0;  

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

        {

            char add = '0';

            if (a[i] == '1' && b[j] == '1')

            {

                add ='0';

                if (carry == 1)

                {

                    add = '1';

                }

                carry = 1;

            }

            else if (a[i] == '0' && b[j] == '0')

            {

                add = '0';

                if (carry == 1)

                {

                    add = '1';

                }

                carry = 0;

            }

            else

            {

                add = '1';  

                if (carry == 1)

                {

                    add = '0';

                    carry = 1;

                }

                else

                {

                    carry = 0;

                }

            }

            res[k--] = add;

            --i;

            --j;

        }

        if (i >= 0)

        {

            this.HandleSingleNum(a, i, res, k, ref carry);

        }

        if (j >= 0)

        {

            this.HandleSingleNum(b, j, res, k, ref carry);

        }

        string result = carry == 1 ?

                        "1" + new string(res) :

                        new string(res);

        return result;

    }

    private void HandleSingleNum(

        string num,

        int numIndex,

        char[] result,

        int resIndex,

        ref int carry)

    {

        while(numIndex >= 0)

        {

            if (num[numIndex] == '0')

            {

                if (carry == 1)

                {

                    result[resIndex--] = '1';

                }

                else

                {

                    result[resIndex--] = '0';

                }

                carry = 0;

            }

            else

            {

                if (carry == 1)

                {

                    result[resIndex--] = '0';

                    carry = 1;

                }

                else

                {

                    result[resIndex--] = '1';

                    carry = 0;

                }

            }

            --numIndex;

        }

    }

Complexity: O(n) where n is max of length of a and length of b.

[Microsoft][LeetCode] Permutations II

Problem: Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example:

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

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

Approach: This is same question as print permutation of a string but here the input contains duplicates. We are just going to use the same approach of backtracking which we used in the above question but while adding the current permutation to result, we will just check for duplicate. We can use HashSet for it.

Implementation in C#:

    public IList<IList<int>> PermuteUnique(int[] nums)

    {

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

        Array.Sort(nums);

        this.PermuteUnique(nums, 0, result, new HashSet<string>());

        return result;

    }

    private void PermuteUnique(int[] nums,

                            int index,

                            IList<IList<int>> result,

                            HashSet<string> set)

    {

        if (index == nums.Length)

        {

            string key = this.GetKey(nums);

            if (set.Add(key))

            {

                result.Add(nums.ToList());

            }

            return;

        }

        for (int j = index; j < nums.Length; ++j)

        {

            this.Swap(nums, index, j);

            this.PermuteUnique(nums, index + 1, result, set);

            this.Swap(nums, index, j);

        }

    }

    private string GetKey(int[] nums)

    {

        return string.Join("-", nums);

    }

    private void Swap(int[] nums, int i, int j)

    {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

Complexity: O(n * !n)

[LeetCode] Find the Town Judge

Problem: In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

• The town judge trusts nobody.
• Everybody (except for the town judge) trusts the town judge.
• There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Example:

Input: n = 2, trust = [[1,2]]
Output: 2

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Approach: This is a straight forward problem. We can use Hash map to solve this problem. Simply, have a look at the implementation to understand the solution.

Implementation in C#:

    public int FindJudge(int n, int[][] trust)

    {

        if (n == 1 && trust.Length == 0)

        {

            return 1;

        }

        Dictionary<int, List<int>> trustGraph = new Dictionary<int, List<int>>();

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

        foreach(int[] t in trust)

        {

            if (!trustGraph.ContainsKey(t[1]))

            {

                trustGraph[t[1]] = new List<int>();

            }

            trustGraph[t[1]].Add(t[0]);

            personsWhoTrust.Add(t[0]);

        }

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

        {

            if (trustGraph.ContainsKey(i))

            {

                if (trustGraph[i].Count == n - 1 && !personsWhoTrust.Contains(i))

                {

                    return i;

                }

            }

        }

        return -1;

    }

Complexity: O(n)

[LeetCode] Longest Path With Different Adjacent Characters

Problem: You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Example:

Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 

Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

Approach: This is again a PostOrder Traversal kind of problem as here too if the subtrees are processed before the root of the subtree then we can easily do the calculation at the root.

At any node, the longest Path will be - 

Max (Largest Path Chain among node's children where character at node is different than child node's character + Second Largest Path Chain among node's children where character at node is different than child node's character + 1(node itself), Largest Path among where node's character is same as child's character)

Why we are taking just one chain in case of inclusion of node because we just can't have branches when we are including the current node. See the below example:

                  a

       /

      b

             / \

           c    d

Here if we include 'a' the path could be a->b->c or a->b->d.

We can have longestPath as global / reference variable to record the longesPath and we can return the longest chain + 1(including current node) from the PostOrderTraversal method as only the longest chain is useful for the parent node.

Implementation in C#:

    public int LongestPath(int[] parent, string s)

    {

        var tree = this.MakeTree(parent);

        int longestPath = 1;

        this.LongestPathPostOrder(0, tree, s, ref longestPath);

        return longestPath;

    }

    private int LongestPathPostOrder(

                                int node,

                                Dictionary<int, List<int>> tree,

                                string s,

                                ref int longestPath)

    {

        int longestPathLength = 0, secondLongestLength = 0;

        if (!tree.ContainsKey(node))

        {

            return 1;

        }

        foreach (int child in tree[node])

        {

            int pathLength = this.LongestPathPostOrder(

                                                    child,

                                                    tree,

                                                    s,

                                                    ref longestPath);

            if (s[child] == s[node])

            {

                continue;

            }

            else

            {

                if (pathLength > longestPathLength)

                {

                    secondLongestLength = longestPathLength;

                    longestPathLength = pathLength;    

                }

                else if (pathLength > secondLongestLength)

                {

                    secondLongestLength = pathLength;

                }

            }

        }

       

        longestPath = Math.Max(

                        longestPath,

                        1 + longestPathLength + secondLongestLength);

        return longestPathLength + 1;

    }

    private Dictionary<int, List<int>> MakeTree(int[] parent)

    {

        var tree = new Dictionary<int, List<int>>();

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

        {

            if (!tree.ContainsKey(parent[i]))

            {

                tree[parent[i]] = new List<int>();

            }

            tree[parent[i]].Add(i);

        }

        return tree;

    }

Complexity: O(n)