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