Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

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

Merged
neetcode-gh merged 6 commits intoneetcode-gh:mainfromSrihari2222:develop_hints
Nov 18, 2024

Conversation

Srihari2222
Copy link
Collaborator

@Srihari2222Srihari2222 commentedNov 15, 2024
edited
Loading

@neetcode-gh

  • Took 7 hours for this work.
  • Please review it.

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.

@neetcode-gh
Copy link
Owner

@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.

<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?

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

typo: through

<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?

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.

Copy link
CollaboratorAuthor

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>?

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!

Copy link
CollaboratorAuthor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thanks.

<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>.

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?

Copy link
CollaboratorAuthor

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.

<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?

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?

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.

<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?

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Minor feedback:

  1. Remove "it is obvious"
  2. 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.

<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?

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Why [does] this work?

@Srihari2222
Copy link
CollaboratorAuthor

@neetcode-gh
Thanks for the feedback, it will really help me to improve in writing the hints.

neetcode-gh reacted with thumbs up emoji

<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.

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.

<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?

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].

Copy link
CollaboratorAuthor

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.

<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?

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.

<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.

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.

Copy link
CollaboratorAuthor

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.

<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.

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.

Copy link
CollaboratorAuthor

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.

<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.

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 ofk 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 ofk, 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:

  1. 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.
  2. Hints don't need to be a substitution for solutions. We don't need to provide long explanations.

Copy link
CollaboratorAuthor

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.

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.

Srihari2222 reacted with thumbs up emoji
<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.

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.

Copy link
CollaboratorAuthor

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.

<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?

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>

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Good hint, no feedback.

<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.

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.

Copy link
CollaboratorAuthor

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.

Copy link
CollaboratorAuthor

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.

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.

@neetcode-ghneetcode-gh merged commit7222e1e intoneetcode-gh:mainNov 18, 2024
@Srihari2222Srihari2222 deleted the develop_hints branchNovember 18, 2024 07:05
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@neetcode-ghneetcode-ghAwaiting requested review from neetcode-gh

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

2 participants
@Srihari2222@neetcode-gh

[8]ページ先頭

©2009-2025 Movatter.jp