Recursion and Dynamic Programming

Come on, you can do it :)

Dynamic programming is mostly just a matter of taking a recursive algorithm and finding the overlapping subproblems. You then cache the results for future recursive calls.

There are generally 2 approaches to such questions

• Memoisation

Looking at the tree above, you see that fib(3) appears twice etc…so we should do caching to save on amount of work done.

• Bottom-Up Approach -> Solve the problem for a simple case, then build up the solution.

This can be thought of as similar to doing the recursive memoized approach but in reverse.

First, we compute fib(1) and fib(0), which are already known from the base cases. Then we use those to compute fib(2). Then we use the prior answers to compute fib(3), then fib(4) and so on.

Recursive + DP solution

How to determine when to give a dynamic programming solution?

• When the problem is recursive and can be built off subproblems.
• “Design an algorithm to compute the nth…” “Write code to list the first nth…” “Implement a method to compute all..”
• Find the biggest…

312 Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

Solution

For those who are not able to understand any solution [WITH DIAGRAM] - Burst Balloons - LeetCode

This problem seems like the order of solving sub prob changes the ans. The subproblems are not independent of each other. i=start and j=end.

coins nums[k-1]*nums[k]*nums[k+1] + rec(i, k-1) + rec(k+1,j)

Instead of thinking, which k balloon to burst first we think of it in the other way round.

We choose the kth balloon as the last one to be burst. Now the subproblems will become independent since (k — 1)th balloon and (k + 1)th balloon won’t need each other in order to calculate the answer. (Try it out using pen and paper).

Now for each k starting from i to j, we choose the kth balloon to be the last one to be burst and calculate the profit by solving the subproblems recursively. Whichever choice of k gives us the best answer, we store it and return.
Important point to be noted here is that the balloons in the range (i, k — 1) and (k + 1, j) will be burst BEFORE kth balloon. So, when we burst the kth balloon, the profit will be nums[i — 1] * nums[k] * nums[j + 1] PROVIDED that index i — 1 and j + 1 are valid.

class Solution {
    public int maxCoins(int[] nums) {

        int len = nums.length;

        int [] arr = new int[len+2];
        arr[0]=1;
        arr[len+1]=1;
        for(int i=1; i<=len; i++){
            arr[i]=nums[i-1];
        } // pad nums with 1s on both ends

        int[][] memo = new int[nums.length + 1][nums.length + 1];
        for(int[] row: memo){
            Arrays.fill(row, -1);
        }
        return maxCoinHelper(arr, 1, len, memo);

    }

    public int maxCoinHelper(int[] nums, int start, int end, int[][] memo){
        if(start>end) return 0;
        if(memo[start][end] != -1) return memo[start][end];
        int max = Integer.MIN_VALUE;
        for(int ind=start; ind<=end; ind++){
            int coins = (nums[start-1]*nums[ind]*nums[end+1]) + maxCoinHelper(nums, start, ind - 1, memo) + maxCoinHelper(nums, ind+1, end, memo);
            max = Math.max(max, coins);
        }
        memo[start][end] = max;
        return max;
    }
}

Interview Cake — Practice Question

Qns 1 a: Write a recursive method for generating all permutations of an input string. Return them as a set.

Definition of permutation: Any ordering of words. For eg, “cat” has the following permutation:

cat
cta
atc
act
tac
tca

If we want to form the permutation of cats, and we have all the permutations of cat, then what we need to do is to put “s” in each possible position in each of these permutations.

Now that we can break the problem into subproblem, we just need a base case and we have a recursive algorithm.

public static List singletonList(T o)

Parameters: This method takes the object o as a parameter to be stored in the returned list.

Return Value: This method returns an immutable list containing only the specified object.

Qns 1 b: Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

The trick to understanding the code here is very simple: Simply write out and follow through the code with a simple example, for eg [1,2,3]

1. We first traverse to the end of the int array. Return the last element of the num array as a list. For eg, if last element is 3, we return [[3]]
2. Then, the caller function will receive this returned list.
3. At the caller function, the second last element -> The element before -> will be stored in a variable called firstChar. This firstChar will then be inserted in all possible positions of the returned list. For eg, here, firstChar=2. So after going through line 24–34, the output finalised list will be [[2,3],[3,2]]
4. Again, this list will be returned to the previous caller function. Repeating 3, we then get

[[1,2,3],[2,1,3],[2,3,1],

[1,3,2,],[3,1,2],[3,2,1]]

This gives us all the permutations :)

• Might be better to use HashSet instead of List because List can have duplicates.

Leet Code 47 Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Use HashSet

Qns 1c: Leetcode 22. Generate Parentheses

Brute Force: To generate all possible permutations like Qns 1a, 1b. Then check the validity of each permutation and discard those invalid ones.

More efficient solution: Think of it as trying out every permutation of the string, deciding whether to add an open-bracket or close-bracket to a string.

1. The first char of the string must always be a (, hence i start by initialising the base string to only contain (.
2. If the number of ( is smaller than the number of ), only then we can add )
3. We can always add ( as long as there are (

For this, we notice that we cannot really return the ArrayList<String> of all possible permutations because we want to have a complete string each time we return something (unlike previous 1a,1b questions where we will create the new permutation based on the returned permutations). So i created a public static ArrayList instead and we will append all possible combinations to this.

Another way is to change line 12: if(leftBrackets==0&&rightBrackets==0)

Qns 2: Write a method fib() that takes an integer n and returns the nth Fibonacci number.

A pretty easy dynamic programming question..

Fib(0) // 0

Fib(1) // 1

Fib(2) //1

Fib(3) //2

Fib(4) //3

Qns 3: Your quirky boss collects rare, old coins… (Also Leet Code 322)

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Leet Code 518 (Follow up Qns) Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Return all METHODS.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Leet Code 39. Combination Sum (similar to coin change)

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Example 4:

Input: candidates = [1], target = 1
Output: [[1]]

Example 5:

Input: candidates = [1], target = 2
Output: [[1,1]]

Correct solution, but slow.

Another correct solution but also SLOW. Slightly faster than the previous solution. This one follows the coin change problem 2.

Leet Code 40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Correct Solution.

Line 52 skips duplicates because consider when we are at recursion R1. For eg, if we have [1,1,2] where the start is at index 0, the first 1, we skip evaluating the second 1 at line 52. This second 1 will then be evaluated in the next recursion R2 where start=1. Here, tempList will then contain [1,1] where 1 comes from the first index 0 and the second 1 comes from the second index 1.

If we did not skip (do not have line 52), then it could be that at R2, the tempList would be [1,1], where both 1s comes from the same second index of the original int[] cand. For example, we add in the first 1 (in index 1, second 1) was added in R1 and the second 1 (index 1) was repeatedly added in R2.

Hence, duplicates.

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        Arrays.sort(candidates);
        backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start){
        if(remain<0) {
            return;     
        } else if (remain == 0) {
            list.add(new ArrayList<>(tempList));
        } else {
            for(int i=start; i<cand.length; i++){
                if(i>start && cand[i]==cand[i-1]) continue; // skip duplicates
                if(remain-cand[i]<0) break; // optimisation
                tempList.add(cand[i]);
                backtrack(list, tempList, cand, remain-cand[i], i+1);
                tempList.remove(tempList.size()-1);
            }
        }
    }
}

Not sure why this gives time limit exceeded error….

216. Combination Sum III

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 1:

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

Example 2:

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.

Example 3:

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.

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new LinkedList<>();
        Queue<Info> queue = new LinkedList<>();
        queue.add(new Info(n, new LinkedList<Integer>()));
        int level = 0;
        while(!queue.isEmpty()){
            int remainders = queue.size();
            level++;
            while(remainders>0){
                Info info = queue.poll();
                int val = info.value;
                List<Integer> list = info.ls;
                for(int i=9; i>=1; i--){
                    int remainder = val-i;
                    List<Integer> copy = new LinkedList<>();
                    for(int j: list){
                        copy.add(j); 
                    }
                    copy.add(i);
                    if(remainder==0 && level==k && !list.contains(i) && i<list.get(list.size()-1)){
                      // !list.contains(i) -> Ensure that we don't add duplicates. 
                      // i<list.get(list.size()-1) -> Since list is sorted in desc order (for loop is from 9 to 1), 
                      // each time we add a value, it should be smaller than the 
                      // value at the end of the list. This ensures we don't add duplicates. Eg, [1,2] and [2,1] we will only add [2,1]
                      result.add(copy);
                    } else if (remainder>0 && !list.contains(i) && (list.size() == 0 || i<list.get(list.size()-1))){
                        queue.add(new Info(remainder, copy));
                    }
                }
                remainders--;
            }
            if(level>=k) break;
        }

        return result;

    }

    public class Info{
        int value;
        List<Integer> ls; // sorted big to small
        public Info(int value, List<Integer> ls){
            this.value=value;
            this.ls=ls;

        }
    }
}

Alternative

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new LinkedList<>();
    
        Queue<Info> queue = new LinkedList<>();
        queue.add(new Info(n, new LinkedList<Integer>()));
        int level = 0;
        while(!queue.isEmpty()){
            int remainders = queue.size();
            level++;
            while(remainders>0){
                Info info = queue.poll();
                int val = info.value;
                List<Integer> list = info.ls;
                for(int i=1; i<=9; i++){
                    int remainder = val-i;
                    List<Integer> copy = new LinkedList<>();
                    copy.add(i);
                    for(int j: list){
                        copy.add(j); // small to big
                    }
                   
                    if(remainder==0 && level==k && !list.contains(i) && i>list.get(0)){
                        result.add(copy);
                    } else if (remainder>0 && !list.contains(i) && (list.size() == 0 || i>list.get(0))){
                        queue.add(new Info(remainder, copy));
                    }
                }
                remainders--;
            }
            if(level>=k) break;
        }

        return result;

    }

    public class Info{
        int value;
        List<Integer> ls;
        public Info(int value, List<Integer> ls){
            this.value=value;
            this.ls=ls;

        }
    }
}

Visualise this problem to be like BFS traversal. From the number n, we want to find the next smaller value and traverse until we reach 0. It’s similar to another leetcode qns 279.

Leet Code 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

This question is similar to Coin Change…

An easy understanding DP solution in Java - LeetCode Discuss

dp[n] = Min{ dp[n - i*i] + 1 },  n - i*i >=0 && i >= 1

Alternative solution

class Solution {
  public int numSquares(int n) {

    ArrayList<Integer> square_nums = new ArrayList<Integer>();
    for (int i = 1; i * i <= n; ++i) {
      square_nums.add(i * i);
    }

    Set<Integer> queue = new HashSet<Integer>();
    queue.add(n);

    int level = 0;
    while (queue.size() > 0) {
      level += 1;
      Set<Integer> next_queue = new HashSet<Integer>();

      for (Integer remainder : queue) {
        for (Integer square : square_nums) {
          if (remainder.equals(square)) {
            return level;
          } else if (remainder < square) {
            break;
          } else {
            next_queue.add(remainder - square);
          }
        }
      }
      queue = next_queue;
    }
    return level;
  }
}

Approach 4 (Current code) time complexity

Approach 3 time complexity

Time complexity: O(n^(n+1)) because in the worst case we can search n + 1 level in depth (worst case the perfect squares are made up all by 1s) from 0 and the tree can thus contains up to n^(n+1) nodes (n^0 + n^1 + n^2 + ... + n^(n-1) + n^n).

Space complexity: O(n^n) because of the queue used to store each level we are iterating through.

Qns 4: You are a renowned thief who has recently switched from stealing precious metals to stealing cakes because of the insane profit margins. You end up hitting the jackpot, breaking into the world’s largest privately owned stock of cakes — the vault of the Queen of England.

While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.

Each type of cake has a weight and a value, stored in objects of a CakeType class:

Each type of cake has a weight and a value, stored in objects of a CakeType class:

public class CakeType {
    final int weight;
    final int value;
    public CakeType(int weight, int value) {
        this.weight = weight;
        this.value  = value;
    }
}

You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.

Write a method maxDuffelBagValue() that takes an array of cake type objects and a weight capacity, and returns the maximum monetary value the duffel bag can hold. Weights and values may be any non-negative integer.

Cracking the Coding Interview — Practice Question

Qns 1: Leet code 70 Climbing stairs. You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Similar to coin change 2.

Qns 2: Robots in a grid: A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

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?

Extension 1 (Leet Code 63): Certain cells are marked off-boundary

Extension 2 (Leet Code 980):

On a 2-dimensional grid, there are 4 types of squares:

• 1 represents the starting square. There is exactly one starting square.
• 2 represents the ending square. There is exactly one ending square.
• 0 represents empty squares we can walk over.
• -1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Qns 2: Power Set -> Write a set to return all possible subset (Leet Code 78)

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Note that the solution below is wrong. In the solution below, List<> seems to be shared across different recursion functions. Even though in line 26, i appear to be modifying just duplicate list but i am actually modifying the original list. This is because, previously in line 21, i am adding the d from list. d is referring to the original list and we are directly modifying it.

WRONG SOLUTION

At every recursion call:

1. Add yourself
2. Add yourself to all existing lists
3. Add all existing lists

class Solution {
    List<List<Integer>> result;
    public List<List<Integer>> subsets(int[] nums) {
        result = new LinkedList<>();
        result.add(new LinkedList<>());
        traverse(result, nums, 0);

        return result;
    }

    public void traverse(List<List<Integer>> result, int[] nums, int index){
        if(index==nums.length){
            return;
        }
        int curr = nums[index];
        
        // Make a copy of all existing lists
        // Add curr to the copy list
        List<List<Integer>> copyList = new LinkedList<>();
        for(List<Integer> r: result){
            List<Integer> copy = new LinkedList<>();
            for(Integer i: r){
                copy.add(i);
            }
            copy.add(curr);
            copyList.add(copy);
        }

        // Add to result
        for(List<Integer> c: copyList){
            result.add(c);
        }

        traverse(result, nums, index+1);
    }
}

Subsets II Leetcode 90

If nums contains non distinct integers, can have duplicates.

class Solution {
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        result.add(new LinkedList<>());
        traverse(result, nums, 0);

        // The only difference here....remove duplicates
        List<List<Integer>> returnResult = new LinkedList<>();
        for(List<Integer> r: result){
            Collections.sort(r); // sorting is a good technique to compare lists without ordering
            if(!returnResult.contains(r)){
                returnResult.add(r);
            }
        }
        return returnResult;
    }

    // Same as before
    public void traverse(List<List<Integer>> result, int[] nums, int index){
        if(index==nums.length){
            return;
        }
        int curr = nums[index];
        
        // Make a copy of all existing lists
        // Add curr to the copy list
        List<List<Integer>> copyList = new LinkedList<>();
        for(List<Integer> r: result){
            List<Integer> copy = new LinkedList<>();
            for(Integer i: r){
                copy.add(i);
            }
            copy.add(curr);
            copyList.add(copy);
        }

        // Add to result
        for(List<Integer> c: copyList){
            result.add(c);      
        }

        traverse(result, nums, index+1);
    }
}

Qns 3: Longest Increasing subsequence -> Can be non contiguous

O(N²) Solution.

How can we have a O(nlogn) solution?

Solution 2: Greedy with Binary Search

• Let’s construct the idea from following example.
• Consider the example nums = [2, 6, 8, 3, 4, 5, 1], let's try to build the increasing subsequences starting with an empty one: sub1 = [].

1. Let pick the first element, sub1 = [2].
2. 6 is greater than previous number, sub1 = [2, 6]
3. 8 is greater than previous number, sub1 = [2, 6, 8]
4. 3 is less than previous number, we can't extend the subsequence sub1, but we must keep 3 because in the future there may have the longest subsequence start with [2, 3], sub1 = [2, 6, 8], sub2 = [2, 3].
5. With 4, we can't extend sub1, but we can extend sub2, so sub1 = [2, 6, 8], sub2 = [2, 3, 4].
6. With 5, we can't extend sub1, but we can extend sub2, so sub1 = [2, 6, 8], sub2 = [2, 3, 4, 5].
7. With 1, we can extend neither sub1 nor sub2, but we need to keep 1, so sub1 = [2, 6, 8], sub2 = [2, 3, 4, 5], sub3 = [1].
8. Finally, length of longest increase subsequence = len(sub2) = 4.

• In the above steps, we need to keep different sub arrays (sub1, sub2..., subk) which causes poor performance. But we notice that we can just keep one sub array, when new number x is not greater than the last element of the subsequence sub, we do binary search to find the smallest element >= x in sub, and replace with number x.
• Let’s run that example nums = [2, 6, 8, 3, 4, 5, 1] again:

1. Let pick the first element, sub = [2].
2. 6 is greater than previous number, sub = [2, 6]
3. 8 is greater than previous number, sub = [2, 6, 8]
4. 3 is less than previous number, so we can't extend the subsequence sub. We need to find the smallest number >= 3 in sub, it's 6. Then we overwrite it, now sub = [2, 3, 8].
5. 4 is less than previous number, so we can't extend the subsequence sub. We overwrite 8 by 4, so sub = [2, 3, 4].
6. 5 is greater than previous number, sub = [2, 3, 4, 5].
7. 1 is less than previous number, so we can't extend the subsequence sub. We overwrite 2 by 1, so sub = [1, 3, 4, 5].
8. Finally, length of longest increase subsequence = len(sub) = 4.

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> temp = new LinkedList<>();
      
        for(int i=0; i<nums.length; i++){
            if(temp.isEmpty() || nums[i]>temp.get(temp.size()-1)){
                temp.add(nums[i]);
            } else {
                // do binary search and replace the smallest num that is 
                // larger than the current nums[i]
                int target = 0; 
                int high = temp.size()-1;
                int low = 0;
                while(low<=high){
                    int mid = (low+high)/2;
                    if (temp.get(mid) < nums[i]){
                        low = mid+1;
                    } else {
                        high = mid-1;
                        target = mid;
                    }
                }

                temp.set(target, nums[i]);
            }
        }

        return temp.size();
    }
}

Extension Leetcode 673

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Solution taken from leet code discussion

Need to make sure that the two if statements are not swapped. This is because if we swapped them both, then the program will enter both if loops.

Qns 4: Minimum path Sum

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.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row_size = grid.size();
        int column_size = grid[0].size();
        vector<vector<int>> visited(row_size, vector<int>(column_size, -1));

        return traverse(grid, 0, 0, visited);
    }
    
    int traverse(vector<vector<int>>& grid, int row, int col, vector<vector<int>>& visited) {
        cout << row << " " << col << endl;
         if (row >= grid.size() || row < 0 || col < 0 || col >= grid[0].size()) {
            return numeric_limits<int>::max();
        }

        if (visited[row][col] != -1) {
            return visited[row][col];
        }

        if (row == grid.size() - 1 && col == grid[0].size() - 1) {
            // Reached the end
            return visited[row][col] = grid[row][col];
        }

        int right = traverse(grid, row, col + 1, visited);
        int down = traverse(grid, row + 1, col, visited);

        return visited[row][col] = min(right, down) + grid[row][col];
    }
};

Leetcode 1262. Greatest Sum Divisible by Three

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

• dp[i,r] where r is the remainder and i is the end index of the number we are going to look at.
• We always start from index 0 and hence i is the end index.
• dp[i,r] will contain the max sum that gives the remainder r when we iterate from 0..i (inclusive).
• At every point of iterating through the num array, we have 2 choices: Do we include the current value or not?

• If we choose to include the current value, then we will have to calculate its’ remainder.
• To understand the equation better (Look at the comments below in my last appended code snippet).

=> dp[i,r]=max(A[i]+dp[i-1, (r-A[i])%3], dp[i-1, r])
Even though it was written to be A[i], i think it should not be A[i].

Leetcode discussion solution below:

Comments

(The answer i derived from the above explanation) => Look at this

Alternative solution (Found this in 2023, much simpler than above)

https://www.youtube.com/watch?v=u_2kOwmJQW4&ab_channel=Joey%27sTech

class Solution {
    public int maxSumDivThree(int[] nums) {
        int dp1[][] = new int[3][nums.length];
        dp1[nums[0]%3][0] = nums[0];

        for(int i=1;i<nums.length;i++)
        {

            int sumWhenAddedToCurrentSumWithRemainder1 = nums[i] + dp1[0][i-1];
            int sumWhenAddedToCurrentSumWithRemainder2 = nums[i] + dp1[1][i-1];
            int sumWhenAddedToCurrentSumWithRemainder3 = nums[i] + dp1[2][i-1];

            int remainder1 = (sumWhenAddedToCurrentSumWithRemainder1)%3; 
            int remainder2 = (sumWhenAddedToCurrentSumWithRemainder2)%3;
            int remainder3 = (sumWhenAddedToCurrentSumWithRemainder3)%3;

            dp1[remainder1][i] = Math.max(dp1[remainder1][i], sumWhenAddedToCurrentSumWithRemainder1); // For the new remainder, 
            dp1[remainder2][i] = Math.max(dp1[remainder2][i], sumWhenAddedToCurrentSumWithRemainder2);
            dp1[remainder3][i] = Math.max(dp1[remainder3][i], sumWhenAddedToCurrentSumWithRemainder3);

            // For all remainders, take the max
            dp1[0][i] = Math.max(dp1[0][i-1],dp1[0][i]);
            dp1[1][i] = Math.max(dp1[1][i-1],dp1[1][i]);
            dp1[2][i] = Math.max(dp1[2][i-1],dp1[2][i]);
        }
    
        return dp1[0][nums.length-1];
    }
}

A question not found in Leet Code

Given a dictionary of words, each word has a positive score. Given a string, cut it to exactly K (K > 0) words and all of them must be found in the dictionary, and the word segmentation score is the sum of the K segmented word’s scores.

Return the max words segmentation score. If it is impossible, return -1.

Example 1:
Input:
[{“abc”, 1}, {“bcd”, 2}, {“f”, 7}], “abcbcdf”, 3
Output:
10 (segment “abcbcdf” to “abc”, “bcd”, “f”)

Recursion Solution

DP Solution -> Not 100% sure that it is correct

801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.

Leet Code Solution:

Line 12: swap at i-1 and i

Line 13: Don’t swap at i-1 and i

Line 17: Swap at i but don’t swap at i-1

Line 18: Swap at i-1 but don’t swap at i.

Leet Code 221. Maximal Square

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

Hmmm hard to think that this is a dynamic programming question.

At every point, we just try to find out if the current point can be the top left corner of a square.

class Solution {
    public int maximalSquare(char[][] matrix) {
        int dp[][] = new int[matrix.length][matrix[0].length];
        int side = 0;
        for(int i=matrix.length-1; i>=0; i--){
            for(int j=matrix[0].length-1; j>=0; j--){
                if(matrix[i][j] == '1'){
                    dp[i][j] = 1; // if current value is 1, the minimum square side length is 1
                    // check right, down, diagonal right..see if this square can be expanded...
                    if(i+1<matrix.length && j+1<matrix[0].length){
                        dp[i][j] = Math.max(dp[i][j], Math.min(Math.min(dp[i+1][j], dp[i][j+1]), dp[i+1][j+1]) + 1);
                    }
                    side = Math.max(dp[i][j], side);
                }   
            }
        }
        return side * side;
    }
}

• Time complexity : O(mn). Single pass.
• Space complexity : O(mn). Another matrix of same size is used for d.

Leet Code 84 Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

WRONG SOLUTION: Memory exceeded

Leet Code Discussion Solution:

https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)

We see that at every height[i], we want to compute the max possible rectangle formed. We want to expand from index i the furthest we can to the left and right direction. The stopping condition for the expansion is when we arrive at a height which is smaller than current height[i].

With this in mind, we then make use of 2 arrays indexLeft and indexRight. indexLeft[i] contains the first index on the left which has height < height[i]. The above illustration explains how to get the width of the rectangle. r-l+1.

Leet Code 85 Maximal Rectangle (Similar to Maximal Squares)

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = []
Output: 0

Example 3:

Input: matrix = [["0"]]
Output: 0

Example 4:

Input: matrix = [["1"]]
Output: 1

Example 5:

Input: matrix = [["0","0"]]
Output: 0

This question is similar to the previous question.

We can visualise each row as a histogram of bars. First, for each row, we construct this histogram of bars. The heights of a bar (column) in the histogram is the sum of the numbers in the current row and above for that column. For eg, see the image below.

Then, once we have a histogram for each rows constructed, we will then attempt to find the max rectangle for the histogram at each level. We apply the previous question technique to each row (1 histogram) and the final result would be the max rectangle formed from a histogram.

This function is the same as the previous question

Leet Code 42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

class Solution {
    public int trap(int[] height) {
        int[] maxLeft = new int[height.length];
        maxLeft[0]=0;
        for(int i=1; i<height.length; i++){
            maxLeft[i] = Math.max(height[i-1], maxLeft[i-1]);
        }
        
        int[] maxRight = new int[height.length];
        maxRight[height.length-1]=0;
        for(int i=height.length-2; i>=0; i--){
            maxRight[i] = Math.max(height[i+1], maxRight[i+1]);
        }

        int result = 0;
        for(int i=0; i<height.length; i++){
            int add = Math.min(maxRight[i], maxLeft[i]) - height[i];
            if(add>0){
                result += add;
            }
        }

        return result;
        
    }
}

This is quite hard…everything about leetcode is hard :( …it took me around 2 hours (second time, months after my first try) to come up with this solution.

The idea is to compute the max left and max right and then minus existing height of the bar.

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

N-Queens — LeetCode

Each recursion call is in charge of exploring a different col index. Internally, the function explores different rows with the FOR loop.

We know for sure that when we have reached colIndex == board.length, all the rows have been filled. This is due to the validate function which ensures that a recursion call will not be called on a board that adds Q to the same row repeatedly. We only make new recursion call when Q is added to the next row. Hence, when colIndex == board.length, we know that board.length number of rows has been filled.

Line 56 already checked

See that if we want to know if we can place Q in position (1,1), we will need its’ diagonals to be empty. So, when we are in the i,j position we want to check if the difference in magnitude in x-y direction from this (1,1) position is the same. If it is the same, we know that the current position i,j is in a diagonal position.

x-i == y-j

class Solution {
public:
    vector<vector<string>> result;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> table;
        for(int i=0; i<n; i++){
            string s = "";
            for(int j=0; j<n; j++){
                s = s + ".";
            }
            table.push_back(s);
            cout << s <<endl;
        }
        traverse(n-1, n, table);
        return result;
    }
    // a vector represents a grid
    // an item in a vector represents a row
    void traverse(int currRow, int n, vector<string> &table){
        if(currRow == -1){
            result.push_back(table);
            return;
        }
       
        string str = "";
        for(int col=n-1; col>=0; col--){
            if(validate(table, currRow, col)){
                string currStringRow = table[currRow];
                currStringRow[col] = 'Q';
                table[currRow] = currStringRow;
                traverse(currRow-1, n, table);
                currStringRow[col] = '.';
                table[currRow] = currStringRow;
            }
        }
    }

    bool validate(vector<string> table, int row, int col){
        for(int i=0; i<table.size(); i++){
            for(int j=0; j<table.size(); j++){
                if(table[i][j] == 'Q' && (abs(row-i) == abs(col-j) || col == j)){
                    return false;
                }
            }
        }
        return true;
    }

};

161. One Edit Distance

An edit between two strings is one of the following changes.

1. Add a character
2. Delete a character
3. Change a character

Given two string s1 and s2, find if s1 can be converted to s2 with exactly one edit. Expected time complexity is O(m+n) where m and n are lengths of two strings.

Examples:

Input:  s1 = "geeks", s2 = "geek"
Output: yes
Number of edits is 1
Input:  s1 = "geeks", s2 = "geeks"
Output: no
Number of edits is 0
Input:  s1 = "geaks", s2 = "geeks"
Output: yes
Number of edits is 1
Input:  s1 = "peaks", s2 = "geeks"
Output: no
Number of edits is 2

From a YouTube Channel

We can classify into the different cases as seen in part 1 and then call the corresponding functions.

72. Edit Distance (Differerent from above)

Instead of just checking if they differ by 1 operation, now there can be >1 operations.

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

TIME LIMIT EXCEEDED SOLUTION. The logic is correct but recursion takes too long.

Hence, we use dynamic programming.

class Solution {
public:
    vector<vector<int>> cache;
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if(len1 == 0) return len2;
        if(len2 == 0) return len1;
        
        cache.resize(len1, vector<int>(len2, 0));
        for (auto& row : cache) {
            std::fill(row.begin(), row.end(), -1);
        }
        return compute(word1, word2, 0, 0);
    }

    int compute(string word1, string word2, int index1, int index2){
        if(word1.length() == index1){
            return word2.length() - index2;
        }
        if(word2.length() == index2){
            return word1.length() - index1;
        }
        if(cache[index1][index2] != -1) return cache[index1][index2];

        if(word1[index1] == word2[index2]){
           return cache[index1][index2] = compute(word1, word2, index1+1, index2+1);
        }

        int insert = compute(word1, word2, index1, index2+1);
        int deleteC = compute(word1, word2, index1+1, index2);
        int replace = compute(word1, word2, index1+1, index2+1);

        return cache[index1][index2] = 1 + min(insert, min(deleteC, replace));
    }
};

Leet Code 329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Leet Code 332. Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.
4. One must use all the tickets once and only once.

Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

Whenever each “Node” cannot be represented by a number, we use HashMap instead of an ArrayList.

We use Recursion here.

WRONG SOLUTION 1: Using PriorityQueue

WRONG OUTPUT

WRONG SOLUTION 2: Using stack

Hence, the best way is not to use Stack or Queue but to use Recursion. Using Stack or Queue does not enable us to discard nodes that were previously visited, but not supposed to be in the path.

Check out around 12 minute of this video

Run through of the algorithm on an example:

Each time you see a node, you will add it to the stack. When you find that you have reached a dead end, pop that single last element to the result list. Then, remove that element from the stack and continue.

Then, go on to N and then J. At N->J ticket, we see we have finished. So we pop from the stack.

The answer is in reversed order.

Leet Code 38. Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return the nth term of the count-and-say sequence.

Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

class Solution {
    public String countAndSay(int n) {
        
        if (n==1) return "1";
        if (n < 1) return "";
        String result = "";
        String prev = countAndSay(n-1); 
        return sayIt(prev);
    }

    public String sayIt(String nString){
        
        int count=0;
        char val='0';
        String result = "";
        for(int i=0; i<nString.length(); i++){
            if(i==0 || val == nString.charAt(i)){
                count++;
                val = nString.charAt(i);
            } else {
                result += String.valueOf(count)+val;
                count=1;
                val=nString.charAt(i);
            }
        }
        result += String.valueOf(count)+val;
        
       
        return result;
    }
}

698. Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

416. Partition Equal Subset Sum

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

This question is similar to 0–1 Knapsack problem where you either choose a number or not.

Here, we attempt to form 1 subset which has the sum of SUM_OF_ALL_NUMS_ITEM/2.

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Solution:

This question smells strongly of DP.

class Solution {
    public int rob(int[] nums) {
        int[]dp = new int[nums.length];
        // dp[i] represents max profit when robber reaches i house.
        // not necessarily that the ith house was robbed.

        for(int i=0; i<nums.length; i++){
            if(i-2>=0){
                // rob 2 houses away and current house
                // or rob the previous house
                dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i]);
            } else if (i-1>=0){
                // rob current house or the previous house
                dp[i]=Math.max(dp[i-1], nums[i]);
            } else{
                // edge case where the current house is the first house
                // the robber visits
                dp[i]=nums[i];
            }
        }

        return dp[nums.length-1];
    }
}

Leet Code 213 House Robber II

The question remains the same as above, except that all houses at this place are arranged in a circle.

Solution:

Compute 2 times. We have 2 dps.

(1) The first dp is for when we include the first house. If we are at the last element, we decide whether to add last house value depending on whether first house value was used. If not used, then we can add. If used, then cannot add.

(2) The second dp is when we exclude the first house. Since we exclude it, then we can do the remaining dp method freely.

Then, we compare the two max values obtained.

Leet Code 337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Use a helper function which receives a node and a bool variable as input, and if that variable is false, it returns the maximum amount of money the thief can rob if starting from this node and robbing this node, else returns the maximum amount of money the thief can rob if starting from this node without robbing this node.

// Another attempt
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    HashMap<TreeNode, Integer> skipCache;
    HashMap<TreeNode, Integer> noSkipCache;
    
    public int rob(TreeNode root) {
        skipCache = new HashMap<>();
        noSkipCache = new HashMap<>();
        if(root==null) return 0;
        return Math.max(helper(root, true), helper(root, false));
    }
   
    public int helper(TreeNode root, boolean skipCurr){
        if(root == null) {
            return 0;
        }
        
        if(skipCurr){
            if(skipCache.containsKey(root)) return skipCache.get(root);
            int skipResult = helper(root.left, false) + helper(root.right, false);
            skipCache.put(root, skipResult);
            return skipResult;
        }
        if(noSkipCache.containsKey(root)) return noSkipCache.get(root);
        int skip = helper(root.left, false) + helper(root.right, false);
        int noSkip = helper(root.left, true) + helper(root.right, true) + root.val;
        int maxResult = Math.max(skip, noSkip);
        noSkipCache.put(root, maxResult);
        return maxResult;
    }
}

Leet Code 91 Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "111" can have each of its "1"s be mapped into 'A's to make "AAA", or it could be mapped to "11" and "1" ('K' and 'A' respectively) to make "KA". Note that "06" cannot be mapped into 'F' since "6" is different from "06".

Given a non-empty string num containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0. The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20".
Since there is no character, there are no valid ways to decode this since all digits need to be mapped.

Example 4:

Input: s = "1"
Output: 1

This is similar to climb stairs problem.

TODO:

DECODE WAYS TWO

241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

Solution:

• The key is to know that we do a split at every operator position. This problem is about different ways of slicing the expression string for k times where k is the number of operators. The different ways refers to the order in which they are sliced.

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        regex pattern("[0-9]+");
         
        if(regex_match(expression, pattern)){
            vector<int> sole;
            sole.push_back(stoi(expression));
            return sole;
        }


        vector<int> result;
        for(int i=0; i<expression.length(); i++){
            if(!isdigit(expression[i])){
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i+1));

                if(left.size() == 0 && right.size() == 0) return result;
                if(left.size() == 0) return right;
                if(right.size() == 0) return left;

                for(int l: left){
                    for(int r: right){
                        if(expression[i] == '+'){
                            result.push_back(l+r);
                        } else if (expression[i] == '-'){
                            result.push_back(l-r);
                        } else {
                            result.push_back(l*r);
                        }
                    }
                }
            }
        }
        return result;
    }
};

I don’t want to be ordinary. I want to be extra-ordinary.

93. Restore IP Addresses

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "1111"
Output: ["1.1.1.1"]

Example 4:

Input: s = "010010"
Output: ["0.10.0.10","0.100.1.0"]

(Below is a related Qns but not recursion)

class Solution {
public:
    vector<string> result;
    vector<string> restoreIpAddresses(string s) {
        traverse(s, "", 0);
        return result;
    }
    void traverse(string remainder, string newString, int dots){
       
        if(dots == 4){
            if(remainder.length() == 0){
                result.push_back(newString.substr(1)); // remove the first 0
            }
            return;
        }

        for(int i=1; i<=3; i++){
            if(i<=remainder.length()){
                string newInt = remainder.substr(0, i);
                if(!startsWith(newInt, "0") && stoi(newInt) >= 0 && stoi(newInt) <= 255){
                    traverse(remainder.substr(i), newString+"."+newInt, dots+1);
                }
            }
        }

    }

    bool startsWith(const std::string& str, const std::string& prefix) {
        if (str.length() < prefix.length()) {
            return false;
        }

        return str.substr(0, prefix.length()) == prefix && str.length() > 1;
    }
    
};

468. Validate IP Address

Given a string IP, return "IPv4" if IP is a valid IPv4 address, "IPv6" if IP is a valid IPv6 address or "Neither" if IP is not a correct IP of any type.

A valid IPv4 address is an IP in the form "x1.x2.x3.x4" where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, "192.168.1.1" and "192.168.1.0" are valid IPv4 addresses but "192.168.01.1", while "192.168.1.00" and "192.168@1.1" are invalid IPv4 addresses.

A valid IPv6 address is an IP in the form "x1:x2:x3:x4:x5:x6:x7:x8" where:

• 1 <= xi.length <= 4
• xi is a hexadecimal string which may contain digits, lower-case English letter ('a' to 'f') and upper-case English letters ('A' to 'F').
• Leading zeros are allowed in xi.

For example, “2001:0db8:85a3:0000:0000:8a2e:0370:7334" and "2001:db8:85a3:0:0:8A2E:0370:7334" are valid IPv6 addresses, while "2001:0db8:85a3::8A2E:037j:7334" and "02001:0db8:85a3:0000:0000:8a2e:0370:7334" are invalid IPv6 addresses.

Copied

WRONG ORIGINAL SOLN

943. Find the Shortest Superstring

https://leetcode.com/problems/find-the-shortest-superstring/

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

Example 1:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

TODO

1444. Number of Ways of Cutting a Pizza

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts.

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10⁹ + 7.

class Solution {
    public int ways(String[] pizza, int k) {
        int rows = pizza.length;
        int cols = pizza[0].length();
        int[][] apples = new int[rows+1][cols+1];
        int dp[][][] = new int[k][rows][cols];
        for(int row=rows-1; row>=0; row--){
            for(int col=cols-1; col>=0; col--){
                apples[row][col] = (pizza[row].charAt(col) == 'A' ? 1 : 0) + apples[row][col+1] + apples[row+1][col] - apples[row+1][col+1];
                dp[0][row][col] = apples[row][col] > 0 ? 1: 0;
                /*
                 * The base case of the DP is remain = 0 when one does not 
need to make any more cuts. If pizza[row..rows-1][col..cols-1] contains at 
least one apple, then dp[0][row][col] = 1 – there is one way to make no cuts 
and give the piece to the last person. Otherwise, 
pizza[row..rows-1][col..cols-1] contains no apples, and there are no ways to 
give the piece to the person, thus dp[0][row][col] = 0.
                 */
            }
        }

        int mod = 1000000007;
        for(int remain=1; remain<k; remain++){
            for(int row=0; row<rows; row++){
                for(int col=0; col<cols; col++){
                    for(int nextRow = row+1; nextRow<rows; nextRow++){
                        // Can cut upper part
                        if(apples[row][col] - apples[nextRow][col]>0){
                            dp[remain][row][col] += dp[remain-1][nextRow][col];
                            dp[remain][row][col] %= mod;
                        }
                    }

                    // Can cut left part
                    for(int nextCol = col+1; nextCol<cols; nextCol++){
                        if(apples[row][col] - apples[row][nextCol] > 0){
                            dp[remain][row][col]+=dp[remain-1][row][nextCol];
                            dp[remain][row][col]%=mod;
                        }
                    }
                }
            }
        }

        return dp[k-1][0][0];

    }
}

We visualise the problem as cutting top or left. Each time, we are left with a grid in the right bottom.

We create apples [] to store the number of apples in a grid. For example, apples[i][j] represents the total number of apples in the grid to the right bottom.

dp[remain][row][col] represents the number of ways to cut the rectangular part pizza[row..rows-1][col..cols-1] with remain cuts.

Maximum absolute sum of any subarray

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

• If x is a negative integer, then abs(x) = -x.
• If x is a non-negative integer, then abs(x) = x.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.

class Solution {
    public int maxAbsoluteSum(int[] A) {
        int s = 0, min = 0, max = 0;
        for (int a: A) {
            s += a;
            min = Math.min(min, s);
            max = Math.max(max, s);
        }
        return max - min;
    }
} // Prefix method??

// Video method

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int minVal = 10000;
        int maxVal = -10000;

        vector<int> minDp; // i: Minimum val inclusive of nums[i]
        vector<int> maxDp; 
        minDp.push_back(0);
        maxDp.push_back(0);
        for(int i=0; i<nums.size(); i++){
            int currMin = min(minDp[i] + nums[i], nums[i]);
            minDp.push_back(currMin);
            int currMax = max(maxDp[i] + nums[i], nums[i]);
            maxDp.push_back(currMax);
            minVal = min(currMin, minVal);
            maxVal = max(currMax, maxVal);
        }

        return max(abs(minVal), abs(maxVal));
    }
};

416. Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

class Solution {
    Boolean [][]memo;
    public boolean canPartition(int[] nums) {
       
        int sum=0;
        for(int i=0; i<nums.length; i++){
            sum+=nums[i];
        }

        if(sum%2==1) return false;
        int half = sum/2;
        memo = new Boolean[nums.length+1][half+1];
        return dfs(nums, 0, half);

    }

    public boolean dfs(int[] nums, int index, int sum){
        if(sum==0) return true;
        if(index>nums.length-1 ||sum < 0) return false;
        if(memo[index][sum] != null) return memo[index][sum];

        return memo[index][sum] = dfs(nums, index+1, sum-nums[index]) || dfs(nums, index+1, sum);

    }
}

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> memo;

    bool canPartition(std::vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1)
            return false;

        int half = sum / 2;
        memo.resize(nums.size() + 1, std::vector<int>(half + 1, INT_MIN)); // set to INT_MIN so we differentiate btw false and INT_MIN

        return dfs(nums, 0, half);
    }

    bool dfs(std::vector<int>& nums, int index, int sum) {
        if (sum == 0)
            return true;
        if (index > nums.size() - 1 || sum < 0)
            return false;
        if (memo[index][sum] != INT_MIN)
            return memo[index][sum];

        return memo[index][sum] = dfs(nums, index + 1, sum - nums[index]) || dfs(nums, index + 1, sum);
    }
};

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {

        HashSet<Pair<Integer, Integer>> visited = new HashSet<>();

        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair<Integer, Integer>(0, 0));

        while(!queue.isEmpty()){
            Pair<Integer, Integer> newPair = queue.poll();
            if (visited.contains(newPair)) continue;
            visited.add(newPair);
            if(matrix[newPair.getKey()][newPair.getValue()] == target) return true;
            if(matrix[newPair.getKey()][newPair.getValue()] < target) {
                // Move right and bottom
                if(newPair.getValue()+1 < matrix[0].length){
                    queue.add(new Pair<Integer, Integer>(newPair.getKey(), newPair.getValue()+1));
                } 
                if (newPair.getKey()+1 < matrix.length){
                    queue.add(new Pair<Integer, Integer>(newPair.getKey()+1, newPair.getValue()));
                }
            }
        }

        return false;
    }
}

Fails the last test case for time limit…but the logic is correct…

I think the time complexity is O(m+n).

Following is from leetcode

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // start our "pointer" in the bottom-left
        int row = matrix.length-1;
        int col = 0;

        while (row >= 0 && col < matrix[0].length) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else { // found it
                return true;
            }
        }

        return false;
    }
}

651. 4 Keys Keyboard

Imagine you have a special keyboard with the following keys:

• A: Print one 'A' on the screen.
• Ctrl-A: Select the whole screen.
• Ctrl-C: Copy selection to buffer.
• Ctrl-V: Print buffer on screen appending it after what has already been printed.

Given an integer n, return the maximum number of 'A' you can print on the screen with at most n presses on the keys.

Example 1:

Input: n = 3
Output: 3
Explanation: We can at most get 3 A's on screen by pressing the following key sequence:
A, A, A

Example 2:

Input: n = 7
Output: 9
Explanation: We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

// Copied from Leetcode's submission from another user
// Assume dp[i] is the current best A list we can get
class Solution {
    public int maxA(int N) {
        int[] dp = new int[N+1];
        for (int i=1; i<=N; i++) {
            if (i<=5) {
                dp[i] = i;
            } else {
                // There are following cases:
                // Type A, which is just dp[i-1]+1
                // Select, copy and paste previous A list generated by three steps before, which is dp[i-3]*2
                // Select, copy, paste, paste. So it is actually pasting dp[i-4] which is the list four steps before and we times three here
                // Select, copy, paste, paste, paste. So it is actually pasting dp[i-5] which is the list five steps before and we times four here
                // We will not have the case of pasting more than 3 times because we can select, copy and paste again to paste with longer A list.
                // Select, copy, paste, paste, paste, paste ----smaller than----> Select, copy, paste, Select, copy, paste  
                dp[i] = Math.max(dp[i-1]+1, Math.max(dp[i-3]*2, Math.max(dp[i-4]*3, dp[i-5]*4)));
            }
        }
        return dp[N];
    }
}

(The one above is easier to understand)

Editorial Solution

Let’s make the first observation: once we have used the copy operation, there is no need to print a single letter A anymore because we can paste the buffer instead. Thus we press a single letter A only at the beginning.

Let’s say that we have used up m presses so far and have obtained a string of length l.

• After these m presses, one can copy-paste the text by pressing Ctrl+A, Ctrl+C, and Ctrl+V. It costs three key presses and doubles the length, so we have a length of 2l with a total of m+3 presses.
• We can press Ctrl+V again, and the length will be 3l with m+4 total presses.
• We can continue this pattern — if we press Ctrl+V 3 times, we have a length of 4l with m+5 total presses. In general, we can have a length of k⋅l with m+k+1 presses, where k≥2.

Here we use the answer to the smaller problem (m) to get the answer to the bigger ones (m+3, m+4, m+5). It alludes to dynamic programming. But before jumping into DP, we make one more observation.

There is no need to press Ctrl+V more than four times in a row. Let the current length be l. Assume we press Ctrl+A, Ctrl+C, then Ctrl+V 5 times. After this sequence, the length becomes 6l, and the buffer contains l characters.

However, if we press Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V instead, the length also becomes 6l, but the buffer contains 2l characters now, which is not worse than in the former case. In both scenarios, we used seven presses.

Now we formulate the DP. Let dp[i] be the answer when we can do i presses.

We can initialize base cases as dp[i]=i (print the letter A i times, this is the first observation we made).

Now we want to describe transitions (the recurrence relation). As stated above, it is inefficient to press Ctrl+V 5 times or more in a row. This means we will press Ctrl+A, Ctrl+C, and then Ctrl+V up to four times:

• dp[i+3]=2⋅dp[i]
• dp[i+4]=3⋅dp[i]
• dp[i+5]=4⋅dp[i]
• dp[i+6]=5⋅dp[i]

In general, we have dp[j]=(j−i−1)⋅dp[i], where i+3≤j≤i+6. We want to take the maximum value, and this gives us our recurrence relation.

class Solution {
    public int maxA(int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
        }
        for (int i = 0; i <= n - 3; i++) {
            for (int j = i + 3; j <= Math.min(n, i + 6); j++) {
                dp[j] = Math.max(dp[j], (j - i - 1) * dp[i]);
            }
        }
        return dp[n];
    }
}

Algorithm

1. Create an array dp of length n + 1. Initialize dp[i]=i
2. Iterate with a variable iii until n−3

• For each j from i+3 to min⁡(n,i+6) update (if greater) dp[j] with (j−i−1)⋅dp[i].

3. Return dp[n]

Complexity Analysis

• Time complexity: O(n)

There are O(n)states in the DP. We visit each state once and loop up to 4 times, which costs O(1) at each state.

• Space complexity: O(n)

We store all O(n) states in our dp array.

My wrong attempt

class Solution {
    public int maxA(int n){
        return helper(n, 0);
    }
    public int helper(int n, int numOfAs){
        if(n<=0) return numOfAs;
        int copyPaste = 0;
        if(n>=3){
            copyPaste = helper(n-3, numOfAs*2);
        }
        int addA = 0;
        if(n>=1){
            addA = helper(n-1, numOfAs+1);
        }  
        return Math.max(copyPaste, addA);
    }
}

// Does not work for when n=7. The code produces 8 as output, but 9 is the expected.

343. Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

From neetcode youtube channel

From the given number n, we want to see if we can multiply any 2 numbers that sums up to n and get the maximum product.

class Solution {
    HashMap<Integer, Integer> dp;
    public int integerBreak(int n) {
        dp = new HashMap<>();
        dp.put(1,1);
        return dfs(n, n);
    }

    public int dfs(int num, int n){
        if(dp.containsKey(num)) return dp.get(num);

        int res = num == n? 0 : num; // don't break it further -> Initialise to num
        for(int i=1; i<num; i++){
            int val = dfs(i, n) * dfs(num-i, n);
            res = Math.max(res, val);
        }
        dp.put(num, res);
        return res;
    }
}

46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

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

Example 3:

Input: nums = [1]
Output: [[1]]

class Solution {
    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> result = permHelper(nums, 0);

        return result;
    }

    public List<List<Integer>> permHelper(int[] nums, int k){
        if(k>=nums.length-1){
            List<List<Integer>> curr = new LinkedList<>();
            curr.add(Arrays.asList(nums[k]));
            return curr;
        }

        int curr = nums[k];
        List<List<Integer>> remaining = permHelper(nums, k+1);
        List<List<Integer>>  result = new LinkedList<>();
        for(List<Integer> r: remaining){
            // put curr in any random position
            for(int i=0; i<=r.size(); i++){
                List<Integer> temp = new LinkedList<>();
                for(int j=0; j<i; j++){
                    temp.add(r.get(j));
                }
                temp.add(curr);
                for(int j=i; j<r.size(); j++){
                    temp.add(r.get(j));
                }
                result.add(temp);
            }
        }

        return result;
        
    }


}

50. Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

class Solution {
    public double myPow(double x, int n) {
        // Check if x is within the given constraints
        if (x < -10000 || x > 10000) {
            return 0;
        }
        
        if (n==0) return 1;
        if (n < 0) {
            n = -n;
            x = 1 / x;
        }
        // If n is even, recursively compute the square of x^(n/2)...helps save time
        if (n % 2 == 0) {
            return myPow(x * x, n / 2);
        } 
        return x * myPow(x, n-1);
    }
}

// My original solution which failed the tests
class Solution {
    public double myPow(double x, int n) {
       
        if (n==0) return 1;
        if (n < 0) {
            return 1 / myPow(x, Math.abs(n));
        }
      
        return x * myPow(x, n-1);
    }
}

The end :-)