[Amazon][LeetCode] Rotting Oranges

Problem: You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Approach: This is another BFS problem. We treat this matrix as graph where a cell is connected to another cell if they are neighbour of each other (except diagonal neighbours). We start our BFS with all the initial rotten oranges (grid[x][y] == 2) cells enqueued in a queue.

We keep incrementing the number of minutes at every iteration and make all the fresh oranges neighbours 2 (rotten). Once the BFS ends, we just need to check if there is a cell with fresh orange, if yes then we will return -1 otherwise we return the number of minutes.

Implementation in C#:

    public int OrangesRotting(int[][] grid) {

        int rows = grid?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = grid[0].Length;

        Queue<int[]> queue = new Queue<int[]>();

        int numOfFreshCells = this.GetFreshCellsAndAddRottenCellsToQueue(grid,

                                                                         queue);

        if (numOfFreshCells == 0)

        {

            return 0;

        }

        int minutes = 0;

        while (queue.Count > 0)

        {

            int size = queue.Count;

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

            {

                var cell = queue.Dequeue();

                this.AddNeighbourFreshCellsToQueue(cell,

                                                   grid,

                                                   queue,

                                                   ref numOfFreshCells);

            }

            if (queue.Count > 0)

            {

                ++minutes;

            }

        }

        return numOfFreshCells != 0 ? - 1 : minutes;

    }

    private bool IsFreshCellRemaining(int[][] grid)

    {

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

        {

            for (int j = 0; j < grid[0].Length; ++j)

            {

                if (grid[i][j] == 1)

                {

                    return true;

                }

            }

        }

        return false;

    }

    private void AddNeighbourFreshCellsToQueue(int[] cell,

                                               int[][] grid,

                                               Queue<int[]> queue,

                                               ref int numOfFreshCells)

    {

        // Left cell

        if (this.IsValidAndFreshCell(cell[0], cell[1] - 1, grid))

        {

            grid[cell[0]][cell[1] - 1] = 2;

            queue.Enqueue(new int[] {cell[0], cell[1] - 1});

            --numOfFreshCells;

        }

        // Right cell

        if (this.IsValidAndFreshCell(cell[0], cell[1] + 1, grid))

        {

            grid[cell[0]][cell[1] + 1] = 2;

            queue.Enqueue(new int[] {cell[0], cell[1] + 1});

            --numOfFreshCells;

        }

        // Up cell

        if (this.IsValidAndFreshCell(cell[0] - 1, cell[1], grid))

        {

            grid[cell[0] - 1][cell[1]] = 2;

            queue.Enqueue(new int[] {cell[0] - 1, cell[1]});

            --numOfFreshCells;

        }

        // Down cell

        if (this.IsValidAndFreshCell(cell[0] + 1, cell[1], grid))

        {

            grid[cell[0] + 1][cell[1]] = 2;

            queue.Enqueue(new int[] {cell[0] + 1, cell[1]});

            --numOfFreshCells;

        }

    }

    private bool IsValidAndFreshCell(int row, int col, int[][] grid)

    {

        return row >= 0 &&

               row < grid.Length &&

               col >= 0 &&

               col < grid[0].Length &&

               grid[row][col] == 1;

    }

    private int GetFreshCellsAndAddRottenCellsToQueue(int[][] grid,

                                                      Queue<int[]> queue)

    {

        int numOfFreshCells = 0;

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

        {

            for (int j = 0; j < grid[0].Length; ++j)

            {

                if (grid[i][j] == 1)

                {

                    ++numOfFreshCells;

                }

                else if (grid[i][j] == 2)

                {

                    queue.Enqueue(new int[] {i, j});

                }

            }

        }

        return numOfFreshCells;

    }

Complexity: O(m x n) where m is number of rows and n is number of columns.

[LeetCode] 3 Sum

Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Approach: We can use sorting here. Once we sort the array, We can use approach of two pointers low and high. For every nums[i], we check if there are two elements in nums[i + 1.... n] whose sum is -nums[i].

To avoid duplicate we can move i till nums[i] == nums[i + 1] and we can move high till nums[high] == nums[high - 1]. That's all!

Implementation in C#:

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

    {

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

        Array.Sort(nums);

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

        {

            if ( i > 0 &&  nums[i] == nums[i - 1])

            {

                continue;

            }

            int low = i + 1, high = nums.Length - 1, sumToCheck = -nums[i];

            while (low < high)

            {

                if (high < nums.Length - 1 && nums[high] == nums[high + 1])

                {

                    --high;

                    continue;

                }

                if (nums[low] + nums[high] == sumToCheck)

                {

                    result.Add(new List<int> { nums[i], nums[low], nums[high] });

                    ++low;

                    --high;

                }

                else if (nums[low] + nums[high] < sumToCheck)

                {

                    ++low;

                }

                else

                {

                    --high;

                }

            }

        }

        return result;

    }

Complexity: O(n^2)

[LeetCode] Sort Characters By Frequency

Problem: Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example: 

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Approach: We can use custom comparer while applying sorting on this string.

Implementation in C#:

    public string FrequencySort(string s) 

    {

        char[] arr = s.ToCharArray();

        Dictionary<char, int> count = new Dictionary<char, int>();

        foreach (char ch in arr)

        {

            if (!count.ContainsKey(ch))

            {

                count[ch] = 0;

            }

            ++count[ch];

        }

        Array.Sort(arr, (a, b) => {

            if (count[b] == count[a])

            {

                return b.CompareTo(a);

            }      

            return count[b].CompareTo(count[a]); 

        });

        return new string(arr);

    }

Complexity: O(nlogn)

[LeetCode] Design HashSet

Problem: Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

• void add(key) Inserts the value key into the HashSet.
• bool contains(key) Returns whether the value key exists in the HashSet or not.
• void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example:

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

Approach: We will approach this problem same as we approached our previous problem of designing HashMap. We just will take array of LinkedList of int instead of LinkedList of Key, Value pair as here we just need to store an integer Rest of the things remains same.

Implementation in C#:

public class MyHashSet 

{

    public MyHashSet() 

    {

        this.size = 2069;

        this.buckets = new LinkedList<int>[2069];

    }

    

    public void Add(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            this.buckets[index] = new LinkedList<int>();

        }

        LinkedListNode<int> node = this.buckets[index].First;

        while(node != null)

        {

            if (node.Value == key)

            {

                return;

            }

            node = node.Next;

        }    

        this.buckets[index].AddFirst(key);

    }

    

    public void Remove(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            return;

        }

        LinkedListNode<int> node = this.buckets[index].First;

        while(node != null)

        {

            if (node.Value == key)

            {

                this.buckets[index].Remove(node);

                return;

            }

            node = node.Next;

        }

    }

    

    public bool Contains(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            return false;

        }        

        LinkedListNode<int> node = this.buckets[index].First;

        while(node != null)

        {

            if (node.Value == key)

            {

                return true;

            }

            node = node.Next;

        }

        return false;

    }

    

    LinkedList<int>[] buckets;

    int size;

}

Complexity: O(1) for all the operations.

[LeetCode] Linked List Random Node

Problem: Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the integer array nums.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.

Example:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

Approach: We can take a private member of type List and just put all the values of the input Linked List into it. Now whenever we will get a call of getRandom(), we can generate a random index and return the value at that index in that list. That's all!

Note that here we are assuming the list size is not getting changed very frequently. If it is the case then we just can't rely on this approach and we need to use Reservoir Sampling.

Implementation in C#:

public class Solution 

{

    public Solution(ListNode head) 

    {

        this.listValues = new List<int>();

        ListNode itr = head;

        while (itr != null)

        {

            this.listValues.Add(itr.val);

            itr = itr.next;

        }

    }

    

    public int GetRandom() {

        int index = new Random().Next() % this.listValues.Count;

        return this.listValues[index];

    }

    

    private List<int> listValues;

}

Complexity: O(n) for constructor and O(1) for getRandom()

[LeetCode] Swapping Nodes in a Linked List

Problem: You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example:

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

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

Input: head = [1], k = 1
Output: [1]

Input: head = [1,2], k = 1
Output: [2,1]

Input: head = [1,2,3], k = 2
Output: [1,2,3]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

Approach: It's a straight forward problem to solve. You can understand the approach by just looking at the implementation.

Implementation in C#:

    public ListNode SwapNodes(ListNode head, int k) 

    {

        if (head == null)

        {

            return head;

        }

        ListNode node = head;

        // Get the kth node from the start

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

        {

            node = node.next;

        }        

        ListNode swapNode1 = node;

        ListNode swapNode2 = head;

        // Get the kth node from the end

        while (node.next != null)

        {

            swapNode2 = swapNode2.next;

            node = node.next;

        }

        int temp = swapNode1.val;

        swapNode1.val = swapNode2.val;

        swapNode2.val = temp;

        return head;

    }

Complexity: O(n)

[LeetCode] Merge In Between Linked Lists

Problem: You are given two linked lists: list1 and list2 of sizes n and m respectively. Remove list1's nodes from the ath node to the bth node, and put list2 in their place.

The blue edges and nodes in the following figure indicate the result:

Build the result list and return its head.

Example:

Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [0,1,2,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Constraints:

• 3 <= list1.length <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 104

Approach: The approach is straight forward. We will store the (a - 1)th node and (b + 1)th node of list1. Now we can put list2 to the next of (a - 1)th node of list1. We traverse the whole list2 and in the end we will put the stored (b + 1)th node of list1 to the next of end of list2 and that's all.

Implementation in C#: 

    public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) 

    {

        ListNode node = list1;

        ListNode mergeStartNode = null;

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

        {

            if (i == a - 1)

            {

                mergeStartNode = node;

            }        

            node = node.next;

        }        

        ListNode mergeEndNode = node;

        mergeStartNode.next = list2;

        node = list2;

        while (node.next != null)

        {

            node = node.next;

        }

        node.next = mergeEndNode;

        return list1;

    }

Complexity: O(n)

[LeetCode] Cousins in Binary Tree

Problem: Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• 1 <= Node.val <= 100
• Each node has a unique value.
• x != y
• x and y are exist in the tree.

Approach: We can use level order traversal to solve this question. Basically if both x and y are on the same level means both have the same depth.

Now while inserting current node's left and right in the queue, we can check left and right nodes have the value x and y. If yes, then we can return false as parent of x and y is same. 

Implementation in C#:

    public bool IsCousins(TreeNode root, int x, int y) 

    {

        bool foundX = false, foundY = false;

        Queue<TreeNode> queue = new Queue<TreeNode>();

        queue.Enqueue(root);

        while(queue.Count > 0)

        {

            int size = queue.Count;

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

            {

                TreeNode node = queue.Dequeue();

                if (node.val == x)

                {

                    foundX = true;

                }

                else if (node.val == y)

                {

                    foundY = true;

                }

                if (node.left != null && node.right != null)

                {

                    // Check for same parent

                    if ((node.left.val == x && node.right.val == y) 

                        || (node.left.val == y && node.right.val == x))

                    {

                        return false;

                    }

                }

                if (node.left != null)

                {

                    queue.Enqueue(node.left);

                }  

                if (node.right != null)

                {

                    queue.Enqueue(node.right);

                }

            }  

            if (foundX && foundY)

            {

                return true;

            }

            else if (foundX || foundY)

            {

                return false;

            }

        }        

        return false;

    }

Complexity: O(n)

[LeetCode] Next Greater Element I

Problem: The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Approach: The problem is similar to our previous problem Next Greater Element and we are going to use the same approach here too. That means we are going to use Stack to find the next greater element for every element of num2 and store it in a hash map.

Using this hash map, we can the quickly see if the elements in the num1 has any next greater element or not. If yes, we will add that otherwise we will add -1. That's all!

Implementation in C#:

    public int[] NextGreaterElement(int[] nums1, int[] nums2) 

    {

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

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

        foreach (int num in nums2)

        {

            while (stack.Count > 0 && stack.Peek() < num)

            {

                nextGreaterDict.Add(stack.Peek(), num);

                stack.Pop();

            }

            stack.Push(num);

        }

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

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

        {

            result[i] = nextGreaterDict.ContainsKey(nums1[i]) ? nextGreaterDict[nums1[i]] : -1;

        }        

        return result;

    }

Complexity: O(m + n) where m is size of nums1 and n is size of nums2.

[LeetCode] Guess Number Higher or Lower

Problem: We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns 3 possible results:

• -1: The number I picked is lower than your guess (i.e. pick < num).
• 1: The number I picked is higher than your guess (i.e. pick > num).
• 0: The number I picked is equal to your guess (i.e. pick == num).

Return the number that I picked.

Example:

Input: n = 10, pick = 6
Output: 6

Input: n = 1, pick = 1
Output: 1

Input: n = 2, pick = 1
Output: 1

Input: n = 2, pick = 2
Output: 2

Approach: It's a straight forward binary search problem. You can look at the implementation to understand the approach.

Implementation in C#:

        public int GuessNumber(int n)

    {

        int start = 0, end = n;

        while (start <=  end)

        {

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

            int guessRes = guess(mid);

            if (guessRes == 0)

            {

                return mid;

            }

            else if(guessRes == -1)

            {

                end = mid - 1;

            }

            else

            {

                start = mid + 1;

            }

        }

        return -1;

    }

Complexity: O(logn)

[LeetCode] Word Search

Problem: Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Constraints:

• m = board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Approach: This problem is same as finding "microsoft" in a 2D matrix. Here we just need to find any string which is given as input. We will use the exactly same backtracking approach which we applied in the previous problem.

Implementation in C#:

    public bool Exist(char[][] board, string word) 

    {

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

        {

            for (int j = 0; j < board[0].Length; ++j)

            {

                if (board[i][j] == word[0])

                {

                    if (this.Search(board, i, j, word, 0))

                    {

                        return true;

                    }

                }

            }

        }

        return false;

    }

    

    private bool Search(char[][] board, int i, int j, string word, int currIndex)

    {

        if (currIndex == word.Length)

        {

            return true;

        }

        if (!this.Check(board, i, j, word[currIndex]))

        {

            return false;

        }

        char temp = board[i][j];

        board[i][j] = '#';

        bool result = this.Search(board, i - 1, j, word, currIndex + 1) ||

            this.Search(board, i + 1, j, word, currIndex + 1) ||

            this.Search(board, i, j - 1, word, currIndex + 1) ||

            this.Search(board, i, j + 1, word, currIndex + 1);

        board[i][j] = temp;

        return result;

    }

    

    private bool Check(char[][] board, int i, int j, char ch)

    {

        if (i >= 0 && i < board.Length && j >= 0 && j < board[0].Length && board[i][j] == ch)

            return true;

        return false;

    }

Complexity: O( m * n * 3 ^ l) where m is number of rows, n is number of columns and l is the length of word.

[LeetCode] Island Perimeter

Problem: You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Input: grid = [[1]]
Output: 4

Input: grid = [[1,0]]
Output: 4

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.
• There is exactly one island in grid.

Approach: If a cell is land then its contribution to island's perimeter is 4 initially. In case of any land neighbour cell of current cell means from the current cell one side is gone which was part of perimeter of the island so we need to subtract 1 from the perimeter. With this intuition we can have following approach:

• FOR i = 0 to rows
• FOR j = 0 to cols
• IF grid[i][j] == 1
• perimeter = perimeter + 4
• IF left cell is 1 
• perimenter = perimeter - 1
• IF right cell is 1 
• perimenter = perimeter - 1
• IF up cell is 1 
• perimenter = perimeter - 1
• IF down cell is 1 
• perimenter = perimeter - 1

Implementation in C#:

    public int IslandPerimeter(int[][] grid) 

    {

        int rows = grid?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = grid[0].Length;

        int perimeter = 0;

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

        {

            for (int j = 0; j < cols; ++j)

            {

                if (grid[i][j] == 1)

                {

                    perimeter += 4;

                    // Left neighbour

                    if (j - 1 >= 0 && grid[i][j -1] == 1)

                    {

                        --perimeter;

                    }

                    // Right neighbour

                    if (j + 1 < cols && grid[i][j + 1] == 1)

                    {

                        --perimeter;

                    }

                    // Up neighbour

                    if (i - 1 >= 0 && grid[i - 1][j] == 1)

                    {

                        --perimeter;

                    }

                    // Down neighbour

                    if (i + 1 < rows && grid[i + 1][j] == 1)

                    {

                        --perimeter;

                    }

                }

            }

        }

        return perimeter;

    }

Complexity: O(m * n) where m is number of rows and n is number of columns.

[Facebook] Maximum Size Subarray Sum Equals k

Problem: Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4  
Explanation: [1,-1,5,-2] is the longest subarray with sum 3.

Input: nums = [2,-1,2,1], k = 1
Output: 2
Explanation: [2,-1] or [-1,2] are the longest subarrays with sum 1.

Approach: We can use hashing here. Basically we will store the [0...i] cumulative sum as key and index i as the value. We can always check if current cumulative sum - k is in the hash table or not. If yes, we can get its index from hash table. The subarray length will be i - value_index + 1. Now we just need to get the max of such subarray's length.

Implementation in C#:

    public int maxLen(int[] arr, int n, int k)

    {

        int length = arr?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

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

        int sum = 0;

        int maxLen = 0;

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

        {

            sum += arr[i];

            if (sum == k)

            {

                maxLen = i + 1;

            }

            else if (sumMap.ContainsKey(sum - k))

            {

                maxLen = Math.Max(maxLen, i - sumMap[sum - k]);

            }

            

            if (!sumMap.ContainsKey(sum))

            {

                sumMap[sum] = i;

            }

        }

        return maxLen;

    }

Complexity: O(n)

[LeetCode] Longest Common Subsequence

Problem: Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Approach: Obviously we are going to use DP here. We are going to maintain a 2D table where table[i][j] will tell the longest common subsequence of substrings text1[0...i] and text2[0...j]. Here is how we can fill the table:

• IF text1[i] == text2[j] then table[i][j] = table[i - 1][j - 1] + 1
• ELSE table[i][j] = MAX(table[i - 1][j], table[i][j - 1]

In the end we will return table[len1-1][len2-1] where len1 and len2 are the length of text1 and text2 respectively.

Implementation in C#:

    public int LongestCommonSubsequence(string text1, string text2) 

    {

        int[,] table = new int[text1.Length + 1, text2.Length + 1];

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

        {

            for (int j = 1; j <= text2.Length; ++j)

            {

                if (text1[i - 1] == text2[j - 1])

                {

                    table[i, j] = table[i - 1, j - 1] + 1;

                }

                else

                {

                    table[i, j] = Math.Max(table[i - 1, j], table[i, j - 1]);

                }

            }

        }

        return table[text1.Length, text2.Length];

    }

Complexity: O(m * n) where m is the length of text1 and n is the length of text2.