[LeetCode] Maximum Sum Circular Subarray

Problem: Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

Approach: This problem is an extension of Kadanes max sum problem. If you see if the max sum exist in the middle than Kadanes approach is sufficient but if the max sum exist in circular subarray then we need to come up with a different approach.

Let's say the other special sum in case of circular array is called circular sum. How does it look like:

So if you see above array, you will understand

circular sum = sum of prefix of array + sum of suffix of array.

Now we just need to get max of all such calculated circular sums. To do it efficiently, we can prepopulate a rightmax array where rightmax[i] is the max sum of subarray nums[i...n-1]. With this we can easily calculate the max sum which is:

max_sum = MAX(kadanes_max_sum, max_circular_sum)

This is time efficient but if you see the above approach is iterating the input array twice and is using extra space in the form of rightmax array. Let's try to do better.

If you see max_circular_sum is equal to total sum of array - kadanes_min_sum. Right! We can calculate it using kadanes min sum with same approach by which we get kadanes max sum. It's just that we need to use Min instead of Max in the algo.

The only exception will be when all the numbers are negative which is easy to handle as in that case we just need to return kadanes_max_sum.

That's all!

Implementation in C#:

Approach 1: Using extra space:

    public int MaxSubarraySumCircular(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        if (length == 1)

        {

            return nums[0];

        }

        int[] rightMax = new int[length];

        rightMax[length - 1] = nums[length - 1];

        int suffixSum = nums[length - 1];

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

        {

            suffixSum += nums[i];

            rightMax[i] = Math.Max(suffixSum, rightMax[i + 1]);

        }

        int maxSum = int.MinValue;

        int circularSum = int.MinValue;

        int currSum = 0;

        int prefixSum = 0;

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

        {

            currSum = Math.Max(currSum, 0) + nums[i];

            maxSum = Math.Max(maxSum, currSum);

            prefixSum += nums[i];

            if (i < length - 1)

            {

                circularSum = Math.Max(circularSum, prefixSum + rightMax[i + 1]);

            }

        }

        return Math.Max(maxSum, circularSum);

    }

Approach 2: No extra space:

       public int MaxSubarraySumCircular(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        if (length == 1)

        {

            return nums[0];

        }

        int maxSum = int.MinValue;

        int currMaxSum = 0;

        int currMinSum = 0;

        int minSum = int.MaxValue;

        int totalSum = 0;

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

        {

            currMaxSum = Math.Max(currMaxSum, 0) + nums[i];

            maxSum = Math.Max(maxSum, currMaxSum);

            currMinSum = Math.Min(currMinSum, 0) + nums[i];

            minSum = Math.Min(currMinSum, minSum);

            totalSum += nums[i];

        }

        return totalSum == minSum ? maxSum : Math.Max(maxSum, totalSum - minSum);

    }

Complexity: O(n)

[Google][CareerCup] Json parser library

Problem: JSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day, suddenly, all of the JSON parser libraries went missing. You have been called upon to save us all from impending doom.

Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order. Please note that to simplify the things key is a string and value is either a string or a json object. No other data type is allowed.

You need to write following methods:

1. Constructor: Make an object of the class.
2. Serialize: Returns the json string.
3. Deserialize: Save the json string in a data structure.

Example:

Input: ["JsonParser", "Deserialize("{a:{h:hat},b:{c:{f:fish,g:goat},d:doll},e:elephant,i:{j:jar, k:kite,l:lion}}")", Serialize()]
Output: [None, None, "{a:{h:hat},b:{c:{f:fish,g:goat},d:doll},e:elephant,i:{j:jar, k:kite,l:lion}}"]

Approach: This can be done using many DS like trees, dictionary/map but I am using Linked List here with child pointer. As for me it looks like a list, where if value is another list of key value pair then we can say it is child otherwise it's simple data stored in the node.

Each comma ',' says this is next node. With this thought just look at the implementation to understand the solution in more details.

Please note that I haven't tested it throroughly so there might be some corner cases where the below program will fail but the approach will remain same.

Implementation in C#:

public class ListNode

{

    public string Key {get; set;}

    public string Value { get; set; }

    public ListNode Next {get; set;}

    public ListNode Child {get; set;}

    public ListNode(string key)

    {

        this.Key = key;

    }

}

public class JsonParser

{

    public JsonParser()

    {

        this.head = null;

    }

    

    public void Deserialize(string str)

    {

        this.Clear();

        int currIndex = 1;

        this.head = this.DeserializeToList(str, ref currIndex);

    }

    

    private ListNode DeserializeToList(string str, ref int currIndex)

    {

        // Nothing to consume

        if (currIndex >= str.Length)

        {

            return null;

        }

        int keyIndex = str.IndexOf(":", currIndex);

        // No key exist means wrong input

        if (keyIndex == -1)

        {

            return null;

        }

        // Get key

        string key = str.Substring(currIndex, keyIndex - currIndex);

        // Create the node

        ListNode node = new ListNode(key);

        // First case when value is string

        if (str[keyIndex + 1] != '{')

        {

            int bracketIndex = str.IndexOf("}", keyIndex + 1);

            int commaIndex = str.IndexOf(",", keyIndex + 1);

            int valIndex = Math.Min(bracketIndex, commaIndex);

            if (valIndex == -1)

            {

                valIndex = bracketIndex;

            }

            string val = str.Substring(keyIndex + 1, valIndex - (keyIndex + 1));

            node.Value = val;

            currIndex = valIndex + 1;

        }

        // Second case when value is JsonObject, Need to initialize child

        else

        {

            currIndex = keyIndex + 2;

            node.Child = this.DeserializeToList(str, ref currIndex);

        }

        // In case of closing bracket there is no next node.

        if (str[currIndex - 1] == '}')

        {

            node.Next = null;

            ++currIndex;

        }

        // In case of comma there is a next node.

        else

        {

            node.Next = this.DeserializeToList(str, ref currIndex);

        }

        // Current node is properly initialized now

        return node;

    }

    

    public string Serialize()

    {

        return this.SerializeToStr(this.head);

    }

    

    private string SerializeToStr(ListNode node, bool isNext = false)

    {

        if (node == null)

        {

            return "";

        }

        // In case of next we don't need to wrap around brackets

        string str = isNext ? "" : "{";

        str += node.Key + ":";

        // If value is null means child is there so serialize it first before moving

        // to next

        if (node.Value == null)

        {

            str += this.SerializeToStr(node.Child);

        }

        else

        {

            str += node.Value;

        }

        // Go to next node

        if (node.Next != null)

        {

            str += ("," + this.SerializeToStr(node.Next, true));

        }

        str += isNext ? "" : "}";

        return str;

    }

    

    public void Clear()

    {

        this.head = null;

    }

    

    private ListNode head;

}

Complexity: O(n) for both serialize and deserialize

[Flipkart][GFG] N meetings in one room

Problem: There is one meeting room in a firm. There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is finish time of meeting i.

What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a particular time?

Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.

Example:

Input:
N = 6
start[] = {1,3,0,5,8,5}
end[] =  {2,4,6,7,9,9}
Output: 
4
Explanation:
Maximum four meetings can be held with given start and end timings.
The meetings are - (1, 2),(3, 4), (5,7) and (8,9)

Input:
N = 3
start[] = {10, 12, 20}
end[] = {20, 25, 30}
Output: 
1
Explanation:
Only one meetings can be held
with given start and end timings.

Approach: We can sort these intervals based on start time and then the problem become super easy. You can look at the implementation to understand the rest of the approach.

Implementation in C#:

    public int maxMeetings(int[] start, int[] end, int n)

    {

        if (n == 0)

        {

            return 0;

        }

        Meeting[] meetings = new Meeting[n];

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

        {

            meetings[i] = new Meeting(start[i], end[i]);

        }

        Array.Sort(meetings, (m1, m2) => {

            return m1.Start.CompareTo(m2.Start);

        });

        int count = 1;

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

        {

            if (meetings[i].Start > meetings[i - 1].End)

            {

                ++count;

            }

            else

            {

                meetings[i] = meetings[i].End < meetings[i - 1].End ? 

                              meetings[i] : 

                              meetings[i - 1];

            }

        }

        return count;

    }

Complexity: O(nlogn)

[Amazon][GFG] Flattening a Linked List

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

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

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

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

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

Example:

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

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

(Note: | represents the bottom pointer.)

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

That's all!

Implementation in Java:

    Node flatten(Node root)

    {

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

    {

        return root;

    }

    root.next = flatten(root.next);

    return merge(root, root.next);

    }

    

    private Node merge(Node node1, Node node2)

    {

        if (node1 == null)

        {

            return node2;

        }

        if (node2 == null)

        {

            return node1;

        }

        Node result = null;

        if (node1.data <= node2.data)

        {

            result = node1;

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

        }

        else

        {

            result = node2;

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

        }

        result.next = null;

        return result;

    }

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

[LeetCode] Merge Two Sorted Lists

Problem: Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: list1 = [], list2 = []
Output: []

Input: list1 = [], list2 = [0]
Output: [0]

Approach: We have already done it recursively before. Just adding the iterative approach here. You can just understand it by looking at the implementation.

Implementation in C#:

    public ListNode MergeTwoLists(ListNode list1, ListNode list2)

    {

        var itr1 = list1;

        var itr2 = list2;

        var head = new ListNode();

        var itr = head;

        while (itr1 != null && itr2 != null)

        {

            if (itr1.val <= itr2.val)

            {

                itr.next = itr1;

                itr1 = itr1.next;

            }

            else

            {

                itr.next = itr2;

                itr2 = itr2.next;

            }

            itr = itr.next;

        }

        if (itr1 != null)

        {

            itr.next = itr1;

        }

        else if (itr2 != null)

        {

            itr.next = itr2;

        }

        return head.next;

    }

Complexity: O(Max(m, n))

Middle of the Linked List

Problem: Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Approach: We can do it in two passes where in first iteration we can get the number of nodes and in the second iteration we will get the size/2th node. 

Let's try to reduce the number of iterations. What we can do, we can use two pointers; one is slow which goes 1 step at one time and one is fast which goes 2 steps at a time:

• slow = slow.next
• fast = fast.next.next

Obviously when fast is null or it's next is null, slow will be pointing at the middle node. That's all!

Implementation in C#:

    public ListNode MiddleNode(ListNode head)

    {

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

        {

            return head;

        }

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null)

        {

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

Complexity: O(n)

[InterviewBit] Subarray with given XOR

Problem: Given an array of integers A and an integer B.

Find the total number of subarrays having bitwise XOR of all elements equals to B.

Example:

Input 1:

 A = [4, 2, 2, 6, 4]
 B = 6

Input 2:

 A = [5, 6, 7, 8, 9]
 B = 5

Example Output

Output 1:

 4

Output 2:

 2

Example Explanation

Explanation 1:

 The subarrays having XOR of their elements as 6 are:
 [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6]

Explanation 2:

 The subarrays having XOR of their elements as 5 are [5] and [5, 6, 7, 8, 9]

Approach: We will use hash map to solve this problem. Approach is simple, we will keep doing the xor of every element and store each xor and its frequency in the hashmap. Now at every step we just need to check if curr_xor ^ B exist in the map or not, if yes we will just add count of curr_xor ^ B to the result. That's all!

Implementation in C#:

    public int solve(List<int> A, int B) 

    {

        int length = A?.Count ?? 0;

        if (length == 0)

        {

            return 0;

        }

        var xorMap = new Dictionary<int, int>();

        int xor = 0;

        int count = 0;

        xorMap[xor] = 1;

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

        {

            xor ^= A[i];

            if (xorMap.ContainsKey(B ^ xor))

            {

                count += xorMap[B ^ xor];

            }

            if (!xorMap.ContainsKey(xor))

            {

                xorMap[xor] = 0;

            }

            ++xorMap[xor];

        }

        return count;

    }

Complexity: O(n)