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

Commitc4ff1cc

Browse files
authored
Batch-3/Neetcode-150/Added hints (neetcode-gh#3750)
1 parent8e802c5 commitc4ff1cc

10 files changed

+280
-1
lines changed

‎articles/pacific-atlantic-water-flow.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
##1. Backtracking
1+
##1.Brute Force (Backtracking)
22

33
::tabs-start
44

‎hints/clone-graph.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(V + E)</code> time and <code>O(E)</code> space, where <code>V</code> is the number of vertices and <code>E</code> is the number of edges in the given graph.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
We are given only the reference to the node in the graph. Cloning the entire graph means we need to clone all the nodes as well as their child nodes. We can't just clone the node and its neighbor and return the node. We also need to clone the entire graph. Can you think of a recursive way to do this, as we are cloning nodes in a nested manner? Also, can you think of a data structure that can store the nodes with their cloned references?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (DFS) algorithm. We use a hash map to map the nodes to their cloned nodes. We start from the given node. At each step of the DFS, we create a node with the current node's value. We then recursively go to the current node's neighbors and try to clone them first. After that, we add their cloned node references to the current node's neighbors list. Can you think of a base condition to stop this recursive path?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We stop this recursive path when we encounter a node that has already been cloned or visited. This DFS approach creates an exact clone of the given graph, and we return the clone of the given node.
30+
</p>
31+
</details>

‎hints/count-number-of-islands.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the grid.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
An island is a group of <code>1</code>'s in which every <code>1</code> is reachable from any other <code>1</code> in that group. Can you think of an algorithm that can find the number of groups by visiting a group only once? Maybe there is a recursive way of doing it.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (DFS) algorithm to traverse each group independently. We iterate through each cell of the grid. When we encounter a <code>1</code>, we perform a DFS starting at that cell and recursively visit every other <code>1</code> that is reachable. During this process, we mark the visited <code>1</code>'s as <code>0</code> to ensure we don't revisit them, as they belong to the same group. The number of groups corresponds to the number of islands.
22+
</p>
23+
</details>

‎hints/course-schedule.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(V + E)</code> time and <code>O(V + E)</code> space, where <code>V</code> is the number of courses (nodes) and <code>E</code> is the number of prerequisites (edges).
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
Consider the problem as a graph where courses represent the nodes, and <code>prerequisite[i] = [a, b]</code> represents a directed edge from <code>a</code> to <code>b</code>. We need to determine whether the graph contains a cycle. Why? Because if there is a cycle, it is impossible to complete the courses involved in the cycle. Can you think of an algorithm to detect cycle in a graph?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (DFS) algorithm to detect a cycle in a graph. We iterate over each course, run a DFS from that course, and first try to finish its prerequisite courses by recursively traversing through them. To detect a cycle, we initialize a hash set called <code>path</code>, which contains the nodes visited in the current DFS call. If we encounter a course that is already in the <code>path</code>, we can conclude that a cycle is detected. How would you implement it?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We run a DFS starting from each course by initializing a hash set, <code>path</code>, to track the nodes in the current DFS call. At each step of the DFS, we return <code>false</code> if the current node is already in the <code>path</code>, indicating a cycle. We recursively traverse the neighbors of the current node, and if any of the neighbor DFS calls detect a cycle, we immediately return <code>false</code>. Additionally, we clear the neighbors list of a node when no cycle is found from that node to avoid revisiting those paths again.
30+
</p>
31+
</details>

‎hints/design-twitter-feed.md

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time for each <code>getNewsFeed()</code> function call, <code>O(1)</code> time for the remaining methods, and <code>O((N * m) + (N * M) + n)</code> space, where <code>n</code> is the number of <code>followeeIds</code> associated with the <code>userId</code>, <code>m</code> is the maximum number of tweets by any user, <code>N</code> is the total number of <code>userIds</code>, and <code>M</code> is the maximum number of followees for any user.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
Can you think of a data structure to store all the information, such as <code>userIds</code> and corresponding <code>followeeIds</code>, or <code>userIds</code> and their tweets? Maybe you should think of a hash data structure in terms of key-value pairs. Also, can you think of a way to determine that a tweet was posted before another tweet?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We use a hash map <code>followMap</code> to store <code>userIds</code> and their unique <code>followeeIds</code> as a <code>hash set</code>. Another hash map, <code>tweetMap</code>, stores <code>userIds</code> and their tweets as a list of <code>(count, tweetId)</code> pairs. A counter <code>count</code>, incremented with each tweet, tracks the order of tweets. The variable <code>count</code> is helpful in distinguishing the time of tweets from two users. This way of storing data makes the functions <code>follow()</code>, <code>unfollow()</code>, and <code>postTweet()</code> run in <code>O(1)</code>. Can you think of a way to implement <code>getNewsFeed()</code>? Maybe consider a brute force approach and try to optimize it.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
A naive solution would involve taking the tweets of the userId and its followeeIds into a list, sorting them in descending order based on their <code>count</code> values, and returning the top <code>10</code> tweets as the most recent ones. Can you think of a more efficient approach that avoids collecting all tweets and sorting? Perhaps consider a data structure and leverage the fact that each user's individual tweets list is already sorted.
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use a Max-Heap to efficiently retrieve the top <code>10</code> most recent tweets. For each followee and the userId, we insert their most recent tweet from the <code>tweetMap</code> into the heap, along with the tweet's <code>count</code> and its index in the tweet list. This index is necessary because after processing a tweet, we can insert the next most recent tweet from the same user's list. By always pushing and popping tweets from the heap, we ensure that the <code>10</code> most recent tweets are retrieved without sorting all tweets.
38+
</p>
39+
</details>

‎hints/islands-and-treasure.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the given grid.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute force solution would be to iterate on each land cell and run a BFS from that cells to find the nearest treasure chest. This would be an <code>O((m * n)^2)</code> solution. Can you think of a better way? Sometimes it is not optimal to go from source to destination.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can see that instead of going from every cell to find the nearest treasure chest, we can do it in reverse. We can just do a BFS from all the treasure chests in grid and just explore all possible paths from those chests. Why? Because in this approach, the treasure chests self mark the cells level by level and the level number will be the distance from that cell to a treasure chest. We don't revisit a cell. This approach is called <code>Multi-Source BFS</code>. How would you implement it?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We insert all the cells <code>(row, col)</code> that represent the treasure chests into the queue. Then, we process the cells level by level, handling all the current cells in the queue at once. For each cell, we mark it as visited and store the current level value as the distance at that cell. We then try to add the neighboring cells (adjacent cells) to the queue, but only if they have not been visited and are land cells.
30+
</p>
31+
</details>

‎hints/max-area-of-island.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the grid.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
An island is a group of <code>1</code>'s in which every <code>1</code> is reachable from any other <code>1</code> in that group. Can you think of an algorithm that can find the number of groups by visiting a group only once? Maybe there is a recursive way of doing it.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (DFS) algorithm to traverse each group by starting at a cell with <code>1</code> and recursively visiting all the cells that are reachable from that cell and are also <code>1</code>. Can you think about how to find the area of that island? How would you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We traverse the grid, and when we encounter a <code>1</code>, we initialize a variable <code>area</code>. We then start a DFS from that cell to visit all connected <code>1</code>'s recursively, marking them as <code>0</code> to indicate they are visited. At each recursion step, we increment <code>area</code>. After completing the DFS, we update <code>maxArea</code>, which tracks the maximum area of an island in the grid, if <code>maxArea < area</code>. Finally, after traversing the grid, we return <code>maxArea</code>.
30+
</p>
31+
</details>

‎hints/pacific-atlantic-water-flow.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the grid.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute force solution would be to traverse each cell in the grid and run a BFS from each cell to check if it can reach both oceans. This would result in an <code>O((m * n)^2)</code> solution. Can you think of a better way? Maybe you should consider a reverse way of traversing.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (DFS) algorithm starting from the border cells of the grid. However, we reverse the condition such that the next visiting cell should have a height greater than or equal to the current cell. For the top and left borders connected to the Pacific Ocean, we use a hash set called <code>pacific</code> and run a DFS from each of these cells, visiting nodes recursively. Similarly, for the bottom and right borders connected to the Atlantic Ocean, we use a hash set called <code>atlantic</code> and run a DFS. The required coordinates are the cells that exist in both the <code>pacific</code> and <code>atlantic</code> sets. How do you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We perform DFS from the border cells, using their respective hash sets. During the DFS, we recursively visit the neighbouring cells that are unvisited and have height greater than or equal to the current cell's height and add the current cell's coordinates to the corresponding hash set. Once the DFS completes, we traverse the grid and check if a cell exists in both the hash sets. If so, we add that cell to the result list.
30+
</p>
31+
</details>

‎hints/rotting-fruit.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the given grid.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
The DFS algorithm is not suitable for this problem because it explores nodes deeply rather than level by level. In this scenario, we need to determine which oranges rot at each second, which naturally fits a level-by-level traversal. Can you think of an algorithm designed for such a traversal?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Breadth First Search (BFS) algorithm. At each second, we rot the oranges that are adjacent to the rotten ones. So, we store the rotten oranges in a queue and process them in one go. The time at which a fresh orange gets rotten is the level at which it is visited. How would you implement it?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We traverse the grid and store the rotten oranges in a queue. We then run a BFS, processing the current level of rotten oranges and visiting the adjacent cells of each rotten orange. We only insert the adjacent cell into the queue if it contains a fresh orange. This process continues until the queue is empty. The level at which the BFS stops is the answer. However, we also need to check whether all oranges have rotted by traversing the grid. If any fresh orange is found, we return <code>-1</code>; otherwise, we return the level.
30+
</p>
31+
</details>

‎hints/surrounded-regions.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the matrix.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
We observe that we need to capture the regions that are not connected to the <code>O</code>'s on the border of the matrix. This means there should be no path connecting the <code>O</code>'s on the border to any <code>O</code>'s in the region. Can you think of a way to check the region connected to these border <code>O</code>'s?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (<code>DFS</code>) algorithm. Instead of checking the region connected to the border <code>O</code>'s, we can reverse the approach and mark the regions that are reachable from the border <code>O</code>'s. How would you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We run the DFS from every <code>'O'</code> on the border of the matrix, visiting the neighboring cells that are equal to <code>'O'</code> recursively and marking them as <code>'#'</code> to avoid revisiting. After completing all the DFS calls, we traverse the matrix again and capture the cells where <code>matrix[i][j] == 'O'</code>, and unmark the cells back to <code>'O'</code> where <code>matrix[i][j] == '#'</code>.
30+
</p>
31+
</details>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp