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
}
}
import "math"
func maxProduct(nums []int) int {
res := math.MinInt32
pre, suff := 1, 1
n := len(nums)
for i, num := range nums {
pre = pre * num
suff = suff * nums[n-i-1]
res = max(res, pre)
res = max(res, suff)
if pre == 0 {
pre = 1
}
if suff == 0 {
suff = 1
}
}
return 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()
}
}
import "slices"
func lengthOfLIS(nums []int) int {
n := len(nums)
lis := make([]int, n)
for i := range n {
lis[i] = 1
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if nums[i] < nums[j] {
lis[i] = max(lis[i], 1+lis[j])
}
}
}
return slices.Max(lis)
}
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();
}
}
func longestCommonSubsequence(text1 string, text2 string) int {
type Key struct {
i int
j int
}
dp := map[Key]int{}
var helper func(i, j int) int
helper = func(i, j int) int {
if val, ok := dp[Key{i, j}]; ok {
return val
}
if i == len(text1) || j == len(text2) {
return 0
}
res := 0
if text1[i] == text2[j] {
res = helper(i+1, j+1) + 1
} else {
res = max(helper(i+1, j), helper(i, j+1))
}
dp[Key{i, j}] = res
return res
}
return helper(0, 0)
}
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
);
}
package main
import "fmt"
func knapsack01(wt, val []int, W int) int {
type Key struct {
ind int
curr int
}
dp := map[Key]int{}
var helper func(ind, curr int) int
helper = func(ind, curr int) int {
if val, ok := dp[Key{ind, curr}]; ok {
return val
}
if ind == len(wt) {
return 0
}
pick := 0
if wt[ind] <= curr {
pick = val[ind] + helper(ind+1, curr-wt[ind])
}
not_pick := helper(ind+1, curr)
dp[Key{ind, curr}] = max(pick, not_pick)
return dp[Key{ind, curr}]
}
return helper(0, W)
}
func main() {
fmt.Println(knapsack01([]int{10, 20, 30}, []int{60, 100, 120}, 50) == 220)
fmt.Println(knapsack01([]int{5, 4, 6, 3}, []int{10, 40, 30, 50}, 10) == 90)
fmt.Println(knapsack01([]int{1, 2, 3, 8, 7, 4}, []int{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
}
}
func minDistance(word1 string, word2 string) int {
type Key struct {
i int
j int
}
dp := map[Key]int{}
var helper func(ind1, ind2 int) int
helper = func(ind1, ind2 int) int {
if val, ok := dp[Key{ind1, ind2}]; ok {
return val
}
if ind1 == len(word1) && 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[Key{ind1, ind2}] = helper(ind1+1, ind2+1)
return dp[Key{ind1, ind2}]
}
insert := helper(ind1, ind2+1)
delete := helper(ind1+1, ind2)
replace := helper(ind1+1, ind2+1)
dp[Key{ind1, ind2}] = min(insert, delete, replace) + 1
return dp[Key{ind1, ind2}]
}
return helper(0, 0)
}
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);
}
package main
import (
"fmt"
"slices"
)
func maxSumIS(nums []int) int {
n := len(nums)
lis := make([]int, n)
copy(lis, nums)
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if nums[i] < nums[j] {
lis[i] = max(lis[i], nums[i]+lis[j])
}
}
}
return slices.Max(lis)
}
func main() {
fmt.Println(maxSumIS([]int{1, 101, 2, 3, 100}) == 106)
fmt.Println(maxSumIS([]int{4, 1, 2, 3}) == 6)
fmt.Println(maxSumIS([]int{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)
}
package main
import (
"fmt"
"math"
)
func matrixMultiplication(nums []int) int {
type key struct {
i int
j int
}
dp := map[key]int{}
var helper func(i, j int) int
helper = func(i, j int) int {
if val, ok := dp[key{i, j}]; ok {
return val
}
if i == j {
return 0
}
mini := math.MaxInt
for k := i; k < j; k++ {
mini = min(
mini,
helper(i, k)+helper(k+1, j)+nums[i-1]*nums[k]*nums[j],
)
}
dp[key{i, j}] = mini
return mini
}
return helper(1, len(nums)-1)
}
func main() {
fmt.Println(matrixMultiplication([]int{2, 1, 3, 4}) == 20)
fmt.Println(matrixMultiplication([]int{1, 2, 3, 4, 3}) == 30)
fmt.Println(matrixMultiplication([]int{3, 4}) == 0)
}