Saturday, September 5, 2020

Minimum Path Sum

Problem: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Approach: Use DP


        public static int MinPathSum(int[][] grid)

        {

            if (grid == null || grid.Length == 0)

            {

                return 0;

            }

            int m = grid.Length;

            int n = grid[0].Length;

            int[,] sum = new int[m, n];

            sum[0, 0] = grid[0][0];

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

            {

                sum[i, 0] = sum[i-1, 0] + grid[i][0];

            }

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

            {

                sum[0, i] = sum[0, i-1] + grid[0][i];

            }

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

            {

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

                {

                    sum[i, j] = Math.Min(sum[i, j - 1], sum[i - 1, j]) + grid[i][j];

                }

            }

            return sum[m - 1, n - 1];

        }

Unique paths with obstacles

Problem:  A robot is located at the top-left corner(0, 0) of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner (m -1, n-1) of the grid.

Now consider if some obstacles are added to the grids. How many unique paths would there be?


        public static int UniquePathsWithObstacles(int[][] obstacleGrid)

        {

            if (obstacleGrid == null || obstacleGrid.Length == 0)

            {

                return 0;

            }

            int m = obstacleGrid.Length;

            int n = obstacleGrid[0].Length;

            int[,] count = new int[m, n];

            count[0, 0] = obstacleGrid[0][0] == 0 ? 1 : 0;

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

            {

                if (obstacleGrid[i][0] == 0)

                {

                    count[i, 0] = count[i - 1, 0];

                }

            }

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

            {

                if (obstacleGrid[0][i] == 0)

                {

                    count[0, i] = count[0, i -1];

                }

            }

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

            {

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

                {

                    if (obstacleGrid[i][j] == 0)

                    {

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

                    }

                }

            }

            return count[m - 1, n - 1];

        }

[LeetCode] Unique Paths

Problem: A robot is located at the top-left corner(0, 0) of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Example:

Input: m = 3, n = 7
Output: 28
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down


Approach: It's a simple DP problem. Just look at the implemetation to understand the approach.


Implementation in C#:

    public int UniquePaths(int m, int n)
    {
        int[,] table = new int[m, n];
        for (int i = 0; i < m; ++i)
        {
            table[i, 0] = 1;
        }
        for (int i = 0; i < n; ++i)
        {
            table[0, i] = 1;
        }
        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                table[i, j] = table[i - 1, j] + table[i, j - 1];
            }
        }
        return table[m - 1, n - 1];
    }


Complexity: O(m * n)

[LeetCode] Rotate List

Problem: Given the head of a linked list, rotate the list to the right by k places.

Example:

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

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


Approach: This is an implementation problem. Just look at the implementation to understand it. Basically to rotate list right, we need to get the kth node from the end. Say its called kthNode. We also need to get end node as it's next will be current head and (k-1)th next will be null.

The kthNode will be the new head. That's all!


Implementation in C#:

    public ListNode RotateRight(ListNode head, int k)
    {
        if (head?.next == null || k == 0)
        {
            return head;
        }
        int length = this.GetLength(head);
        if (length <= k)
        {
            if (k % length == 0)
            {
                return head;
            }
            k = k % length;
        }
        ListNode curr = head;
        ListNode fwd = head;
        for (int i = 0; i < k; ++i)
        {
            fwd = fwd.next;
        }
        while (fwd.next != null)
        {
            curr = curr.next;
            fwd = fwd.next;
        }
        fwd.next = head;
        head = curr.next;
        curr.next = null;
        return head;
    }

    private int GetLength(ListNode node)
    {
        int count = 0;
        while (node != null)
        {
            node = node.next;
            ++count;
        }
        return count;
    }


Complexity: O(n)


[LeetCode] Length of Last Word

Problem: Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Example:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.
Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.
Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.


Approach: This is a simple implementation problem. You can just look at the implementation to understand the approach.


Implementation in C#:

    public int LengthOfLastWord(string s)
    {
        int length = s?.Length ?? 0;
        if (length == 0)
        {
            return 0;
        }
        int endIndex = length - 1;
        while (endIndex >= 0 && s[endIndex] == ' ')
        {
            --endIndex;
        }
        if (endIndex < 0)
        {
            return 0;
        }
        int startIndex = endIndex - 1;
        while (startIndex >= 0 && s[startIndex] != ' ')
        {
            --startIndex;
        }
        return endIndex - startIndex;
    }

Complexity: O(n)

Insert Interval

Problem: Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].


Approach: First we insert the newInterval to the right position according to it's start time and then we merge these intervals.


Implementation in C#:

        public static int[][] InsertAndMergeInterval(int[][] intervals, int[] newInterval)

        {

            if (intervals == null)

            {

                return null;

            }

            int[][] temp = new int[intervals.Length + 1][];

            bool newIntervalAdded = false;

            int j = 0;

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

            {

                if (!newIntervalAdded && intervals[i][0] > newInterval[0])

                {

                    temp[j++] = newInterval;

                    newIntervalAdded = true;

                }

                temp[j++] = intervals[i];

            }        

            if (!newIntervalAdded)

            {

                temp[j] = newInterval;

            }

            return MergeInterval(temp);

        }


        public static int[][] MergeInterval(int[][]intervals)

        {

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

            result.Add(intervals[0]);

            int resultIndex = 0;

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

            {

                if (result[resultIndex][1] >= intervals[i][0])

                {

                    int[] interval = new int[2];

                    interval[0] = result[resultIndex][0];

                    interval[1] = Math.Max(result[resultIndex][1], intervals[i][1]);

                    result.RemoveAt(resultIndex);

                    result.Add(interval);

                }

                else

                {

                    result.Add(intervals[i]);

                    ++resultIndex;

                }

            }

            return result.ToArray();

        }


Complexity: O(n)

Friday, September 4, 2020

[Amazon] Best Time to Buy and Sell Stock With Multiple Transactions

Problem: Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.


Approach: Not much to say here. It's a simple greedy approach. You can understand the approach by just looking at the implementation. 


Implementation in C#:

    public int MaxProfit(int[] prices)
    {
        int length = prices?.Length ?? 0;
        if (length <= 1)
        {
            return 0;
        }
        int i = 0, result = 0;
        while (i < length)
        {
            while (i < length - 1 && prices[i] >= prices[i + 1])
            {
                ++i;
            }
            int buyIndex = i;
            while (i < length - 1 && prices[i] < prices[i + 1])
            {
                ++i;
            }
            int sellIndex = i;
            result += Math.Max(0, prices[sellIndex] - prices[buyIndex]);
            ++i;
        }
        return result;
    }


Complexity: O(n)