- Notifications
You must be signed in to change notification settings - Fork2.4k
Sri Hari: Batch-3/Neetcode-150/Added hints#3741
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
@Srihari2222 Yeah I think for hard problems a solution that passes is enough. For example, trapping rain water O(n) and O(n) space is enough, we don't need O(1) space. For sliding window max, i think same, whatever is enough to pass. I think that would be O(nlogn) time. |
hints/buy-and-sell-crypto.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 1</summary> | ||
<p> | ||
A brute force solution would be to iterate throgh the array with index <code>i</code>, considering it as the day to buy, and trying all possible options for selling it on the days to the right of index <code>i</code>. This would be an <code>O(n^2)</code> solution. Can you think of a better way? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
typo: through
hints/buy-and-sell-crypto.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 2</summary> | ||
<p> | ||
From the problem, you should buy at a price and should always sell at a higher price. Can you try to fix anyone between buy and sell? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I would remove "From the problem" it seems unnecessary.
Can you try to fix anyone between buy and sell?
I think this could be more clear, i'm not sure what this means.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Got it. I re-wrote it.
<details class="hint-accordion"> | ||
<summary>Hint 3</summary> | ||
<p> | ||
We can iterate through the array with index <code>i</code>, considering it as the selling value. But what value will it be optimal to consider as buying point on the left of index <code>i</code>? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This is an excellent hint, good job!
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thanks.
hints/buy-and-sell-crypto.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 4</summary> | ||
<p> | ||
It is obvious to take the minimum value as the buying point on the left of index <code>i</code>. So, we just need to maintain the prefix minimum for the index <code>i</code> and compute the profit as <code>sell - buy</code>. The result will be the maximum profit among all. We also need to make sure that we can also avoid doing transaction. So, we should initialize our maximum profit as <code>0</code>. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
We can remove "It is obvious". Some beginners might be offended by it.
I think it might be easier to start this hint with the motivation. For example, we can say start with something like this:
We are trying to maximize profit = sell - buy. If the current i is the sell value, we want to choose to minimum buy value to the left of i to maximize the profit.
I think this wording is a natural follow up to your third hint.
We also need to make sure that we can also avoid doing transaction.
This isn't super clear. Do you mean that if we cannot do a profitable transaction?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
yeah, good feedback. I will make sure not to use that word again.
hints/daily-temperatures.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 3</summary> | ||
<p> | ||
We can use a stack to maintain elements in a monotonically decreasing order. To maintain the monotonically decreasing order, we pop elements from the stack whose values are smaller than the current element. However, since we need to compute the result array by finding the difference between indices, we should store the indices of the elements in the stack instead of the elements themselves but should consider the values at that indices while operating the stack. Can you figure out how is this stack useful? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
However, since we need to compute the result array by finding the difference between indices, we should store the indices of the elements in the stack instead of the elements themselves but should consider the values at that indices while operating the stack.
This sentence is pretty long, can we split it up.
<details class="hint-accordion"> | ||
<summary>Hint 1</summary> | ||
<p> | ||
A brute force solution would be to try the substring starting at index <code>i</code> and try to find the maximum length we can form without duplicates by starting at that index. We can use hash set for <code>O(1)</code> lookups. Can you think of a better way? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I would specifically mention that we can use a hashset todetect duplicates in O(1) time.
hints/permutation-string.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 2</summary> | ||
<p> | ||
It is obvious to return false when the length of <code>s1</code> is greater than the length of <code>s2</code>. We can simply use an array of size <code>O(26)</code>, since the character set is <code>a</code> through <code>z</code> (<code>26</code> continuous characters), to count the frequency of each character in a string. Which algorithm can we use now? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Minor feedback:
- Remove "it is obvious"
- In the second sentence, i would start with "To count the frequency.. we can simply use an array.." Starting with the reason makes it easier to understand. Otherwise when i start that sentence idk why we are using an array.
hints/validate-parentheses.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 2</summary> | ||
<p> | ||
We can use a stack to store characters. Iterate through the string by index. For an opening bracket, push it onto the stack. If the bracket is a closing type, check for the corresponding opening bracket at the top of the stack. If we don't find the corresponding opening bracket, immediately return false. Why this works? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Why [does] this work?
@neetcode-gh |
hints/binary-search.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 2</summary> | ||
<p> | ||
The problem name is the name of the algorithm that we gonna use. We need to find a target value and if it does not exist in the array return <code>-1</code>. We have <code>l</code> and <code>r</code> as the boundaries of the segment of the array in which we are searching. Try building conditions to eliminate half of the search segment at each step. Maybe sorted nature of the array can be helpful. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
The problem name is the name of the algorithm that we gonna use.
The problem name is the name of the algorithm that we [can] use.
hints/binary-search.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 3</summary> | ||
<p> | ||
We compare the target value with the <code>mid</code> of the segment. For example, in <code>[1, 2, 3, 4, 5]</code> and <code>target = 4</code>, <code>mid</code> is equal to <code>3</code> and we only consider the segment <code>[4, 5]</code> for the next step. Why? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
minor: I would split it up like this:
For example, consider the array [1, 2, 3, 4, 5] and target = 4. The mid value is 3, thus, on the next iteration we search to the right of mid. The remaining segment is [4,5].
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Yeah, this is good statement.
hints/eating-bananas.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 1</summary> | ||
<p> | ||
Can you determine the upper bound for the possible answer? How much time does it take Koko to eat a pile with <code>x</code> bananas? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Can you determine the upper bound for the possible answer?
Remove "possible". Also, we should mention thath
is always greater than or equal to the length of piles, since that is the only reason we can determine the upper bound.
hints/eating-bananas.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 3</summary> | ||
<p> | ||
The upper bound for <code>k</code> is the maximum size of all the piles. Why? Because if Koko eats largest pile in one hour, then it is straightforward that she can eat any other pile in an hour only. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Because if Koko eats largest pile in one hour, then it is straightforward that she can eat any other pile in an hour only.
if koko eats [the] largest pile
Now that we have tools like chatgpt to proof read, I don't really wanna catch grammar errors for you.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
It is weird that after I wrote the hint and cross-checked it with GPT for errors, it can also make mistakes in grammar.
hints/eating-bananas.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 4</summary> | ||
<p> | ||
A brute force solution would be to linearly check all values from <code>1</code> to <code>m</code> and find the minimum possible value at which Koko can complete the task. This approach would take <code>O(n * m)</code> time, where <code>n</code> is the size of the input array, and <code>m</code> is the maximum value in the array. Can you think of a more efficient method? Perhaps an efficient searching algorithm could help. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Why are we using a variablem
in a sentence before we explain what it represents. This is a poor way of conveying ideas.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thanks, I will keep that in mind.
hints/eating-bananas.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 5</summary> | ||
<p> | ||
We can use the binary search on answers approach because if Koko cannot finish the task with a rate of <code>k</code>, it means she also cannot finish it with any rate less than <code>k</code>. Similarly, if she can finish the task with a rate of <code>k</code>, she can also finish it with any rate greater than <code>k</code>. This allows us to find the smallest possible <code>k</code> using binary search. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Even ignoring the grammar errors, I think some of these hints could be much better.
Don't you think they are overly verbose and also hard to understand?
Why didn't you just say:
Rather than linearly scanning, we can use binary search. The upper bound of
k
ismax(piles)
and since we are only dealing with positive values, the lower bound is1
. The search space of our binary search is1
throughmax(piles)
.
Keep in mind, you're not writing these hints for yourself. You are writing them for other people.
if Koko cannot finish the task with a rate of
k
, it means she also cannot finish it with any rate less thank
. Similarly, if she can finish the task with a rate ofk
, she can also finish it with any rate greater thank
. This allows us to find the smallest possiblek
using binary search.
The problems I see with this part are:
- This is implied, for even the brute force solution, it's not specific to the binary search solution, so it just feels like a distraction.
- Hints don't need to be a substitution for solutions. We don't need to provide long explanations.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I was confused by the (2) point that hints need not be lengthy. I will make sure I don't write long hints.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
@Srihari2222 I don't think long hints are necessarily bad. But if it's possible to convey the same information with less words, that is preferable. I think most of the hints have been pretty good.
<details class="hint-accordion"> | ||
<summary>Hint 1</summary> | ||
<p> | ||
A rectangle has a length and a breadth. Can you visualize how rectangles are formed in the given input? Considering one bar at a time might help. The height of the bar becomes the length of the rectangle. How can you determine the breadth of the rectangle in which the current bar is present, with the length of the rectangle being the height of the bar? Extending the current bar to the left and right might help determine the rectangle's breadth. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Why are we using length and breadth?
Don't you think in the context of this problem we should usewidth
andheight
. Please read the problem statement again. To be honest, I know it's easy for me to correct this, but I'm honestly a little puzzled that I had to tell you this.
I'm pretty sure you are better than me at leetcode, so why is your reading and writing skills so subpar? If you are tired, I understand. You can always take a break. I would prefer that, rather than having to give you basic feedback.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Sorry, I will try to improve it. I thought people would be comfortable with length and breadth in terms of rectangles. But yeah, I will make sure and be more focused on it now.
hints/sliding-window-maximum.md Outdated
<details class="hint-accordion"> | ||
<summary>Hint 2</summary> | ||
<p> | ||
A heap is the best data structure to use when dealing with maximum or minimum values and it takes <code>O(1)</code> time to know the max or min value depending on the type of the heap. Here, we use a max-heap. But what should we do if the current maximum element is no longer part of the window? Can you think of a different way of adding values to the max-heap? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
time to "get" the max or min
we can remove the "depending on the type of the heap" part. It's implied and it shortens the hint.
<br> | ||
<details class="hint-accordion"> | ||
<summary>Hint 4</summary> | ||
<p> |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Good hint, no feedback.
hints/sliding-window-maximum.md Outdated
<details class="hint-accordion"> | ||
<summary>Recommended Time & Space Complexity</summary> | ||
<p> | ||
You should aim for a solution with <code>O(nlogn)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I think we should say "as good or better" since an O(n) solution exists. But let me know if you did this for a reason.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Sorry, it was my mistake. But I can assure you that, I always try to see the work I have done neetcode and I always try to correct that If I made any mistake. This mistake you mentioned is an example.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I also got to know that I have done some mistakes in the solutions, when I see that I corrected those articles when I was writing Go and Kotlin solutions. Now I am 100% sure that there is no solution in those articles that gives a wrong answer and any errors other than TLE for brute force.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
@Srihari2222 Thank you, i appreciate that.
Uh oh!
There was an error while loading.Please reload this page.
@neetcode-gh
Can you just confirm that for a hard problem, should I suggest the most optimal solution or else I should just suggest an average solution that basically passes? Example: Can you suggest for trapping rain water and sliding window maximum.
You can just tell the suggestion so that It will be helpful for me to go myself for other hard problems also.
Also, I am trying my best to phrase good hints. But to justify every statement, it is taking more time to create hints and the number of hints are becoming at least 3. Hope you understand it as I also need to read the question while creating hints and phrase the statements properly and include examples if necessary in the hints. Also, it is more hard to phrase the greedy ideas as hints.