# 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.

## Extension

For Fibonacci qns, during interviews they like to ask you about the time complexity. The ans is O(2^n).

The best solution is to use iteration so you can deal with large numbers

`public static void fib(int n){`

int one = 0;

int two = 1;

for(int i=2; i<=n; i++){

int temp = two;

two += one;

one = two;

}

return two;

}

// if you have a restriction that you cannot use temp

public static int fib(int n){

int one = 0;

int two = 1;

for(int i=2; i<=n; i++){

two += one;

one = two - one;

}

return n<=0 ? 0 : two;

}

## 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

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 objectoas a parameter to be stored in the returned list.

Return Value:This method returns animmutable listcontaining 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]

- 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]]
- Then, the caller function will receive this returned list.
- 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]]
- 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 (same as above)

Given a collection of numbers, `nums`

, that might contain duplicates, return *all possible unique permutations **in any order**.*

`class Solution {`

List<List<Integer>> result;

public List<List<Integer>> permuteUnique(int[] nums) {

result = new LinkedList<>();

helper(nums, 0, new LinkedList<>());

return result;

}

public void helper(int[] nums, int start, List<Integer> curr){

if(start == nums.length){

if(!result.contains(curr)){

result.add(curr);

}

return;

}

int currNum = nums[start];

for(int positionToInsert = 0; positionToInsert<=curr.size(); positionToInsert++){

// create new copies of curr

// send to helper

List<Integer> copy = copyList(curr);

copy.add(positionToInsert, currNum);

helper(nums, start+1, copy);

}

}

public List<Integer> copyList(List<Integer> curr){

List<Integer> result = new LinkedList<>();

for(int c: curr){

result.add(c);

}

return result;

}

}

## 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.

- The first char of the string must always be a
**(, hence i start by initialising the base string to only contain (.** - If the number of
**(**is smaller than the number of**),**only then we can add**)** - 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.

## 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]]

## 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]

]

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

}

}

}

}

## 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;

}

}

}

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…

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

s) 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.

At every recursion call:

- Add yourself
- Add yourself to all existing lists
- 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 = []`

.

- Let pick the first element,
`sub1 = [2]`

. `6`

is greater than previous number,`sub1 = [2, 6]`

`8`

is greater than previous number,`sub1 = [2, 6, 8]`

`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]`

.- With
`4`

, we can't extend`sub1`

, but we can extend`sub2`

, so`sub1 = [2, 6, 8], sub2 = [2, 3, 4]`

. - With
`5`

, we can't extend`sub1`

, but we can extend`sub2`

, so`sub1 = [2, 6, 8], sub2 = [2, 3, 4, 5]`

. - 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]`

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

- Let pick the first element,
`sub = [2]`

. `6`

is greater than previous number,`sub = [2, 6]`

`8`

is greater than previous number,`sub = [2, 6, 8]`

`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]`

.`4`

is less than previous number, so we can't extend the subsequence`sub`

. We overwrite`8`

by`4`

, so`sub = [2, 3, 4]`

.`5`

is greater than previous number,`sub = [2, 3, 4, 5]`

.`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]`

.- 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.

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

`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];

}

}

// simplier...

class Solution {

public int maxSumDivThree(int[] nums) {

int[] dp = new int[3];

for(int n: nums){

int sum1 = n+dp[0];

int sum2 = n+dp[1];

int sum3 = n+dp[2];

int remainder1 = (sum1)%3;

int remainder2 = (sum2)%3;

int remainder3 = (sum3)%3;

dp[remainder1]=Math.max(dp[remainder1], sum1);

dp[remainder2]=Math.max(dp[remainder2], sum2);

dp[remainder3]=Math.max(dp[remainder3], sum3);

}

return dp[0];

}

}

# 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”, 3Output:10 (segment “abcbcdf” to “abc”, “bcd”, “f”)

# 139. Word Break

Given a string `s`

and a dictionary of strings `wordDict`

, return `true`

if `s`

can be segmented into a space-separated sequence of one or more dictionary words.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**Example 1:**

`Input: s = "leetcode", wordDict = ["leet","code"]`

Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

**Example 2:**

`Input: s = "applepenapple", wordDict = ["apple","pen"]`

Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".

Note that you are allowed to reuse a dictionary word.

**Example 3:**

`Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]`

Output: false

`class Solution {`

HashMap<String, Boolean> map;

public boolean wordBreak(String s, List<String> wordDict) {

map = new HashMap<>();

return helper(s, wordDict);

}

public boolean helper(String s, List<String> wordDict){

if(map.containsKey(s)) return map.get(s);

if(s.isEmpty()) return true;

for(String word: wordDict){

if(s.startsWith(word)) {

Boolean val = helper(s.substring(word.length()), wordDict);

map.put(s, val);

if(val == true){

return true;

}

}

}

map.put(s, false);

return false;

}

}

# 140. Word Break II

Given a string `s`

and a dictionary of strings `wordDict`

, add spaces in `s`

to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in **any order**.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**Example 1:**

`Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]`

Output: ["cats and dog","cat sand dog"]

**Example 2:**

`Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]`

Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

Explanation: Note that you are allowed to reuse a dictionary word.

**Example 3:**

`Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]`

Output: []

`class Solution {`

List<String> result;

public List<String> wordBreak(String s, List<String> wordDict) {

result = new LinkedList<>();

helper(s, wordDict, "");

return result;

}

public void helper(String s, List<String> wordDict, String curr){

if(s.length() == 0){

result.add(curr.trim()); // remove leading space

return;

}

for(String word: wordDict){

if(s.startsWith(word)){

helper(s.substring(word.length()), wordDict, curr + " " + word);

}

}

}

}

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

`class Solution {`

public int minSwap(int[] nums1, int[] nums2) {

int[] noSwap = new int[nums1.length];

int[] swap = new int[nums1.length];

swap[0]=1;

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

swap[i]=noSwap[i]=nums1.length;

if(nums1[i-1]<nums1[i] && nums2[i-1]<nums2[i]){

// perform swaps in i-1 and 1 to maintain order

swap[i]=swap[i-1]+1;

noSwap[i]=noSwap[i-1]; // don't swap at all

}

// swap at either i-1 or 1 but not both

if(nums1[i-1]<nums2[i] && nums2[i-1]<nums1[i]){

swap[i]=Math.min(noSwap[i-1]+1, swap[i]);

noSwap[i]=Math.min(swap[i-1], noSwap[i]);

}

}

return Math.min(noSwap[nums1.length-1], swap[nums1.length-1]);

}

}

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.

Set first element to be 0 and 1.

All other places could be initialised to value of length of A or B, in this case 4.

Next, we look at {3,2}. We know that we can don’t perform any swap since 3 is already bigger than 1. Hence, the value at the second column of no swap remains as 0.

swap[i] = swap[i-1]+1.

Then, compare diagonally.

0 is less than 1, so keep it.

0+1=1 which is smaller than 2 -> Update value to be the lower value 1.

# 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 rows = matrix.length;

int cols = matrix[0].length;

int[][] dp = new int[rows][cols];

int side = 0;

for(int i=rows-1; i>=0; i--){

for(int j=cols-1; j>=0; j--){

if(matrix[i][j]=='1'){

dp[i][j]=1;

if((i+1)<rows && (j+1)<cols){

// check down, right, diagonal

dp[i][j]+=Math.min(dp[i][j+1], Math.min(dp[i+1][j], dp[i+1][j+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

## Leet Code Discussion Solution:

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.

# 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"]]

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.

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.

- Add a character
- Delete a character
- 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 1Input: s1 = "geeks", s2 = "geeks"

Output: no

Number of edits is 0Input: s1 = "geaks", s2 = "geeks"

Output: yes

Number of edits is 1Input: s1 = "peaks", s2 = "geeks"

Output: no

Number of edits is 2

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

`// simplified solution`

class Solution {

public boolean isOneEditDistance(String s, String t) {

if(Math.abs(s.length()-t.length()) > 1) return false;

if(s.length() == t.length()){

int diff = 0;

for(int i=0; i<s.length(); i++){

if(s.charAt(i)!=t.charAt(i)){

diff++;

}

}

return diff == 1;

}

String shorter = t.length()<s.length()?t:s;

String longer = t.length()<s.length()?s:t;

for(int i=0; i<longer.length(); i++){

String newString = longer.substring(0, i)+longer.substring(i+1);

if(newString.equals(shorter)){

return true;

}

}

return false;

}

}

# 72. Edit Distance (Different 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')

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.

`class Solution {`

int[][] dp;

public int longestIncreasingPath(int[][] matrix) {

dp = new int[matrix.length][matrix[0].length];

int max = Integer.MIN_VALUE;

for(int i=0; i<matrix.length; i++){

for(int j=0; j<matrix[0].length; j++){

max = Math.max(max, search(i, j, matrix, -1));

}

}

return max;

}

public int search(int i, int j, int[][] matrix, int prev){

if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length || matrix[i][j] <= prev){

return 0;

}

if (dp[i][j] != 0) return dp[i][j];

int one = search(i-1, j, matrix, matrix[i][j]);

int two = search(i+1, j, matrix, matrix[i][j]);

int three = search(i, j-1, matrix, matrix[i][j]);

int four = search(i, j+1, matrix, matrix[i][j]);

return dp[i][j] = Math.max(one, Math.max(two, Math.max(three, four))) + 1;

}

}

// since we have dp, we don't need visited checks

# 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:**

- 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"]`

. - All airports are represented by three capital letters (IATA code).
- You may assume all tickets form at least one valid itinerary.
**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 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.

The above solution exceeded the time limit. Use the one below instead.

`class Solution {`

HashMap<String, Boolean> map;

public boolean canPartitionKSubsets(int[] nums, int k) {

map = new HashMap<>();

int sum = 0;

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

sum+=nums[i];

}

if(k==0 || sum%k != 0) return false;

char[] taken = new char[nums.length];

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

taken[i] = '0';

}

return tryout(nums, k, 0, 0, sum/k, taken);

}

boolean tryout(int[]nums, int bucketLeft, int startIndex, int currentSum, int sum, char[] taken){

String takenString = new String(taken);

if(map.containsKey(takenString)) return map.get(takenString);

if(bucketLeft == 0) return true;// can also be bucketLeft==1

if(currentSum==sum){

Boolean v = tryout(nums, bucketLeft-1, 0, 0,sum, taken);

map.put(takenString, v);

return v;

}

// No need to proceed further.

if (currentSum > sum) {

return false;

}

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

if(taken[i]=='0' && currentSum+nums[i] <= sum){

taken[i]='1';

if(tryout(nums, bucketLeft, startIndex+1, currentSum+nums[i], sum, taken)){

map.put(takenString, true);

return true;

}

taken[i]='0';

}

}

map.put(takenString, false);

return false;

}

}

# 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.

`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);

}

}

# 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.

`class Solution {`

public int rob(int[] nums) {

if(nums.length == 1) return nums[0];

int[]dp = new int[nums.length-1];

int[] dp2 = new int[nums.length-1];

// exclude the last one

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

if(i-2>=0){

dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i]);

} else if (i-1 >= 0){

dp[i]=Math.max(dp[i-1], nums[i]);

} else{

dp[i]= nums[i];

}

}

// exclude the first one

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

if(i-3>=0){

dp2[i-1]=Math.max(dp2[i-2], dp2[i-3]+nums[i]);

} else if (i-2 >= 0){

dp2[i-1]=Math.max(dp2[i-2], nums[i]);

} else{

dp2[i-1]= nums[i];

}

}

// return the bigger one

if(dp[nums.length-2] > dp2[nums.length-2]){

return dp[nums.length-2];

}

return dp2[nums.length-2];

}

}

# 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 realised 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 1Output:7Explanation: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 1Output:9Explanation: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.

/**

* 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

`class Solution {`

Map<String, Integer> memo = new HashMap<>();

public int numDecodings(String s) {

return decodeHelper(s);

}

public int decodeHelper(String s){

if(memo.containsKey(s)){

return memo.get(s);

}

if(s.length()==0){

return 1;

}

int count = 0;

// try to find out if can match 1 or 2 chars

for(int i=1; i<=2; i++){

if(i>s.length()) continue;

String beginning = s.substring(0, i);

if(!beginning.startsWith("0") && Integer.parseInt(beginning) <= 26 && Integer.parseInt(beginning) >= 1){

count += decodeHelper(s.substring(i));

}

}

memo.put(s, count);

return count;

}

}

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)){ // if it is only a number

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])){ // operator

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"]

`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 dot

}

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.

`class Solution {`

public String validIPAddress(String queryIP) {

String[] ipv4 = queryIP.split("\\.", -1);

String[] ipv6 = queryIP.split("\\:", -1);

if(queryIP.chars().filter(ch -> ch=='.').count() == 3){

for(String s: ipv4){

if(!isIPv4(s)) return "Neither";

}

return "IPv4";

}

if(queryIP.chars().filter(ch -> ch==':').count() == 7){

for(String s: ipv6){

if(!isIPv6(s)) return "Neither";

}

return "IPv6";

}

return "Neither";

}

public static boolean isIPv4(String s){

try{

// prevent leading 0

return String.valueOf(Integer.parseInt(s)).equals(s) && Integer.parseInt(s) >= 0 && Integer.parseInt(s) <= 255;

} catch (NumberFormatException e){

return false;

}

}

public static boolean isIPv6(String s){

if(s.length()<=0 || s.length()>4) return false;

for (int i = 0; i < s.length(); i++) {

char c = s.charAt(i);

if (!Character.isDigit(c) && !((c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'))) {

return false;

}

}

return true;

}

}

# 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

The following is leetcode soln

`class Solution {`

public String shortestSuperstring(String[] A) {

int N = A.length;

// Populate overlaps

int[][] overlaps = new int[N][N];

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

for (int j = 0; j < N; ++j) if (i != j) {

int m = Math.min(A[i].length(), A[j].length());

for (int k = m; k >= 0; --k)

if (A[i].endsWith(A[j].substring(0, k))) {

overlaps[i][j] = k;

break;

}

}

// dp[mask][i] = most overlap with mask, ending with ith element

int[][] dp = new int[1<<N][N];

int[][] parent = new int[1<<N][N];

for (int mask = 0; mask < (1<<N); ++mask) {

Arrays.fill(parent[mask], -1);

for (int bit = 0; bit < N; ++bit) if (((mask >> bit) & 1) > 0) {

// Let's try to find dp[mask][bit]. Previously, we had

// a collection of items represented by pmask.

int pmask = mask ^ (1 << bit);

if (pmask == 0) continue;

for (int i = 0; i < N; ++i) if (((pmask >> i) & 1) > 0) {

// For each bit i in pmask, calculate the value

// if we ended with word i, then added word 'bit'.

int val = dp[pmask][i] + overlaps[i][bit];

if (val > dp[mask][bit]) {

dp[mask][bit] = val;

parent[mask][bit] = i;

}

}

}

}

// # Answer will have length sum(len(A[i]) for i) - max(dp[-1])

// Reconstruct answer, first as a sequence 'perm' representing

// the indices of each word from left to right.

int[] perm = new int[N];

boolean[] seen = new boolean[N];

int t = 0;

int mask = (1 << N) - 1;

// p: the last element of perm (last word written left to right)

int p = 0;

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

if (dp[(1<<N) - 1][j] > dp[(1<<N) - 1][p])

p = j;

// Follow parents down backwards path that retains maximum overlap

while (p != -1) {

perm[t++] = p;

seen[p] = true;

int p2 = parent[mask][p];

mask ^= 1 << p;

p = p2;

}

// Reverse perm

for (int i = 0; i < t/2; ++i) {

int v = perm[i];

perm[i] = perm[t-1-i];

perm[t-1-i] = v;

}

// Fill in remaining words not yet added

for (int i = 0; i < N; ++i) if (!seen[i])

perm[t++] = i;

// Reconstruct final answer given perm

StringBuilder ans = new StringBuilder(A[perm[0]]);

for (int i = 1; i < N; ++i) {

int overlap = overlaps[perm[i-1]][perm[i]];

ans.append(A[perm[i]].substring(overlap));

}

return ans.toString();

}

}

# 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, if

pizza[row..rows-1][col..cols-1] contains no apples, and there is no way 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??

// I think this method is easier to understand.....just need to take note the

// initialisation of min and max

`// 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;

}

}

Starting from the top-right corner or any other corner is also possible, but it may require different decision-making logic compared to the bottom-left corner. For example, if you start from the top-right corner, you may need to move left if the target value is smaller, and move down if the target value is larger.

If you start from top left or bottom right corner, it is harder. For eg in the top left, moving down or right will lead to a value being bigger than the current value. Hence, there is no elimination of search space.

# 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 6*l*, but the buffer contains 2*l* 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

- Create an array dp of length
`n + 1`

. Initialize dp[i]=i - Iterate with a variable ii
*i*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 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;

}

}

# 372. Super Pow

Your task is to calculate `ab`

mod `1337`

where `a`

is a positive integer and `b`

is an extremely large positive integer given in the form of an array.

**Example 1:**

`Input: a = 2, b = [3]`

Output: 8

**Example 2:**

`Input: a = 2, b = [1,0]`

Output: 1024

**Example 3:**

`Input: a = 1, b = [4,3,3,8,5,2]`

Output: 1

**Constraints:**

`1 <= a <= 231 - 1`

`1 <= b.length <= 2000`

`0 <= b[i] <= 9`

`b`

does not contain leading zeros.

**One knowledge: ab % k = (a%k)(b%k)%k**

**Since the power here is an array, we’d better handle it digit by digit.**

**Suppose f(a, b) calculates a^b % k; Then translate above formula to using f :f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k;**

`class Solution {`

private:

const int base = 1337;

int powmod(int a, int k) //a^k mod 1337 where 0 <= k <= 10

{

a %= base;

int result = 1;

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

result = (result * a) % base;

return result;

}

public:

int superPow(int a, vector<int>& b) {

if (b.empty()) return 1;

int last_digit = b.back();

b.pop_back();

return powmod(superPow(a, b), 10) * powmod(a, last_digit) % base;

// (a^25, 10) * (a^4) -> (a^254)

}

};

`class Solution {`

int base = 1337;

public int superPow(int a, int[] b) {

if(b.length == 0) return 1;

int lastDigit = b[b.length-1];

return powerMod(superPow(a, Arrays.copyOfRange(b, 0, b.length-1)), 10) * powerMod(a, lastDigit) % base;

}

public int powerMod(int a, int k){

a%=base;

int result=1;

for(int i=0; i<k; ++i){

result = (result*a) % base;

}

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

}

}

`// there was an update to eleetcode test case....the one below here is the latest`

class Solution {

public double myPow(double x, int n) {

return binaryExp(x, (long) n);

}

private double binaryExp(double x, long n){

if(n==0) return 1;

if(n<0){

n = -n;

x = 1.0/x;

}

if(n%2==0){

return binaryExp(x*x, n/2);

}

return x * binaryExp(x, n-1);

}

}

# 174. Dungeon Game

The demons had captured the princess and imprisoned her in **the bottom-right corner** of a `dungeon`

. The `dungeon`

consists of `m x n`

rooms laid out in a 2D grid. Our valiant knight was initially positioned in **the top-left room** and must fight his way through `dungeon`

to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to `0`

or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight’s health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only **rightward** or **downward** in each step.

Return *the knight’s minimum initial health so that he can rescue the princess*.

**Note** that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

**Example 1:**

`Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]`

Output: 7

Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

**Example 2:**

`Input: dungeon = [[0]]`

Output: 1

`class Solution {`

int inf = Integer.MAX_VALUE;

int[][] energyNeeded;

int rows, cols;

public int getMinHealth(int currCell, int nextRow, int nextCol) {

if (nextRow >= this.rows || nextCol >= this.cols)

return inf;

int nextCell = this.energyNeeded[nextRow][nextCol]; // points that nextCell will consume

// if nextCell require 6 energy, then curr cell has 1 points, then current cell will need at least 5 points

// to meet requirement of 6 energy

// nextCell - currCell -> Calculate the diff between the energy needed in the next cell from the existing

// energy provided in the currCell

// The diff tells us how many more energy we need to add to the currCell if we want to make the jump to next cell.

// if this diff turns out to be -ve, it means currCell provides us with a lot of energy and we will only require

// the knight to have at least 1 energy so it can even make a jump to the curr cell.

return Math.max(1, nextCell - currCell);

}

public int calculateMinimumHP(int[][] dungeon) {

this.rows = dungeon.length;

this.cols = dungeon[0].length;

this.energyNeeded = new int[rows][cols];

for (int[] arr : this.energyNeeded) {

Arrays.fill(arr, this.inf);

}

int currCell, rightHealth, downHealth, nextHealth, minHealth;

for (int row = this.rows - 1; row >= 0; --row) {

for (int col = this.cols - 1; col >= 0; --col) {

currCell = dungeon[row][col];

rightHealth = getMinHealth(currCell, row, col + 1);

downHealth = getMinHealth(currCell, row + 1, col);

nextHealth = Math.min(rightHealth, downHealth);

if (nextHealth != inf) {

minHealth = nextHealth;

} else {

// entering this loop means we no longer need to move to any neighbouring

// cell. Hence, the amt of energy needed here is just dependent on the currCell.

minHealth = currCell >= 0 ? 1 : 1 - currCell;

// currCell is negative -a, so we need a + 1 to have at least 1 left after going to next cell.

// If currCell is positive, we only need 1 health to reach it.

}

this.energyNeeded[row][col] = minHealth;

}

}

return this.energyNeeded[0][0];

}

}

`Printing dp at each iteration:`

2147483647 2147483647 2147483647

2147483647 2147483647 2147483647

2147483647 2147483647 6

++++++++++++++++++

2147483647 2147483647 2147483647

2147483647 2147483647 2147483647

2147483647 1 6

++++++++++++++++++

2147483647 2147483647 2147483647

2147483647 2147483647 2147483647

1 1 6

++++++++++++++++++

2147483647 2147483647 2147483647

2147483647 2147483647 5

1 1 6

++++++++++++++++++

2147483647 2147483647 2147483647

2147483647 11 5

1 1 6

++++++++++++++++++

2147483647 2147483647 2147483647

6 11 5

1 1 6

++++++++++++++++++

2147483647 2147483647 2

6 11 5

1 1 6

++++++++++++++++++

2147483647 5 2

6 11 5

1 1 6

++++++++++++++++++

7 5 2

6 11 5

1 1 6

++++++++++++++++++

# 873. Length of Longest Fibonacci Subsequence

A sequence `x1, x2, ..., xn`

is *Fibonacci-like* if:

`n >= 3`

`xi + xi+1 == xi+2`

for all`i + 2 <= n`

Given a **strictly increasing** array `arr`

of positive integers forming a sequence, return *the **length** of the longest Fibonacci-like subsequence of* `arr`

. If one does not exist, return `0`

.

A **subsequence** is derived from another sequence `arr`

by deleting any number of elements (including none) from `arr`

, without changing the order of the remaining elements. For example, `[3, 5, 8]`

is a subsequence of `[3, 4, 5, 6, 7, 8]`

.

**Example 1:**

`Input: arr = [1,2,3,4,5,6,7,8]`

Output: 5

Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

**Example 2:**

`Input: arr = [1,3,7,11,12,14,18]`

Output: 3

Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

`class Solution {`

public int lenLongestFibSubseq(int[] arr) {

int N = arr.length;

Map<Integer, Integer> map = new HashMap<>();

for(int i=0; i<N; i++){

map.put(arr[i], i);

}

int maxLength = 0;

int[][] dp = new int[N][N];

for(int i=2; i<N; i++){

for(int j=i-1; j>=0; j--){

int diff = arr[i]-arr[j];

if(map.containsKey(diff) && map.get(diff)<j){

int other = map.get(diff);

//i>k

dp[j][i] = Math.max(dp[j][i], dp[other][j]+1);

// dp[other][j] represents length of longest subsequence ending at j and other. j > other

maxLength = Math.max(maxLength, dp[j][i]);

}

}

}

return maxLength > 0 ? maxLength + 2 : maxLength;

}

}

A single dimension array does not work.

For eg, if we have [1,2,3,4,5], 1+2=3 and 2+3=5. When we reach position with value 5, it can be made by 1+4 or 2+3. The longest length of Fib sequence is 3. But if we do dp[4]=dp[1]+dp[2]+1 where dp[1]=1 and dp[2]=3, we will get 4 which is wrong.

**The solution**

**dp[j][i] represents longest subsequence ending at j and i**. During the iteration, for each pair of indices `i`

and `j`

where `i > j`

, the code checks if there exists a value `diff`

(representing the difference between `arr[i]`

and `arr[j]`

) in the `map`

(which maps values in `arr`

to their indices) such that `diff < arr[j]`

. If such a value exists, it means there is a potential element in the subsequence that could come before `arr[j]`

and complete the Fibonacci-like property.

In that case, the code retrieves the index `k`

from the `map`

where `arr[k]`

is equal to `diff`

. Then, it updates `dp[j][i]`

by comparing the current value with `dp[other][j] + 1`

, where `dp[other][]`

represents the length of the longest Fibonacci-like subsequence ending at indices `other`

and j. By adding 1, we consider the inclusion of `arr[i]`

in the subsequence.

# 842. Split Array into Fibonacci Sequence

You are given a string of digits `num`

, such as `"123456579"`

. We can split it into a Fibonacci-like sequence `[123, 456, 579]`

.

Formally, a **Fibonacci-like** sequence is a list `f`

of non-negative integers such that:

`0 <= f[i] < 231`

, (that is, each integer fits in a**32-bit**signed integer type),`f.length >= 3`

, and`f[i] + f[i + 1] == f[i + 2]`

for all`0 <= i < f.length - 2`

.

Note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number `0`

itself.

Return any Fibonacci-like sequence split from `num`

, or return `[]`

if it cannot be done.

**Example 1:**

`Input: num = "1101111"`

Output: [11,0,11,11]

Explanation: The output [110, 1, 111] would also be accepted.

**Example 2:**

`Input: num = "112358130"`

Output: []

Explanation: The task is impossible.

**Example 3:**

`Input: num = "0123"`

Output: []

Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

**Constraints:**

`1 <= num.length <= 200`

`num`

contains only digits.

**Leetcode solution**

`class Solution {`

public List<Integer> splitIntoFibonacci(String S) {

List<Integer> ans = new ArrayList<>();

helper(S, ans, 0);

return ans;

}

public boolean helper(String s, List<Integer> ans, int idx) {

if (idx == s.length() && ans.size() >= 3) {

return true;

}

for (int i=idx; i<s.length(); i++) {

if (s.charAt(idx) == '0' && i > idx) {

break;

}

long num = Long.parseLong(s.substring(idx, i+1));

if (num > Integer.MAX_VALUE) {

break;

}

int size = ans.size();

// early termination

if (size >= 2 && num > ans.get(size-1)+ans.get(size-2)) {

break;

}

if (size <= 1 || num == ans.get(size-1)+ans.get(size-2)) {

ans.add((int)num);

// branch pruning. if one branch has found fib seq, return true to upper call

if (helper(s, ans, i+1)) {

return true;

}

ans.remove(ans.size()-1);

}

}

return false;

}

`class Solution {`

public List<Integer> splitIntoFibonacci(String num) {

List<Integer> ans = new ArrayList<>();

helper(num, ans, 0);

return ans;

}

public Boolean helper(String num, List<Integer> ans, int start){

if(start==num.length() && ans.size()>=3){ // complete

return true;

}

for(int end=start; end<num.length(); end++){

if(num.charAt(start) == '0' && end>start){ // cannot add a num with preceding 0

break;

}

long currVal = Long.parseLong(num.substring(start, end+1));

if (currVal > Integer.MAX_VALUE) {

break;

}

int size = ans.size();

if(size >= 2 && currVal > ans.get(size-1)+ans.get(size-2)){

break; // current combi is not fibonacci, cannot continue

// with next itr because the value of currVal will only get bigger

// and definitely will be wrong. So, early termination.

}

if(size<=1 || currVal==ans.get(size-1)+ans.get(size-2)){

ans.add((int)currVal);

if(helper(num, ans, end+1)){

return true;

}

ans.remove(ans.size()-1);

}

}

return false;

}

}

# 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Given an integer `k`

, *return the minimum number of Fibonacci numbers whose sum is equal to *`k`

. The same Fibonacci number can be used multiple times.

The Fibonacci numbers are defined as:

`F1 = 1`

`F2 = 1`

`Fn = Fn-1 + Fn-2`

for`n > 2.`

It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to `k`

.

**Example 1:**

`Input: k = 7`

Output: 2

Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ...

For k = 7 we can use 2 + 5 = 7.

**Example 2:**

`Input: k = 10`

Output: 2

Explanation: For k = 10 we can use 2 + 8 = 10.

**Example 3:**

`Input: k = 19`

Output: 3

Explanation: For k = 19 we can use 1 + 5 + 13 = 19.

`class Solution {`

public int findMinFibonacciNumbers(int k) {

if(k<2) return k;

// Generate all fib values

TreeSet<Integer> set = new TreeSet<>();

int first = 0;

for(int second=1; second < k;){

int temp = second;

second += first;

first = temp;

set.add(second);

}

// Greedy solution to remove biggest value from set

int res = 0;

while(k>0){

int fib = set.floor(k);// returns the greatest element in the set that is less than or equal to the given element.

k-=fib;

res++;

}

return res;

}

}

# 2301. Match Substring After Replacement

You are given two strings `s`

and `sub`

. You are also given a 2D character array `mappings`

where `mappings[i] = [oldi, newi]`

indicates that you may perform the following operation **any** number of times:

**Replace**a character`oldi`

of`sub`

with`newi`

.

Each character in `sub`

**cannot** be replaced more than once.

Return `true`

* if it is possible to make *`sub`

* a substring of *`s`

* by replacing zero or more characters according to *`mappings`

. Otherwise, return `false`

.

A **substring** is a contiguous non-empty sequence of characters within a string.

**Example 1:**

`Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]`

Output: true

Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'.

Now sub = "l3e7" is a substring of s, so we return true.

**Example 2:**

`Input: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]`

Output: false

Explanation: The string "f00l" is not a substring of s and no replacements can be made.

Note that we cannot replace '0' with 'o'.

**Example 3:**

`Input: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]`

Output: true

Explanation: Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.

Now sub = "l33tb" is a substring of s, so we return true.

**Constraints:**

`1 <= sub.length <= s.length <= 5000`

`0 <= mappings.length <= 1000`

`mappings[i].length == 2`

`oldi != newi`

`s`

and`sub`

consist of uppercase and lowercase English letters and digits.`oldi`

and`newi`

are either uppercase or lowercase English letters or digits.

`class Solution {`

public boolean matchReplacement(String s, String sub, char[][] mappings)

{

int n=mappings.length;

Map<Character,Set<Character>> map=new HashMap<>();

for(int i=0;i<n;i++){

map.putIfAbsent(mappings[i][0],new HashSet<>());

map.get(mappings[i][0]).add(mappings[i][1]);

} // one char could be mapped to >1 diff char

for(int i=0;i<s.length()-sub.length()+1;i++){

int f=-1;

int pos=i;

for(int j=0;j<sub.length();j++){

if(s.charAt(pos)==sub.charAt(j)){

// match

pos++;

} else if(!map.containsKey(sub.charAt(j)) || !map.get(sub.charAt(j)).contains(s.charAt(pos))){

// curr char is diff from match..but we cannot transform it to make it match...

f++;

break;

} else {

// transform current char in sub to match s

pos++;

}

}

if(f==-1){

return true;

}

// didn't find a match starting from position i of s....

// need to try with starting from i+1 next....

}

return false;

}

}

My original code which had time limit exceeded.

` public boolean matchReplacement(String s, String sub, char[][] mappings) {`

return helper(s, sub, mappings, 0);

}

private boolean helper(String s, String sub, char[][] mappings, int start){

if(start == sub.length()) return false;

if(s.contains(sub)) return true;

for(char[] map: mappings){

char c = map[0];

char replaceChar = map[1];

for(int i=start; i<sub.length(); i++){

if(sub.charAt(i) == c){

// replace it and check if it matches

// if yes, return true

String tryNewString = constructNewString(sub, i, replaceChar);

if(s.contains(tryNewString)) return true;

// if no,

// (1) call recursion but with i removed

if(helper(s, sub, mappings, i+1)){

return true;

}

// (2) call recursion with i present

if(helper(s, tryNewString, mappings, i+1)){

return true;

}

}

}

}

return false;

}

private String constructNewString(String sub, int i, char replaceChar){

if((i+1)<sub.length()){

return sub.substring(0, i)+replaceChar+sub.substring(i+1);

}

return sub.substring(0, i)+replaceChar;

}

# 286. Walls and Gates

You are given an `m x n`

grid `rooms`

initialized with these three possible values.

`-1`

A wall or an obstacle.`0`

A gate.`INF`

Infinity means an empty room. We use the value`231 - 1 = 2147483647`

to represent`INF`

as you may assume that the distance to a gate is less than`2147483647`

.

Fill each empty room with the distance to *its nearest gate*. If it is impossible to reach a gate, it should be filled with `INF`

.

**Example 1:**

`Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]`

Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

**Example 2:**

`Input: rooms = [[-1]]`

Output: [[-1]]

class Solution {

public void wallsAndGates(int[][] rooms) {

if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {

return;

}

int m = rooms.length;

int n = rooms[0].length;

int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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

// Enqueue all gate cells and mark them as distance 0

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (rooms[i][j] == 0) {

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

}

}

}

while (!queue.isEmpty()) {

int[] current = queue.poll();

int row = current[0];

int col = current[1];

for (int[] direction : directions) {

int newRow = row + direction[0];

int newCol = col + direction[1];

if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && rooms[newRow][newCol] == Integer.MAX_VALUE) {

rooms[newRow][newCol] = rooms[row][col] + 1;

queue.offer(new int[]{newRow, newCol});

}

}

}

}

}

# 1235. Maximum Profit in Job Scheduling

We have `n`

jobs, where every job is scheduled to be done from `startTime[i]`

to `endTime[i]`

, obtaining a profit of `profit[i]`

.

You’re given the `startTime`

, `endTime`

and `profit`

arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time `X`

you will be able to start another job that starts at time `X`

.

**Example 1:**

`Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]`

Output: 120

Explanation: The subset chosen is the first and fourth job.

Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

**Example 2:**

`Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]`

Output: 150

Explanation: The subset chosen is the first, fourth and fifth job.

Profit obtained 150 = 20 + 70 + 60.

**Example 3:**

`Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]`

Output: 6

`class Solution {`

public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {

List<Unit> jobs = new ArrayList<>();

int length = profit.length;

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

jobs.add(new Unit(startTime[i], endTime[i], profit[i]));

}

jobs.sort(Comparator.comparingInt(a -> a.start));

return findMaxProfits(jobs);

}

public int findMaxProfits(List<Unit> jobs){

int n = jobs.size();

int maxProfit = 0;

PriorityQueue<ArrayList<Integer>> pq = new PriorityQueue<>((a, b) -> a.get(0)-b.get(0));

for(int i=0; i<n; i++){

int start = jobs.get(i).start;

int end = jobs.get(i).end;

int profit = jobs.get(i).profit;

// At the current timestamp, the current job i can be scheduled

// as it does not conflict with the job at the front of the queue.

// pq.peek().get(0) contain the previous job's end time.

while(!pq.isEmpty() && start >= pq.peek().get(0)){

maxProfit = Math.max(maxProfit, pq.peek().get(1));

pq.remove();

}

ArrayList<Integer> combinedJob = new ArrayList<>();

combinedJob.add(end);

combinedJob.add(profit + maxProfit);

pq.add(combinedJob);

}

while(!pq.isEmpty()){

maxProfit = Math.max(maxProfit, pq.peek().get(1));

pq.remove();

}

return maxProfit;

}

class Unit{

int start;

int end;

int profit;

public Unit(int start, int end, int profit){

this.start = start;

this.end = end;

this.profit = profit;

}

}

}

# 1730. Shortest Path to Get Food

You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell.

You are given an `m x n`

character matrix, `grid`

, of these different types of cells:

`'*'`

is your location. There is**exactly one**`'*'`

cell.`'#'`

is a food cell. There may be**multiple**food cells.`'O'`

is free space, and you can travel through these cells.`'X'`

is an obstacle, and you cannot travel through these cells.

You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.

Return *the **length** of the shortest path for you to reach **any** food cell*. If there is no path for you to reach food, return `-1`

.

**Example 1:**

`Input: grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]`

Output: 3

Explanation: It takes 3 steps to reach the food.

**Example 2:**

`Input: grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]`

Output: -1

Explanation: It is not possible to reach the food.

**Example 3:**

`Input: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]`

Output: 6

Explanation: There can be multiple food cells. It only takes 6 steps to reach the bottom food.

Start traversing from FOOD grid.

Use BFS to avoid TLE.

`class Solution {`

int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};

public int getFood(char[][] grid) {

int n = grid.length;

int m = grid[0].length;

int steps = 0;

boolean[][] seen = new boolean[n][m];

Queue<int[]>q = new LinkedList();

for(int i=0; i<n; i++){

for(int j=0; j<m; j++){

if(grid[i][j] == '*'){

// is food

q.add(new int[]{i, j});

}

}

}

while(!q.isEmpty()){

int size = q.size();

while(size>0){

int[] index = q.poll();

int row = index[0];

int col = index[1];

if(grid[row][col] == '#') return steps;

for(int[] direction: directions){

int r = row+direction[0];

int c = col+direction[1];

if(r>=0 && c>=0 && r<n && c<m && grid[r][c] != 'X' && !seen[r][c]){

seen[r][c]=true;

q.add(new int[]{r,c});

}

}

size--;

}

steps++;

}

return -1;

}

}

`class Solution {`

public int getFood(char[][] grid) {

int len = Integer.MAX_VALUE;

// from each food, check if can get to the human

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

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

if(grid[i][j]=='#'){

int curr = findHuman(grid, i, j);

len = Math.min(curr, len);

}

}

}

return len != Integer.MAX_VALUE ? len : -1;

}

// dfs: TLE

// public int findHuman(char[][] grid, int i, int j){

// if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]=='X'){

// return Integer.MAX_VALUE;

// }

// if(grid[i][j] == '*'){

// return 0;

// }

// if(dp[i][j] != 0){

// return dp[i][j];

// }

// int left = findHuman(grid, i, j-1);

// int right = findHuman(grid, i, j+1);

// int up = findHuman(grid, i-1, j);

// int down = findHuman(grid, i+1, j);

// return dp[i][j] = Math.min(Math.min(Math.min(left, right), up), down) + 1;

// }

public int findHuman(char[][] grid, int i, int j){

Queue<Point> queue = new LinkedList<>();

queue.add(new Point(i,j,0));

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

while(!queue.isEmpty()){

Point curr = queue.poll();

if(visited.contains(curr.coord)) continue;

visited.add(curr.coord);

if(grid[curr.coord.x][curr.coord.y] == 'X') continue;

if(grid[curr.coord.x][curr.coord.y] == '*') return curr.len;

if((curr.coord.x-1)>=0){

queue.add(new Point(curr.coord.x-1, curr.coord.y, curr.len+1));

}

if((curr.coord.x+1)<grid.length){

queue.add(new Point(curr.coord.x+1, curr.coord.y, curr.len+1));

}

if((curr.coord.y-1)>=0){

queue.add(new Point(curr.coord.x, curr.coord.y-1, curr.len+1));

}

if((curr.coord.y+1)<grid[0].length){

queue.add(new Point(curr.coord.x, curr.coord.y+1, curr.len+1));

}

}

return Integer.MAX_VALUE;

}

public class Point{

Coord coord;

int len;

public Point(int x, int y, int len){

this.coord = new Coord(x, y);

this.len = len;

}

public String toString(){

return coord.x+" "+coord.y+" "+len;

}

}

public class Coord{

int x;

int y;

public Coord(int x, int y){

this.x = x;

this.y = y;

}

public String toString(){

return x + " " + y;

}

public boolean equals(Object obj) {

if (this == obj) {

return true;

}

if (obj == null || getClass() != obj.getClass()) {

return false;

}

Coord other = (Coord) obj;

return x == other.x && y == other.y;

}

public int hashCode() {

return Objects.hash(x, y);

}

}

}