Part1
Max Product Subarray
❓: Given an array that contains both negative and positive integers, find the maximum product subarray.
Example:
Input: [1,2,3,4,5,0]
Output: 120
Explanation: In the given array, we can see 1×2×3×4×5 gives maximum product value.
Input: Nums = [1,2,-3,0,-4,-5]
Output: 20
Explanation: In the given array, we can see (-4)×(-5) gives maximum product value.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
res = float("-inf")
pre, suff = 1, 1
n = len(nums)
for i in range(n):
pre = pre * nums[i]
suff = suff * nums[n - i - 1]
res = max(pre, suff, res)
if pre == 0:
pre = 1
if suff == 0:
suff = 1
return res
use std::cmp::max;
impl Solution {
pub fn max_product(nums: Vec<i32>) -> i32 {
let (mut pre_max, mut suff_max) = (1, 1);
let n = nums.len();
let mut res = nums[0];
for i in 0..n {
pre_max = pre_max * nums[i];
suff_max = suff_max * nums[n - i - 1];
res = max(res, max(pre_max, suff_max));
if pre_max == 0 {
pre_max = 1
}
if suff_max == 0 {
suff_max = 1
}
}
res
}
}
Longest Increasing Subsequence
❓: Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Input: Nums = [0,1,0,3,2,3]
Output: 4
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
lis = [1] * n
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if nums[i] < nums[j]:
lis[i] = max(lis[i], 1 + lis[j])
return max(lis)
use std::cmp::max;
impl Solution {
pub fn length_of_lis(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut lis: Vec<i32> = vec![1; n];
for i in (0..n).rev() {
for j in i + 1..n {
if nums[i] < nums[j] {
lis[i] = max(lis[i], 1 + lis[j]);
}
}
}
*lis.iter().max().unwrap()
}
}
Longest Common Subsequence
❓: Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
Example:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Input: Nums = text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
return self.helper(text1, text2, dp={})
def helper(self, text1, text2, ind1=0, ind2=0, dp={}):
if (ind1, ind2) in dp:
return dp[(ind1, ind2)]
if ind1 == len(text1) or ind2 == len(text2):
return 0
if text1[ind1] == text2[ind2]:
dp[(ind1, ind2)] = 1 + self.helper(text1, text2, ind1 + 1, ind2 + 1, dp)
return dp[(ind1, ind2)]
p1 = self.helper(text1, text2, ind1, ind2 + 1, dp)
p2 = self.helper(text1, text2, ind1 + 1, ind2, dp)
dp[(ind1, ind2)] = max(p1, p2)
return dp[(ind1, ind2)]
use std::{cmp::max, collections::HashMap, str};
impl Solution {
pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
let mut dp: HashMap<(usize, usize), i32> = HashMap::new();
Solution::helper(&text1, &text2, 0, 0, &mut dp)
}
fn helper(
text1: &str,
text2: &str,
ind1: usize,
ind2: usize,
dp: &mut HashMap<(usize, usize), i32>,
) -> i32 {
if dp.contains_key(&(ind1, ind2)) {
return *dp.get(&(ind1, ind2)).unwrap();
}
if ind1 == text1.len() || ind2 == text2.len() {
return 0;
}
if text1.as_bytes()[ind1] == text2.as_bytes()[ind2] {
let res = 1 + Solution::helper(text1, text2, ind1 + 1, ind2 + 1, dp);
dp.insert((ind1, ind2), res);
return res;
}
let p1 = Solution::helper(text1, text2, ind1 + 1, ind2, dp);
let p2 = Solution::helper(text1, text2, ind1, ind2 + 1, dp);
dp.insert((ind1, ind2), max(p1, p2));
return *dp.get(&(ind1, ind2)).unwrap();
}
}
0/1 Knapsack
❓: A thief wants to rob a store. He is carrying a bag of capacity W. The store has ‘n’ items. Its weight is given by the ‘wt’ array and its value by the ‘val’ array. He can either include an item in its knapsack or exclude it but can’t partially have it as a fraction. We need to find the maximum value of items that the thief can steal.
Example:
class Solution:
def knapsack01(self, wt, val, n, W):
return self.helper(wt, val, 0, W, {})
def helper(self, wt, val, ind, curr, dp):
if (ind, curr) in dp:
return dp[(ind, curr)]
if ind == len(wt):
return 0
pick = 0
if wt[ind] <= curr:
pick = val[ind] + self.helper(wt, val, ind + 1, curr - wt[ind], dp)
not_pick = self.helper(wt, val, ind + 1, curr, dp)
dp[(ind, curr)] = max(pick, not_pick)
return dp[(ind, curr)]
use std::{cmp::max, collections::HashMap};
struct Solution {}
impl Solution {
fn zero_one_knapsack(wt: Vec<usize>, val: Vec<usize>, w: usize) -> usize {
let mut dp: HashMap<(usize, usize), usize> = HashMap::new();
Solution::helper(&wt, &val, 0, w, &mut dp)
}
fn helper(
wt: &Vec<usize>,
val: &Vec<usize>,
ind: usize,
curr: usize,
dp: &mut HashMap<(usize, usize), usize>,
) -> usize {
if dp.contains_key(&(ind, curr)) {
return *dp.get(&(ind, curr)).unwrap();
}
if ind == wt.len() {
return 0;
}
let p1 = Solution::helper(wt, val, ind + 1, curr, dp);
let mut p2 = 0;
if wt[ind] <= curr {
p2 = val[ind] + Solution::helper(wt, val, ind + 1, curr - wt[ind], dp);
}
dp.insert((ind, curr), max(p1, p2));
*dp.get(&(ind, curr)).unwrap()
}
}
fn main() {
assert_eq!(
Solution::zero_one_knapsack(vec![10, 20, 30], vec![60, 100, 120], 50),
220
);
assert_eq!(
Solution::zero_one_knapsack(vec![5, 4, 6, 3], vec![10, 40, 30, 50], 10),
90
);
assert_eq!(
Solution::zero_one_knapsack(vec![1, 2, 3, 8, 7, 4], vec![20, 5, 10, 40, 15, 25], 10),
60
);
}
Edit Distance
❓: We are given two strings ‘S1’ and ‘S2’. We need to convert S1 to S2. The following three operations are allowed:
1. Deletion of a character.
2. Replacement of a character with another one.
3. Insertion of a character.
We have to return the minimum number of operations required to convert S1 to S2 as our answer.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
return self.helper(word1, word2, dp={})
def helper(self, word1, word2, ind1=0, ind2=0, dp={}):
if (ind1, ind2) in dp:
return dp[(ind1, ind2)]
if ind1 == len(word1) and ind2 == len(word2):
return 0
if ind1 == len(word1):
return len(word2) - ind2
if ind2 == len(word2):
return len(word1) - ind1
if word1[ind1] == word2[ind2]:
dp[(ind1, ind2)] = self.helper(word1, word2, ind1 + 1, ind2 + 1, dp)
return dp[(ind1, ind2)]
insert = self.helper(word1, word2, ind1, ind2 + 1, dp)
delete = self.helper(word1, word2, ind1 + 1, ind2, dp)
replace = self.helper(word1, word2, ind1 + 1, ind2 + 1, dp)
dp[(ind1, ind2)] = 1 + min(insert, delete, replace)
return dp[(ind1, ind2)]
use std::{cmp::min, collections::HashMap};
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let mut dp: HashMap<(usize, usize), usize> = HashMap::new();
Solution::helper(&word1, &word2, 0, 0, &mut dp) as i32
}
fn helper(
word1: &str,
word2: &str,
ind1: usize,
ind2: usize,
dp: &mut HashMap<(usize, usize), usize>,
) -> usize {
if dp.contains_key(&(ind1, ind2)) {
return *dp.get(&(ind1, ind2)).unwrap();
}
if ind1 == word1.len() && ind2 == word2.len() {
return 0;
}
if ind1 == word1.len() {
return word2.len() - ind2;
}
if ind2 == word2.len() {
return word1.len() - ind1;
}
if word1.as_bytes()[ind1] == word2.as_bytes()[ind2] {
let res = Solution::helper(word1, word2, ind1 + 1, ind2 + 1, dp);
dp.insert((ind1, ind2), res);
return res;
}
let insert = Solution::helper(word1, word2, ind1, ind2 + 1, dp);
let delete = Solution::helper(word1, word2, ind1 + 1, ind2, dp);
let replace = Solution::helper(word1, word2, ind1 + 1, ind2 + 1, dp);
let res = 1 + min(insert, min(delete, replace));
dp.insert((ind1, ind2), res);
res
}
}
Max Sum Increasing Subsequence
❓: Given an array of positive integers arr. Find the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in strictly increasing order i.e. a strictly increasing subsequence.
Example:
Input: [1, 101, 2, 3, 100]
Output: 106
Explanation: The maximum sum of a increasing sequence is obtained from [1, 2, 3, 100].
Input: arr[] = [4, 1, 2, 3]
Output: 6
Explanation: The maximum sum of a increasing sequence is obtained from {1, 2, 3}.
class Solution:
def maxSumIS(self, arr):
n = len(arr)
dp = arr[:]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if arr[i] < arr[j]:
dp[i] = max(dp[i], arr[i] + dp[j])
return max(dp)
use std::cmp::max;
struct Solution {}
impl Solution {
pub fn length_of_lis(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut dp: Vec<i32> = nums.clone();
for i in (0..n).rev() {
for j in i + 1..n {
if nums[i] < nums[j] {
dp[i] = max(dp[i], nums[i] + dp[j]);
}
}
}
*dp.iter().max().unwrap()
}
}
fn main() {
assert_eq!(Solution::length_of_lis(vec![1, 101, 2, 3, 100]), 106);
assert_eq!(Solution::length_of_lis(vec![4, 1, 2, 3]), 6);
assert_eq!(Solution::length_of_lis(vec![4, 1, 2, 4]), 7);
}
Matrix Chain Multiplication
❓: Given an array arr[] which represents the dimensions of a sequence of matrices where the ith matrix has the dimensions (arr[i-1] x arr[i]) for i>=1, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of multiplications.
Example:
Input: arr[] = [2, 1, 3, 4]
Output: 20
Explanation: There are 3 matrices of dimensions 2 × 1, 1 × 3, and 3 × 4, Let this 3 input matrices be M1, M2, and M3. There are two ways to multiply: ((M1 x M2) x M3) and (M1 x (M2 x M3)), note that the result of (M1 x M2) is a 2 x 3 matrix and result of (M2 x M3) is a 1 x 4 matrix.
((M1 x M2) x M3) requires (2 x 1 x 3) + (2 x 3 x 4) = 30
(M1 x (M2 x M3)) requires (1 x 3 x 4) + (2 x 1 x 4) = 20.
The minimum of these two is 20.
class Solution:
def matrixMultiplication(self, nums):
return self.helper(nums, 1, len(nums) - 1, {})
def helper(self, nums, i, j, dp):
if (i, j) in dp:
return dp[(i, j)]
if i == j:
return 0
mini = float("inf")
for k in range(i, j):
mini = min(
mini,
self.helper(nums, i, k, dp)
+ self.helper(nums, k + 1, j, dp)
+ (nums[i - 1] * nums[k] * nums[j]),
)
dp[(i, j)] = mini
return dp[(i, j)]
use std::{cmp::min, collections::HashMap};
struct Solution {}
impl Solution {
fn matrix_chain_multiplication(nums: Vec<usize>) -> usize {
let mut dp: HashMap<(usize, usize), usize> = HashMap::new();
Solution::helper(&nums, 1, nums.len() - 1, &mut dp)
}
fn helper(
nums: &Vec<usize>,
i: usize,
j: usize,
dp: &mut HashMap<(usize, usize), usize>,
) -> usize {
if dp.contains_key(&(i, j)) {
return *dp.get(&(i, j)).unwrap();
}
if i == j {
return 0;
}
let mut res = usize::MAX;
for k in i..j {
res = min(
res,
Solution::helper(nums, i, k, dp)
+ Solution::helper(nums, k + 1, j, dp)
+ (nums[i - 1] * nums[k] * nums[j]),
);
}
dp.insert((i, j), res);
return *dp.get(&(i, j)).unwrap();
}
}
fn main() {
assert_eq!(Solution::matrix_chain_multiplication(vec![2, 1, 3, 4]), 20);
assert_eq!(
Solution::matrix_chain_multiplication(vec![1, 2, 3, 4, 3]),
30
);
assert_eq!(Solution::matrix_chain_multiplication(vec![3, 4]), 0)
}