[LeetCode] Frog Jump

Problem: A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

Example:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Approach: We can look at this problem as a Graph where its node contains position and the amount of jump. Now a node is connected to another node if target node is reachable from source node. 

We can just apply BFS to see if we can reach from first stone to last stone.

Implementation in C#:

public class Jump

{

    public int Position { get; set; }

    public int PrevJump { get; set; }

    public Jump(int pos, int jump)

    {

        this.Position = pos;

        this.PrevJump = jump;

    }

}

public class Solution 

{    

    public bool CanCross(int[] stones) 

    {

        if (stones.Length <= 1)

        {

            return true;

        }        

        HashSet<int> stonesSet = new HashSet<int>(stones);

        HashSet<string> visited = new HashSet<string>();

        if (stones[1] != 1)

        {

            return false;

        }

        Queue<Jump> jumps = new Queue<Jump>();

        int lastStone = stones[stones.Length - 1];

        jumps.Enqueue(new Jump(0, 0));        

        while (jumps.Count > 0)

        {

            Jump jump = jumps.Dequeue();

            if (jump.Position == lastStone)

            {

                return true;

            }

            for (int i = jump.PrevJump - 1; i <= jump.PrevJump + 1; ++i)

            {

                if (i <= 0)

                {

                    continue;

                }

                string visitKey = (jump.Position + i) + " " + i; 

                if (stonesSet.Contains(jump.Position + i) && !visited.Contains(visitKey))

                {

                    visited.Add(visitKey);

                    jumps.Enqueue(new Jump(jump.Position + i, i));

                }

            }

        }

        return false;

    }

Complexity: O(n)

[LeetCode] Predict the Winner

Problem: You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

Example:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.

Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Approach: Few things which we can just guess by looking at the problem and different examples are if n <= 2, Player1 will always win, also if n is even then Player 1 will always win where n is the length of nums array.

Now let's see how we can solve it. Let's define a variable effective_score which will have the difference of current player score and other player score i.e.

effective_score = curr_player_score - other_player_score

where curr_player is the player whose turn is to choose the integer from nums.

Obviously if player 1's effective_score is >= 0 then player 1 wins, otherwise lose.

Now given num[i...j] array, current player effective_score would be

effective_score(nums[i...j)  = MAX(nums[i] - effective_score(nums[i + 1...j), nums[j] - effective_score(nums[i...j - 1])

Meaning of above recursive relation is as follows: current player chooses 

• nums[i]:  effective_score will be nums[i] - effective_score of other player for nums[i + 1...j]  
• nums[j]:  effective_score will be nums[j] - effective_score of other player for nums[i...j - 1]

Obviously we want to take the maximum of the above 2 to calculate the effective_score.

This will surely solve the problem but it will not be efficient. The size of the recursion tree will be 2^n here.

We can optimize it using DP. We can have a 2D table say Table, where Table[i][j] will tell the effective score of player 1 in the sub array nums[i...j]. We can simply fill this table as follows:

Table[i][j] = MAX(nums[i] - Table[i + 1][j], nums[j] - Table[i][j - 1])

Above line is just like the recursive relation so nothing to explain here.

Implementation in C#:

Approach 1: Recursion:

    public bool PredictTheWinner(int[] nums) 

    {

        if (nums.Length <= 2)

        {

            return true;

        }

        if (nums.Length % 2 == 0)

        {

            return true;

        }        

        return this.EffectiveScore(nums, 0, nums.Length - 1) >= 0;

    }

    

    private int EffectiveScore(int[] nums, int start, int end)

    {

        if (start == end)

        {

            return nums[start];

        }

        int scoreWithStart = nums[start] - this. EffectiveScore(nums, start + 1, end);

        int scoreWithEnd = nums[end] - this. EffectiveScore(nums, start, end - 1);

        return Math.Max(scoreWithStart, scoreWithEnd);

    }

Approach 2: DP:

    public bool PredictTheWinner(int[] nums) 

    {

        if (nums.Length <= 2)

        {

            return true;

        }

        if (nums.Length % 2 == 0)

        {

            return true;

        }

        int[,] table = new int[nums.Length, nums.Length];

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

        {

            table[i, i] = nums[i];

        }

        for (int i = nums.Length - 2; i >= 0; --i)

        {

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

            {

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

            }

        }

        return table[0, nums.Length - 1] >= 0;

    }

Complexity: Approach 1: O(2^n), Approach 2: O(n^2)

[LeetCode] Can I Win

Problem: In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

Example:

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation: No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true

Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true

Constraints:

• 1 <= maxChoosableInteger <= 20
• 0 <= desiredTotal <= 300

Approach: We can use simple recursion (DFS) to solve this question. We can do something like following:

• FOR i = 1 TO maxChoosableInteger
• IF i is not used
• // 1st player can win if desired total can be achieved or second player can't win
• IF desiredTotal <= i OR NOT CanWin(desiredTotal - i)
• RETURN True
• RETURN False

The only problem in the above solution is the time complexity which is !n where n is maxChoosableInteger.  We can improve it using memorization  / DP. If you see we are solving the problem for same state again and again. We can basically memorize that at a certain state (used integers) the 1st player won or not and we can use it to make this program efficient.

Implementation in C#:

    public bool CanIWin(int maxChoosableInteger, int desiredTotal) 

    {

        if (maxChoosableInteger >= desiredTotal)

        {

            return true;

        }

        if (desiredTotal > ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2))

        {

            return false;

        }

        // Can use a integer to keep track of what ints are already used as maxChoosableInteger 

       // is not more than 20

        int currState = 0;

        //memorization: currState(Used Integers) => Player 1 win / loss (true / false)

        Dictionary<int, bool> table = new Dictionary<int, bool>();

        return this.CanWin(maxChoosableInteger, desiredTotal, currState, table);

    }

    

    public bool CanWin(

        int maxChoosableInteger, 

        int desiredTotal, 

        int currState, 

        Dictionary<int, bool> table)

    {

        if (table.ContainsKey(currState))

        {

            return table[currState];

        }

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

        {

            // Integer is already used

            if ((currState & (1 << (i - 1))) != 0)

            {

                continue;

            }

            // total achieved or second player lost

            if (desiredTotal <= i || 

                !CanWin(maxChoosableInteger, desiredTotal - i, (currState | (1 << (i - 1))), table))

            {

                table[currState] = true;

                return true;

            }

        }

        table[currState] = false;

        return false;

    }

Complexity: O(n * 2 ^ n)

Sort an array of 0, 1, 2 and 3.

Problem: Sort an array which only contains 0, 1, 2 and 3

Example:

Input: arr = [0, 3, 1, 2, 0, 1, 3, 1, 2]
Output: [0, 0, 1, 1, 1, 2, 2, 3, 3]

Approach: The problem is similar to the problem of sorting an array containing only 0, 1 and 2. We will use the same approach which we took there. We will start with three pointers low, high and mid but here we want mid to have both 1 and 2 so our intermediate result would be something like:

0, 0, 0, ..., 0,  1, 2, 2, 1, 2, 1, 3, 3, 3, ... 3

Now we just need to sort the mid array which contains only 1 and 2. We can use the approach which we have taken to solve the problem of sorting array containing only 0 and 1.

Implementation in C#:

    private static void Sort0123(int[] arr)

    {

        int low = 0, mid = 0, high = arr.Length - 1;

        while (mid <= high)

        {

            switch(arr[mid])

            {

                case 0: 

                    Swap(arr, low, mid);

                    ++low;

                    ++mid;

                    break;

                case 1:

                case 2:

                    ++mid;

                    break;

                case 3:

                    Swap(arr, mid, high);

                    --high;

                    break;

                default:

                    break;

            }

        }

        while(low <= high)

        {

            if (arr[low] == 2)

            {

                Swap(arr, low, high);

                --high;

            }

            else

            {

                ++low;

            }

        }

        

    }

Complexity: O(n)

[LeetCode] Combination Sum III

Problem: Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Approach: We can use backtracking here. The recursive relation would be something like below:

f(k, n, i) = f(k - 1, n - i, i - j), where j is (i + 1)....9

Implementation in C#:

    public IList<IList<int>> CombinationSum3(int k, int n)

    {

        var currNums = new List<int>();

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

        this.CombinationSum(k, n, currNums, 1, result);

        return result;

    }

    private void CombinationSum(int k,

                                int n,

                                List<int> currNums,

                                int currNum,

                                List<IList<int>> result)

    {

        if (currNums.Count == k)

        {

            if (n == 0)

            {

                Console.WriteLine($"Adding {string.Join(", ", currNums)}");

                result.Add(new List<int>(currNums));

            }

            return;

        }

        for (int i = currNum; i <= 9; ++i)

        {

            if (n - i >= 0)

            {

                currNums.Add(i);

                this.CombinationSum(k, n - i, currNums, i + 1, result);

                currNums.RemoveAt(currNums.Count - 1);

            }

            else

            {

                break;

            }

        }

    }

Complexity: O(2 ^ 9)

[LeetCode] Word Search II

Problem: Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must 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 in a word.

Example:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Approach: The problem is similar to the problem of search a word in a matrix except here we are given an array of words. We will have the similar backtracking approach here too but we will use Trie to make it more efficient.

Implementation:

public class TrieNode

{

    public const short ALPHABET_SIZE = 26;

    public TrieNode(char value)

    {

        this.Value = value;

        this.Children = new TrieNode[ALPHABET_SIZE];

        this.End = 0;

    }

    public char Value { get; set; }

    public TrieNode[] Children { get; set; }

    public string Word { get; set; }

    public int End { get; set; }

}

public class Trie

{

    public Trie()

    {

        this.root = new TrieNode('/'); // special charater for root

    }

    public void Insert(string word)

    {

        TrieNode node = root;

        foreach(char ch in word)

        {

            if (node.Children[ch - 'a'] == null)

            {

                node.Children[ch - 'a'] = new TrieNode(ch);

            }

            node = node.Children[ch - 'a'];

        }

        node.End++;

        node.Word = word;

    }

    

    public void SearchOnBoard(char[][] board, int i, int j, List<string> result)

    {

        if (this.root.Children[board[i][j] - 'a'] == null)

        {

            return;

        }

        this.SearchOnBoard(this.root, board, i, j, result);     

    }

    

    private void SearchOnBoard(TrieNode node, char[][] board, int i, int j, List<string> result)

    {

        int index = board[i][j] - 'a';

        if (board[i][j] == '#' || node.Children[index] == null)

        {

            return;

        }

        node = node.Children[index];

        if (node.End > 0)

        {

            result.Add(node.Word);

            node.End--;

        }

        char temp = board[i][j];

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

        if (i > 0)

        {

            SearchOnBoard(node, board, i - 1, j, result);

        }

        if (i < board.Length - 1)

        {

            SearchOnBoard(node, board, i + 1, j, result);

        }

        if (j > 0)

        {

            SearchOnBoard(node, board, i, j - 1, result);

        }

        if (j < board[0].Length - 1)

        {

            SearchOnBoard(node, board, i, j + 1, result);

        }

        board[i][j] = temp;

    }

    private TrieNode root;

}

public class Solution 

{

    public IList<string> FindWords(char[][] board, string[] words) 

    {

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

        int rows = board?.Length ?? 0;

        if (rows == 0)

        {

            return result;

        }

        int cols = board[0].Length;

        int length = words.Length;

        if (length == 0)

        {

            return result;

        }

        Trie trie = new Trie();

        foreach(string word in words)

        {

            trie.Insert(word);

        }

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

        {

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

            {

                trie.SearchOnBoard(board, i, j, result);

            }

        }

        return result;

    }

}

Complexity: O( rows * cols * 3 ^ (length of the largest word in words)) 

[LeetCode] Search in Rotated Sorted Array II

Problem: There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example:

Input: nums = [1,0,1,1,1], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Approach: This question is similar to search an element is sorted rotated array but here the elements in the array might not be distinct. We will apply the same approach here with little modification to avoid duplicate values. You can look at the implementation to understand the extra step.

Implementation in C#:

    public bool Search(int[] nums, int target) 

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return false;

        }

        int start = 0, end = length - 1;

        while (start <= end && nums[start] == nums[end])

        {

            if (nums[start] == target)

            {

                return true;

            }

            ++start;

            --end;

        }  

        while (start <= end)

        {

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

            if (target == nums[mid]) 

            {

                return true;

            }     

            if (nums[start] <= nums[mid])

            {

                if (target >= nums[start] && target < nums[mid])

                {

                    end = mid - 1;

                }

                else

                {

                    start = mid + 1;

                }

            }

            else

            {

                if (target > nums[mid] && target <= nums[end])

                {

                    start = mid + 1;

                }

                else

                {

                    end = mid - 1;

                }

            }

        }        

        return false;

    }

Complexity: O(n)