I think this it would be really important to explain that instead of a map if you use an array to store the values, you'll get MLE.. Using a map works here since most values actually aren't required since you're skipping them. Same is the idea with the time complexity !
First, thank you for your regular videos and clear explanations, Neetcode! In my solution, I sorted the array first, and also added 0 and n values to the array. I think it is a simpler approach: def minCost(n: int, cuts: list[int]) -> int: cuts = [0] + sorted(cuts) + [n]
cache = {} def recursive(l, r): if r - l == 1: return 0
if (l,r) in cache: return cache[(l,r)]
cache[(l,r)] = cuts[r] - cuts[l] + min([recursive(l, m) + recursive(m, r) for m in range(l+1, r)]) return cache[(l,r)]
Would it be possible to optimize it by trying to cut a stick in the point that is closer to the middle? Or if there are two points with equal distance from the middle, then try both and return the lowest cost
According to the constraints this problem needs to be solved in another approach where the recurrence relation depends on the cuts array not the len of the stick
@NeetcodeIO Nice Solution. You can get rid of inf. So if a stick can not be cut, cost will be 0. Below is the code. from functools import cache class Solution: def minCost(self, n: int, cuts: list[int]) -> int: @cache def dfs(l: int, r: int) -> int: w = r - l return min( (w + dfs(l, c) + dfs(c, r) for c in cuts if l < c < r), default=0 ) return dfs(0, n)
I didn't understand why we are adding these (r - l) + dfs(l, c) + dfs(c, r) , isn't r-l the length of rod? and why do we need to add both left and right cuts
The cost for cutting a stick is the length of the stick you cut, plus the costs of cutting the two sticks that your are left with after cutting the first one.
Just to be precise, for this specific task, the overall complexity can be improved from O(N^3) to O(N^2) via the Knuth's Optimization, possible because of the cost function properties.
Honestly I don’t feel the question was worded wrong, although a bit tricky. You must cut it in an order just means you cannot cut simultaneously, and not necessarily in the given order.
Sometimes with problems like this I have trouble figuring out what parameters to cache the results by. Any tips on figuring out what we need to cache the results by in any problem?
Even I struggle with the same . You can try writing the recursive solution first, then maybe drawing its recursive tree . Sometimes this helps me identify what are the subproblems being repeated, and what to cache.
Lmao man, i guess i have gotten better cuz this is the solution i kind of thought but just wasnt sure about it in few parts, so checked to see if i was correct 😅.
java implementation - class Solution { Map cacheMap = new HashMap(); public int minCost(int n, int[] cuts) { return dfs(0, n, cuts); } private int dfs(int left, int right, int cuts[]) { if (right - left == 1) return 0; String currentPair = left + "," + right; if (cacheMap.containsKey(currentPair)) { return cacheMap.get(currentPair); } int result = Integer.MAX_VALUE; for (int c : cuts) { if (left < c && c < right) { int currResult = (right - left) + dfs(left, c, cuts) + dfs(c, right, cuts); result = Math.min(result, currResult); } } result = (result == Integer.MAX_VALUE) ? 0 : result; cacheMap.put(currentPair, result); return result; } }
Interestingly enough, but if we use 2d array for memo we get Memory limit exceeded. public class Solution { public int minCost(int n, int[] cuts) { int[][] memo = new int[n + 1][n + 1]; return dfs(cuts, 0, n, memo); } private int dfs( int[] cuts, int left, int right, int[][] memo) { if(left - right == 1) return 0; if(memo[left][right] != 0){ return memo[left][right]; } int result = Integer.MAX_VALUE; for (int i = 0; i < cuts.length; i++) { if(cuts[i] < right && cuts[i] > left) { result = Math.min(result, right - left + dfs(cuts, left, cuts[i], memo) + dfs(cuts, cuts[i], right, memo)); } } if(result == Integer.MAX_VALUE) result = 0; memo[left][right] = result; return result; } }
They use a pretty clever variation of the solution I presented, where instead of needing an 'if-statement' to check if a cut applies to the current stick, we can just pass the appropriate subarray of cuts into the recursive call. In that solution left and right refer to the index of `cuts`, rather than the edges of the current stick.
Whoever is coming up with these descriptions needs to chill out with the loopy loop. Reminds me of the meme "Every 60 seconds in Africa a minute passes".
class Solution { public: int dfs(int l, int r , vector &cuts,vector&dp){ if(r-l==1)return 0; if(dp[l][r]!=-1){ return dp[l][r]; } int res=INT_MAX; for(auto c:cuts){ if(c>l && c
I got the same , Memory limit exceeded issue, then i tried hashmap, instead of vector of vector... class Solution { public: int util(int i, int j, vector& cuts, unordered_map& dp) { if (i + 1 == j) { return 0; } string key = to_string(i) + "_" + to_string(j); if (dp.count(key) != 0) { return dp[key]; } int res = INT_MAX; for (int x = 0; x < cuts.size(); x++) { if (cuts[x] > i && cuts[x] < j) { int cost = j - i; cost += util(i, cuts[x], cuts, dp); cost += util(cuts[x], j, cuts, dp); res = min(res, cost); } } if (res == INT_MAX) { res = 0; } dp[key] = res; return res; } int minCost(int n, vector& cuts) { unordered_map dp; return util(0, n, cuts, dp); } }; This code gave TLE, even though all test case passed. Leetcode just doesnt want this solution in c++
Don't use vector, use unordered_map or map instead. Reason is: vector has pre-allocated space(even some cache might miss), whereas hashmap or map only uses necessary(cache hit) memory. You can try to verify the result by checking the vector how much cache has been missed (value, -1). But the downside is you'll have to provide your own hashfuc if you go with unordered_map(collision, might hurt the runtime complexity). Hope that helps.
hi neetcode while you are trying to solve this, did you come up with your own solution ? bcoz i solved nearly 400+ problems i didn’t able to come up with this solution am i really bad ? or the problem ?
Yeah yeah it happens.. I have solved around 550 questions but still end up confused and blank with some questions. Just never stop learning new methods and see where you are lacking and solve more questions on those topics.. For me it is graphs... :)
Same solution but 1 second faster: class Solution: def minCost(self, n: int, cuts: List[int]) -> int: cuts.sort() @lru_cache(None) def dfs(l: int, r: int) -> int: if l >= r - 1: return 0 res = float("inf") for i in range(bisect_left(cuts, l), bisect_right(cuts, r)): if l < cuts[i] < r: res = min(res, dfs(l, cuts[i]) + dfs(cuts[i], r) + r - l) return res if res != float("inf") else 0 return dfs(0, n)
I think this it would be really important to explain that instead of a map if you use an array to store the values, you'll get MLE..
Using a map works here since most values actually aren't required since you're skipping them.
Same is the idea with the time complexity !
Correction, time complexity should be O(M^3), no need to include N, since we wont necessarily cut it at every point.
could u explain to get order in which we need to cut the rod
Hi, Can you solve this problem by using dynamic programing?
@@maotay yes, in the solution it dp only
Hey Neet thank you so much for this one, Leetcode should hire you to make their video solution editorials! You're the Best, kind sir!
First, thank you for your regular videos and clear explanations, Neetcode!
In my solution, I sorted the array first, and also added 0 and n values to the array. I think it is a simpler approach:
def minCost(n: int, cuts: list[int]) -> int:
cuts = [0] + sorted(cuts) + [n]
cache = {}
def recursive(l, r):
if r - l == 1:
return 0
if (l,r) in cache:
return cache[(l,r)]
cache[(l,r)] = cuts[r] - cuts[l] + min([recursive(l, m) + recursive(m, r) for m in range(l+1, r)])
return cache[(l,r)]
return recursive(0, len(cuts)-1)
Would it be possible to optimize it by trying to cut a stick in the point that is closer to the middle? Or if there are two points with equal distance from the middle, then try both and return the lowest cost
Thank you
According to the constraints this problem needs to be solved in another approach where the recurrence relation depends on the cuts array not the len of the stick
@NeetcodeIO Nice Solution.
You can get rid of inf. So if a stick can not be cut, cost will be 0. Below is the code.
from functools import cache
class Solution:
def minCost(self, n: int, cuts: list[int]) -> int:
@cache
def dfs(l: int, r: int) -> int:
w = r - l
return min(
(w + dfs(l, c) + dfs(c, r) for c in cuts if l < c < r),
default=0
)
return dfs(0, n)
Thanks man , u are the GOAT
The top-down solution doesn't deserve the "Hard" label, the real hard part of this problem is to come up the bottom-up solution.
can you explain why a greedy solution wont work in this case
thanks for this explanatory video
Hi, Can you solve this problem by using dynamic programing?
can anyone explain how to get the order in which we need to cut the rod
wonderful explanation
Thank you!
I didn't understand why we are adding these (r - l) + dfs(l, c) + dfs(c, r) , isn't r-l the length of rod? and why do we need to add both left and right cuts
The cost for cutting a stick is the length of the stick you cut, plus the costs of cutting the two sticks that your are left with after cutting the first one.
Just to be precise, for this specific task, the overall complexity can be improved from O(N^3) to O(N^2) via the Knuth's Optimization, possible because of the cost function properties.
Indeed! Knuth's Optimisation is perfect for such cases when the cost function is a subarray sum.
Thanks for the daily
Honestly I don’t feel the question was worded wrong, although a bit tricky. You must cut it in an order just means you cannot cut simultaneously, and not necessarily in the given order.
Sometimes with problems like this I have trouble figuring out what parameters to cache the results by. Any tips on figuring out what we need to cache the results by in any problem?
Even I struggle with the same . You can try writing the recursive solution first, then maybe drawing its recursive tree . Sometimes this helps me identify what are the subproblems being repeated, and what to cache.
Thank you so much for these daily challenge questions. Your explanations are just so easy to understand. Love from India.
Thanks
thanks neet
Lmao man, i guess i have gotten better cuz this is the solution i kind of thought but just wasnt sure about it in few parts, so checked to see if i was correct 😅.
can anyone explain the time complexity here?
java implementation -
class Solution {
Map cacheMap = new HashMap();
public int minCost(int n, int[] cuts) {
return dfs(0, n, cuts);
}
private int dfs(int left, int right, int cuts[]) {
if (right - left == 1) return 0;
String currentPair = left + "," + right;
if (cacheMap.containsKey(currentPair)) {
return cacheMap.get(currentPair);
}
int result = Integer.MAX_VALUE;
for (int c : cuts) {
if (left < c && c < right) {
int currResult = (right - left) + dfs(left, c, cuts) + dfs(c, right, cuts);
result = Math.min(result, currResult);
}
}
result = (result == Integer.MAX_VALUE) ? 0 : result;
cacheMap.put(currentPair, result);
return result;
}
}
Interestingly enough, but if we use 2d array for memo we get Memory limit exceeded.
public class Solution {
public int minCost(int n, int[] cuts) {
int[][] memo = new int[n + 1][n + 1];
return dfs(cuts, 0, n, memo);
}
private int dfs( int[] cuts, int left, int right, int[][] memo) {
if(left - right == 1) return 0;
if(memo[left][right] != 0){
return memo[left][right];
}
int result = Integer.MAX_VALUE;
for (int i = 0; i < cuts.length; i++) {
if(cuts[i] < right && cuts[i] > left) {
result = Math.min(result, right - left + dfs(cuts, left, cuts[i], memo) + dfs(cuts, cuts[i], right, memo));
}
}
if(result == Integer.MAX_VALUE) result = 0;
memo[left][right] = result;
return result;
}
}
I'm just wondering. Wont we get the same issue if we solve it bottom up using tabulation like the Tip suggests
"someone should put down the crack pipe" - neetcode 2023
Jokes aside, I was wondering why the official solution sorts the array before solving
They use a pretty clever variation of the solution I presented, where instead of needing an 'if-statement' to check if a cut applies to the current stick, we can just pass the appropriate subarray of cuts into the recursive call.
In that solution left and right refer to the index of `cuts`, rather than the edges of the current stick.
Amazing
Whoever is coming up with these descriptions needs to chill out with the loopy loop. Reminds me of the meme "Every 60 seconds in Africa a minute passes".
class Solution {
public:
int dfs(int l, int r , vector &cuts,vector&dp){
if(r-l==1)return 0;
if(dp[l][r]!=-1){
return dp[l][r];
}
int res=INT_MAX;
for(auto c:cuts){
if(c>l && c
bro did you got the problem ?
I got the same , Memory limit exceeded issue, then i tried hashmap, instead of vector of vector...
class Solution {
public:
int util(int i, int j, vector& cuts, unordered_map& dp)
{
if (i + 1 == j)
{
return 0;
}
string key = to_string(i) + "_" + to_string(j);
if (dp.count(key) != 0)
{
return dp[key];
}
int res = INT_MAX;
for (int x = 0; x < cuts.size(); x++)
{
if (cuts[x] > i && cuts[x] < j)
{
int cost = j - i;
cost += util(i, cuts[x], cuts, dp);
cost += util(cuts[x], j, cuts, dp);
res = min(res, cost);
}
}
if (res == INT_MAX)
{
res = 0;
}
dp[key] = res;
return res;
}
int minCost(int n, vector& cuts) {
unordered_map dp;
return util(0, n, cuts, dp);
}
};
This code gave TLE, even though all test case passed.
Leetcode just doesnt want this solution in c++
Don't use vector, use unordered_map or map instead. Reason is: vector has pre-allocated space(even some cache might miss), whereas hashmap or map only uses necessary(cache hit) memory. You can try to verify the result by checking the vector how much cache has been missed (value, -1). But the downside is you'll have to provide your own hashfuc if you go with unordered_map(collision, might hurt the runtime complexity). Hope that helps.
hi neetcode while you are trying to solve this, did you come up with your own solution ?
bcoz i solved nearly 400+ problems i didn’t able to come up with this solution am i really bad ? or the problem ?
Yeah yeah it happens.. I have solved around 550 questions but still end up confused and blank with some questions. Just never stop learning new methods and see where you are lacking and solve more questions on those topics.. For me it is graphs... :)
@@yolo3659 can we make group and solve with each other !
Thank you so much
Same solution but 1 second faster:
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts.sort()
@lru_cache(None)
def dfs(l: int, r: int) -> int:
if l >= r - 1:
return 0
res = float("inf")
for i in range(bisect_left(cuts, l), bisect_right(cuts, r)):
if l < cuts[i] < r:
res = min(res, dfs(l, cuts[i]) + dfs(cuts[i], r) + r - l)
return res if res != float("inf") else 0
return dfs(0, n)
Thank you !