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 = 167Example 2:
Input: nums = [1,5]
Output: 10Constraints:
n == nums.length1 <= n <= 3000 <= 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 object o as a parameter to be stored in the returned list.
Return Value: This method returns an immutable list containing only the specified object.
Qns 1 b: Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
The trick to understanding the code here is very simple: Simply write out and follow through the code with a simple example, for eg [1,2,3]
- 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+1Example 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
1through9are 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 >= 1Alternative solution
class Solution {
public int numSquares(int n) {
ArrayList<Integer> square_nums = new ArrayList<Integer>();
for (int i = 1; i * i <= n; ++i) {
square_nums.add(i * i);
}
Set<Integer> queue = new HashSet<Integer>();
queue.add(n);
int level = 0;
while (queue.size() > 0) {
level += 1;
Set<Integer> next_queue = new HashSet<Integer>();
for (Integer remainder : queue) {
for (Integer square : square_nums) {
if (remainder.equals(square)) {
return level;
} else if (remainder < square) {
break;
} else {
next_queue.add(remainder - square);
}
}
}
queue = next_queue;
}
return level;
}
}
Approach 4 (Current code) time complexity
Approach 3 time complexity
Time complexity: O(n^(n+1)) because in the worst case we can search n + 1 level in depth (worst case the perfect squares are made up all by 1s) from 0 and the tree can thus contains up to n^(n+1) nodes (n^0 + n^1 + n^2 + ... + n^(n-1) + n^n).
Space complexity: O(n^n) because of the queue used to store each level we are iterating through.
Qns 4: You are a renowned thief who has recently switched from stealing precious metals to stealing cakes because of the insane profit margins. You end up hitting the jackpot, breaking into the world’s largest privately owned stock of cakes — the vault of the Queen of England.
While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.
Each type of cake has a weight and a value, stored in objects of a CakeType class:
Each type of cake has a weight and a value, stored in objects of a CakeType class:
public class CakeType { final int weight;
final int value; public CakeType(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.
Write a method maxDuffelBagValue() that takes an array of cake type objects and a weight capacity, and returns the maximum monetary value the duffel bag can hold. Weights and values may be any non-negative integer.
Cracking the Coding Interview — Practice Question
Qns 1: Leet code 70 Climbing stairs. You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Similar to coin change 2.
Qns 2: Robots in a grid: A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Extension 1 (Leet Code 63): Certain cells are marked off-boundary
Extension 2 (Leet Code 980):
On a 2-dimensional grid, there are 4 types of squares:
1represents the starting square. There is exactly one starting square.2represents the ending square. There is exactly one ending square.0represents empty squares we can walk over.-1represents 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]. 6is greater than previous number,sub1 = [2, 6]8is greater than previous number,sub1 = [2, 6, 8]3is less than previous number, we can't extend the subsequencesub1, but we must keep3because 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 extendsub1, but we can extendsub2, sosub1 = [2, 6, 8], sub2 = [2, 3, 4]. - With
5, we can't extendsub1, but we can extendsub2, sosub1 = [2, 6, 8], sub2 = [2, 3, 4, 5]. - With
1, we can extend neithersub1norsub2, but we need to keep1, sosub1 = [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
subarrays (sub1,sub2...,subk) which causes poor performance. But we notice that we can just keep onesubarray, when new numberxis not greater than the last element of the subsequencesub, we do binary search to find the smallest element >=xinsub, and replace with numberx. - Let’s run that example
nums = [2, 6, 8, 3, 4, 5, 1]again:
- Let pick the first element,
sub = [2]. 6is greater than previous number,sub = [2, 6]8is greater than previous number,sub = [2, 6, 8]3is less than previous number, so we can't extend the subsequencesub. We need to find the smallest number >=3insub, it's6. Then we overwrite it, nowsub = [2, 3, 8].4is less than previous number, so we can't extend the subsequencesub. We overwrite8by4, sosub = [2, 3, 4].5is greater than previous number,sub = [2, 3, 4, 5].1is less than previous number, so we can't extend the subsequencesub. We overwrite2by1, sosub = [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: falseclass 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: 4Example 2:
Input: matrix = [["0","1"],["1","0"]]
Output: 1Example 3:
Input: matrix = [["0"]]
Output: 0Hmmm 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: 0Example 3:
Input: matrix = [["0"]]
Output: 0Example 4:
Input: matrix = [["1"]]
Output: 1Example 5:
Input: matrix = [["0","0"]]
Output: 0This 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 aboveExample 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 checksLeet 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 fromcountAndSay(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: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: [3,4,5,1,3,null,1] 3
/ \
4 5
/ \ \
1 3 1Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Use a helper function which receives a node and a bool variable as input, and if that variable is false, it returns the maximum amount of money the thief can rob if starting from this node and robbing this node, else returns the maximum amount of money the thief can rob if starting from this node without robbing this node.
/**
* 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: 1class 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)) = 2Example 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) = 10Solution:
- 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 <= 4xiis 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
xis a negative integer, thenabs(x) = -x. - If
xis a non-negative integer, thenabs(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: trueExample 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: falseclass 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, AExample 2:
Input: n = 7
Output: 9
Explanation: We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V// Copied from Leetcode's submission from another user
// Assume dp[i] is the current best A list we can get
class Solution {
public int maxA(int N) {
int[] dp = new int[N+1];
for (int i=1; i<=N; i++) {
if (i<=5) {
dp[i] = i;
} else {
// There are following cases:
// Type A, which is just dp[i-1]+1
// Select, copy and paste previous A list generated by three steps before, which is dp[i-3]*2
// Select, copy, paste, paste. So it is actually pasting dp[i-4] which is the list four steps before and we times three here
// Select, copy, paste, paste, paste. So it is actually pasting dp[i-5] which is the list five steps before and we times four here
// We will not have the case of pasting more than 3 times because we can select, copy and paste again to paste with longer A list.
// Select, copy, paste, paste, paste, paste ----smaller than----> Select, copy, paste, Select, copy, paste
dp[i] = Math.max(dp[i-1]+1, Math.max(dp[i-3]*2, Math.max(dp[i-4]*3, dp[i-5]*4)));
}
}
return dp[N];
}
}(The one above is easier to understand)
Editorial Solution
Let’s make the first observation: once we have used the copy operation, there is no need to print a single letter A anymore because we can paste the buffer instead. Thus we press a single letter A only at the beginning.
Let’s say that we have used up m presses so far and have obtained a string of length l.
- After these m presses, one can copy-paste the text by pressing Ctrl+A, Ctrl+C, and Ctrl+V. It costs three key presses and doubles the length, so we have a length of 2l with a total of m+3 presses.
- We can press Ctrl+V again, and the length will be 3l with m+4 total presses.
- We can continue this pattern — if we press Ctrl+V 3 times, we have a length of 4l with m+5 total presses. In general, we can have a length of k⋅l with m+k+1 presses, where k≥2.
Here we use the answer to the smaller problem (m) to get the answer to the bigger ones (m+3, m+4, m+5). It alludes to dynamic programming. But before jumping into DP, we make one more observation.
There is no need to press Ctrl+V more than four times in a row. Let the current length be l. Assume we press Ctrl+A, Ctrl+C, then Ctrl+V 5 times. After this sequence, the length becomes 6l, and the buffer contains l characters.
However, if we press Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V instead, the length also becomes 6l, but the buffer contains 2l characters now, which is not worse than in the former case. In both scenarios, we used seven presses.
Now we formulate the DP. Let dp[i] be the answer when we can do i presses.
We can initialize base cases as dp[i]=i (print the letter A i times, this is the first observation we made).
Now we want to describe transitions (the recurrence relation). As stated above, it is inefficient to press Ctrl+V 5 times or more in a row. This means we will press Ctrl+A, Ctrl+C, and then Ctrl+V up to four times:
- dp[i+3]=2⋅dp[i]
- dp[i+4]=3⋅dp[i]
- dp[i+5]=4⋅dp[i]
- dp[i+6]=5⋅dp[i]
In general, we have dp[j]=(j−i−1)⋅dp[i], where i+3≤j≤i+6. We want to take the maximum value, and this gives us our recurrence relation.
class Solution {
public int maxA(int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = i;
}
for (int i = 0; i <= n - 3; i++) {
for (int j = i + 3; j <= Math.min(n, i + 6); j++) {
dp[j] = Math.max(dp[j], (j - i - 1) * dp[i]);
}
}
return dp[n];
}
}Algorithm
- Create an array dp of length
n + 1. Initialize dp[i]=i - Iterate with a variable iii until n−3
- For each j from i+3 to min(n,i+6) update (if greater) dp[j] with (j−i−1)⋅dp[i].
3. Return dp[n]
Complexity Analysis
- Time complexity: O(n)
There are O(n)states in the DP. We visit each state once and loop up to 4 times, which costs O(1) at each state.
- Space complexity: O(n)
We store all O(n) states in our dp array.
My wrong attempt
class Solution {
public int maxA(int n){
return helper(n, 0);
}
public int helper(int n, int numOfAs){
if(n<=0) return numOfAs;
int copyPaste = 0;
if(n>=3){
copyPaste = helper(n-3, numOfAs*2);
}
int addA = 0;
if(n>=1){
addA = helper(n-1, numOfAs+1);
}
return Math.max(copyPaste, addA);
}
}
// Does not work for when n=7. The code produces 8 as output, but 9 is the expected.343. Integer Break
Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.
Example 1:
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.Example 2:
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
From 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: 8Example 2:
Input: a = 2, b = [1,0]
Output: 1024Example 3:
Input: a = 1, b = [4,3,3,8,5,2]
Output: 1Constraints:
1 <= a <= 231 - 11 <= b.length <= 20000 <= b[i] <= 9bdoes 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.00000Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25class 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: 1class 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 >= 3xi + xi+1 == xi+2for alli + 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, andf[i] + f[i + 1] == f[i + 2]for all0 <= 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 <= 200numcontains 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 = 1F2 = 1Fn = Fn-1 + Fn-2forn > 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
oldiofsubwithnewi.
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 <= 50000 <= mappings.length <= 1000mappings[i].length == 2oldi != newisandsubconsist of uppercase and lowercase English letters and digits.oldiandnewiare 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.
-1A wall or an obstacle.0A gate.INFInfinity means an empty room. We use the value231 - 1 = 2147483647to representINFas you may assume that the distance to a gate is less than2147483647.
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: 6class 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);
}
}
}