Part2
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: grid = [[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:
def minPathSum(self, grid: List[List[int]]) -> int:
return self.helper(grid, 0, 0, {})
def helper(self, grid, r, c, dp):
if (r, c) in dp:
return dp[(r, c)]
if r == len(grid) - 1 and c == len(grid[0]) - 1:
return grid[r][c]
if r == len(grid) or c == len(grid[0]):
return float("inf")
p1 = self.helper(grid, r + 1, c, dp)
p2 = self.helper(grid, r, c + 1, dp)
dp[(r, c)] = grid[r][c] + min(p1, p2)
return dp[(r, c)]
use std::{cmp::min, collections::HashMap};
impl Solution {
pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
let mut dp: HashMap<(usize, usize), i32> = HashMap::new();
return Solution::helper(&grid, 0, 0, &mut dp);
}
fn helper(
grid: &Vec<Vec<i32>>,
r: usize,
c: usize,
dp: &mut HashMap<(usize, usize), i32>,
) -> i32 {
if dp.contains_key(&(r, c)) {
return *dp.get(&(r, c)).unwrap();
}
if r == grid.len() - 1 && c == grid[0].len() - 1 {
return grid[r][c];
}
if r == grid.len() || c == grid[0].len() {
return i32::MAX;
}
let p1 = Solution::helper(grid, r + 1, c, dp);
let p2 = Solution::helper(grid, r, c + 1, dp);
let res = grid[r][c] + min(p1, p2);
dp.insert((r, c), res);
return res;
}
}
Coin Change
❓: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
Example:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
res = self.helper(coins, amount, 0, {})
return res if res != float("inf") else -1
def helper(self, coins, amount, ind, dp):
if (amount, ind) in dp:
return dp[(amount, ind)]
if amount == 0:
return 0
if ind == len(coins):
return float("inf")
p1 = self.helper(coins, amount, ind + 1, dp)
p2 = float("inf")
if coins[ind] <= amount:
p2 = 1 + self.helper(coins, amount - coins[ind], ind, dp)
dp[(amount, ind)] = min(p1, p2)
return dp[(amount, ind)]
use std::{cmp::min, collections::HashMap};
impl Solution {
pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
let mut dp: HashMap<(usize, i32), i32> = HashMap::new();
let res = Solution::helper(&coins, 0, 0, amount, &mut dp);
if res == i32::MAX {
return -1;
}
return res;
}
fn helper(
coins: &Vec<i32>,
ind: usize,
curr: i32,
amount: i32,
dp: &mut HashMap<(usize, i32), i32>,
) -> i32 {
if dp.contains_key(&(ind, curr)) {
return *dp.get(&(ind, curr)).unwrap();
}
if ind == coins.len() || curr > amount {
return i32::MAX;
}
if curr == amount {
return 0;
}
let p1: i64 = 1 + Solution::helper(coins, ind, curr + coins[ind], amount, dp) as i64;
let p2: i64 = Solution::helper(coins, ind + 1, curr, amount, dp) as i64;
let mini = min(p1, p2);
if mini >= i32::MAX as i64 {
dp.insert((ind, curr), i32::MAX);
return i32::MAX;
}
dp.insert((ind, curr), mini as i32);
return mini as i32;
}
}
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:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
class Solution:
def canPartition(self, nums: List[int]) -> bool:
target = sum(nums)
if target % 2:
return False
return self.helper(nums, target // 2, 0, {})
def helper(self, nums, target, ind, dp):
if (target, ind) in dp:
return dp[(target, ind)]
if target == 0:
return True
if target < 0 or ind == len(nums):
return False
p1 = self.helper(nums, target, ind + 1, dp)
p2 = False
if nums[ind] <= target:
p2 = self.helper(nums, target - nums[ind], ind + 1, dp)
dp[(target, ind)] = p1 or p2
return dp[(target, ind)]
use std::collections::HashMap;
impl Solution {
pub fn can_partition(nums: Vec<i32>) -> bool {
let target: i32 = nums.iter().sum();
if target % 2 == 1 {
return false;
}
let mut dp: HashMap<(usize, i32), bool> = HashMap::new();
Solution::helper(&nums, 0, target / 2, &mut dp)
}
fn helper(
nums: &Vec<i32>,
ind: usize,
target: i32,
dp: &mut HashMap<(usize, i32), bool>,
) -> bool {
if dp.contains_key(&(ind, target)) {
return *dp.get(&(ind, target)).unwrap();
}
if target == 0 {
return true;
}
if target < 0 || ind == nums.len() {
return false;
}
let p1 = Solution::helper(nums, ind + 1, target - nums[ind], dp);
let p2 = Solution::helper(nums, ind + 1, target, dp);
dp.insert((ind, target), p1 || p2);
return p1 || p2;
}
}
Rod Cutting
❓: Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:
Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.
Problem statement is confusing, please refer leetcode link for better clarity of description.
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
return self.helper(0, n, cuts, {})
def helper(self, l, r, cuts, dp):
if (l, r) in dp:
return dp[(l, r)]
res = float("inf")
for cut in cuts:
if l < cut < r:
res = min(
res,
r
- l
+ self.helper(l, cut, cuts, dp)
+ self.helper(cut, r, cuts, dp),
)
dp[(l, r)] = res if res != float("inf") else 0
return dp[(l, r)]
use std::{cmp::min, collections::HashMap, i32};
impl Solution {
pub fn min_cost(n: i32, cuts: Vec<i32>) -> i32 {
let mut dp: HashMap<(i64, i64), i64> = HashMap::new();
Solution::helper(0, n as i64, &cuts, &mut dp) as i32
}
fn helper(l: i64, r: i64, cuts: &Vec<i32>, dp: &mut HashMap<(i64, i64), i64>) -> i64 {
if dp.contains_key(&(l, r)) {
return *dp.get(&(l, r)).unwrap();
}
if l == r {
return 0;
}
let i: i64 = 2;
let mut res: i64 = i.pow(32);
for cut in cuts.iter() {
let i_cut: i64 = *cut as i64;
if l < i_cut && i_cut < r {
let curr = r - l
+ Solution::helper(l, i_cut, cuts, dp)
+ Solution::helper(i_cut, r, cuts, dp);
res = min(res, curr);
}
}
if res >= i.pow(32) {
res = 0
}
dp.insert((l, r), res);
return res;
}
}
Egg Dropping
❓: You are given n identical eggs and you have access to a k-floored building from 1 to k.
There exists a floor f where 0 <= f <= k such that any egg dropped from a floor higher than f will break, and any egg dropped from or below floor f will not break.
There are few rules given below.
1. An egg that survives a fall can be used again.
2. A broken egg must be discarded.
3. The effect of a fall is the same for all eggs.
4. If the egg doesn't break at a certain floor, it will not break at any floor below.
5. If the egg breaks on a certain floor, it will break on any floor above.
Return the minimum number of moves you need to determine the value of f with certainty.
Example:
Input: n = 1, k = 2
Output: 2
Explanation: Drop the egg from floor 1. If it breaks, we know that f = 0. Otherwise, drop the egg from floor 2.If it breaks, we know that f = 1. If it does not break, then we know f = 2. Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
Input: n = 10, k = 5
Output: 3
Explanation: Drop the egg from floor 2. If it breaks, test floor 1 with a remaining egg.If it doesn’t break, drop from floor 4. If it breaks, test floor 3. If it still doesn’t break, we know the critical floor is 5.Hence, with a minimum of 3 moves, we can find the critical floor.
class Solution:
def eggDrop(self, n, k):
return self.helper(n, k, {})
def helper(self, n, k, dp):
if (n, k) in dp:
return dp[(n, k)]
if n == 1 or k <= 0:
return k
res = float("inf")
for i in range(1, k + 1):
not_break = self.helper(n, k - i, dp)
breaks = self.helper(n - 1, i - 1, dp)
res = min(res, 1 + max(not_break, breaks))
dp[(n, k)] = res
return dp[(n, k)]
use std::{
cmp::{max, min},
collections::HashMap,
};
fn egg_drop(n: i32, k: i32) -> i32 {
let mut dp: HashMap<(i32, i32), i32> = HashMap::new();
return helper(n, k, &mut dp);
}
fn helper(n: i32, k: i32, dp: &mut HashMap<(i32, i32), i32>) -> i32 {
if dp.contains_key(&(n, k)) {
return *dp.get(&(n, k)).unwrap();
}
if n == 1 || k <= 0 {
return k;
}
let mut res = 100;
for i in 1..k + 1 {
let not_break = helper(n, k - i, dp);
let breaks = helper(n - 1, i - 1, dp);
res = min(res, 1 + max(breaks, not_break));
}
dp.insert((n, k), res);
return res;
}
fn main() {
assert_eq!(egg_drop(1, 2), 2);
assert_eq!(egg_drop(10, 5), 3);
assert_eq!(egg_drop(2, 10), 4);
}
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:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
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.
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
return self.helper(s, set(wordDict), 0, {})
def helper(self, s, words, ind, dp):
if ind in dp:
return dp[ind]
if ind == len(s):
return True
for i in range(ind + 1, len(s) + 1):
if s[ind:i] in words and self.helper(s, words, i, dp):
dp[ind] = True
return dp[ind]
dp[ind] = False
return dp[ind]
use std::collections::{HashMap, HashSet};
impl Solution {
pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
let word_set: HashSet<String> = word_dict.into_iter().collect();
let mut dp: HashMap<usize, bool> = HashMap::new();
return Solution::helper(&s, &word_set, 0, &mut dp);
}
fn helper(s: &str, words: &HashSet<String>, ind: usize, dp: &mut HashMap<usize, bool>) -> bool {
if dp.contains_key(&ind) {
return *dp.get(&ind).unwrap();
}
if ind == s.len() {
return true;
}
for i in ind + 1..s.len() + 1 {
if words.contains(&s[ind..i]) && Solution::helper(s, words, i, dp) == true {
dp.insert(ind, true);
return true;
}
}
dp.insert(ind, false);
false
}
}
Palindrome Partitioning
❓: Given a string s, a partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome. Determine the fewest cuts needed for palindrome partitioning of the given string.
Example:
Input: s = "ababbbabbababa"
Output: 3
Explaination: After 3 partitioning substrings
are "a", "babbbab", "b", "ababa".
Input: s = "aaabba"
Output: 1
Explaination: The substrings after 1 partitioning are "aa" and "abba".
class Solution:
def palindromicPartition(self, s):
return self.helper(s, 0, {})
def helper(self, s, ind, dp):
if ind in dp:
return dp[ind]
if s[ind:] == s[ind:][::-1]:
return 0
res = len(s)
for i in range(ind + 1, len(s)):
curr_string = s[ind:i]
if curr_string == curr_string[::-1]:
res = min(res, 1 + self.helper(s, i, dp))
dp[ind] = res
return dp[ind]
use std::{cmp::min, collections::HashMap};
fn palindrom_partition(s: String) -> usize{
let mut dp: HashMap<usize, usize> = HashMap::new();
return helper(&s, 0, &mut dp)
}
fn helper(s: &str, ind: usize, dp: &mut HashMap<usize, usize>) -> usize{
if dp.contains_key(&ind){
return *dp.get(&ind).unwrap()
}
if &s[ind..] == &s[ind..].chars().rev().collect::<String>(){
return 0
}
let mut res = s.len();
for i in ind+1..s.len(){
let curr_string = &s[ind..i];
if curr_string == curr_string.chars().rev().collect::<String>(){
res = min(res, 1 + helper(s, i, dp))
}
}
dp.insert(ind, res);
res
}
fn main(){
assert_eq!(palindrom_partition("ababbbabbababa".to_string()), 3);
assert_eq!(palindrom_partition("aaabba".to_string()), 1);
assert_eq!(palindrom_partition("aaa".to_string()), 0);
}
Job Sequencing Problem
❓: You are given three arrays: id, deadline, and profit, where each job is associated with an ID, a deadline, and a profit. Each job takes 1 unit of time to complete, and only one job can be scheduled at a time. You will earn the profit associated with a job only if it is completed by its deadline.
Your task is to find: The maximum number of jobs that can be completed within their deadlines. The total maximum profit earned by completing those jobs.
Example:
Input: id = [1, 2, 3, 4], deadline = [4, 1, 1, 1], profit = [20, 1, 40, 30]
Output: [2, 60]
Explanation: Job1 and Job3 can be done with maximum profit of 60 (20+40).
Input: id = [1, 2, 3, 4, 5], deadline = [2, 1, 2, 1, 1], profit = [100, 19, 27, 25, 15]
Output: [2, 127]
Explanation: Job1 and Job3 can be done with maximum profit of 127 (100+27).
class Solution:
def JobSequencing(self, id, deadline, profit):
tuple_items = [(a, b, c) for (a, b, c) in zip(profit, deadline, id)]
tuple_items.sort(reverse=True)
n = len(id)
res = [0] * n
for item_profit, item_deadline, _ in tuple_items:
ind = item_deadline - 1
while ind >= 0 and res[ind] != 0:
ind -= 1
if ind >= 0:
res[ind] = item_profit
return len(res) - res.count(0), sum(res)