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

Commit4096598

Browse files
authored
Batch-3/Neetcode-150/Added hints (neetcode-gh#3744)
1 parent864a32a commit4096598

10 files changed

+326
-0
lines changed

‎hints/balanced-binary-tree.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(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute force solution would involve traversing every node and checking whether the tree rooted at each node is balanced by computing the heights of its left and right subtrees. This approach would result in an <code>O(n^2)</code> solution. Can you think of a more efficient way? Perhaps you could avoid repeatedly computing the heights for every node by determining balance and height in a single traversal.
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 compute the heights at each node. While calculating the heights of the left and right subtrees, we also check if the tree rooted at the current node is balanced. If <code>leftHeight - rightHeight > 1</code>, we update a global variable, such as <code>isBalanced = False</code>. After traversing all the nodes, the value of <code>isBalanced</code> indicates whether the entire tree is balanced or not.
22+
</p>
23+
</details>

‎hints/binary-tree-diameter.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 and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
The diameter of a binary tree is the maximum among the sums of the left height and right height of the nodes in the tree. Why?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Because the diameter of a binary tree is defined as the longest path between any two nodes in the tree. The path may or may not pass through the root. For any given node, the longest path that passes through it is the sum of the height of its left subtree and the height of its right subtree.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
A brute force solution would be to go through every node in the tree and compute its left height and right height, returning the maximum diameter found. This would be an <code>O(n^2)</code> solution. Can you think of a better way? Maybe we can compute the diameter as we calculate the height of the tree? Think about what information you need from each subtree during a single traversal.
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use the Depth First Search (DFS) algorithm to calculate the height of the tree. At each node, the subtrees return their respective heights (leftHeight and rightHeight). Then we calculate the diameter at that node as <code>d = leftHeight + rightHeight</code>. We use a global variable to update the maximum diameter as needed during the traversal.
38+
</p>
39+
</details>

‎hints/depth-of-binary-tree.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(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
From the definition of binary tree's maximum depth, Can you think of a way to achieve this recursively? Maybe you should consider the max depth of the subtrees first before computing the maxdepth at the root.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We use the Depth First Search (DFS) algorithm to find the maximum depth of a binary tree, starting from the <code>root</code>. For the subtrees rooted at the <code>left</code> and <code>right</code> children of the <code>root</code> node, we calculate their maximum depths recursively going through <code>left</code> and <code>right</code> subtrees. We return <code>1 + max(leftDepth, rightDepth)</code>. Why?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
The <code>+1</code> accounts for the current node, as it contributes to the current depth in the recursion call. We pass the maximum depth from the current node's left and right subtrees to its parent because the current maximum depth determines the longest path from the parent to a leaf node through this subtree.
30+
</p>
31+
</details>

‎hints/find-duplicate-integer.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 and <code>O(1)</code> space, where <code>n</code> is the size of the input array.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A naive approach would be to use a hash set, which takes <code>O(1)</code> time to detect duplicates. Although this solution is acceptable, it requires <code>O(n)</code> extra space. Can you think of a better solution that avoids using extra space? Consider that the elements in the given array <code>nums</code> are within the range <code>1</code> to <code>len(nums)</code>.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the given input array itself as a hash set without creating a new one. This can be achieved by marking the positions (<code>0</code>-indexed) corresponding to the elements that have already been encountered. Can you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We iterate through the array using index <code>i</code>. For each element, we use its absolute value to find the corresponding index and mark that position as negative: <code>nums[abs(nums[i]) - 1] *= -1</code>. Taking absolute value ensures we work with the original value even if it’s already negated. How can you detect duplicates?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
For example, in the array <code>[2, 1, 2, 3]</code>, where <code>2</code> is repeated, we mark the index corresponding to each element as negative. If we encounter a number whose corresponding position is already negative, it means the number is a duplicate, and we return it.
38+
</p>
39+
</details>

‎hints/invert-a-binary-tree.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(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
From the diagram, you can see that the left and right children of every node in the tree are swapped. Can you think of a way to achieve this recursively? Maybe an algorithm that is helpful to traverse the tree.
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. At each node, we swap its left and right children by swapping their pointers. This inverts the current node, but every node in the tree also needs to be inverted. To achieve this, we recursively visit the left and right children and perform the same operation. If the current node is <code>null</code>, we simply return.
22+
</p>
23+
</details>
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(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the given list.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A naive approach would be to use a hash set, which takes <code>O(1)</code> time to detect duplicates. Although this solution is acceptable, it requires <code>O(n)</code> extra space. Can you think of a better solution that avoids using extra space? Maybe there is an efficient algorithm which uses two pointers.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the fast and slow pointers technique, which is primarily used to detect cycles in a linked list. We iterate through the list using two pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If the list has a cycle, these two pointers will eventually meet. Why does this work?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
When there is no cycle in the list, the loop ends when the fast pointer becomes <code>null</code>. If a cycle exists, the fast pointer moves faster and continuously loops through the cycle. With each step, it reduces the gap between itself and the slow pointer by one node. For example, if the gap is <code>10</code>, the slow pointer moves by <code>1</code>, increasing the gap to <code>11</code>, while the fast pointer moves by <code>2</code>, reducing the gap to <code>9</code>. This process continues until the fast pointer catches up to the slow pointer, confirming a cycle.
30+
</p>
31+
</details>

‎hints/lru-cache.md‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
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(1)</code> time for each <code>put()</code> and <code>get()</code> function call and an overall space of <code>O(n)</code>, where <code>n</code> is the capacity of the <code>LRU</code> cache.
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 for storing data in key-value pairs? Maybe a hash-based data structure with unique keys.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a hash map which takes <code>O(1)</code> time to get and put the values. But, how can you deal with the least recently used to be removed criteria as a key is updated by the <code>put()</code> or recently used by the <code>get()</code> functions? Can you think of a data structure to store the order of values?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
A brute-force solution would involve maintaining the order of key-value pairs in an array list, performing operations by iterating through the list to erase and insert these key-value pairs. However, this would result in an <code>O(n)</code> time complexity. Can you think of a data structure that allows removing and reinserting elements in <code>O(1)</code> time?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use a doubly-linked list, which allows us to remove a node from the list when we have the address of that node. Can you think of a way to store these addresses so that we can efficiently remove or update a key when needed?
38+
</p>
39+
</details>
40+
41+
<br>
42+
<detailsclass="hint-accordion">
43+
<summary>Hint 5</summary>
44+
<p>
45+
We can use a doubly linked list where key-value pairs are stored as nodes, with the least recently used (LRU) node at the head and the most recently used (MRU) node at the tail. Whenever a key is accessed using <code>get()</code> or <code>put()</code>, we remove the corresponding node and reinsert it at the tail. When the cache reaches its capacity, we remove the LRU node from the head of the list. Additionally, we use a hash map to store each key and the corresponding address of its node, enabling efficient operations in <code>O(1)</code> time.
46+
</p>
47+
</details>
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 as good or better than <code>O(n * k)</code> time and <code>O(1)</code> space, where <code>k</code> is the total number of lists and <code>n</code> is the total number of nodes across all lists.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute-force solution would involve storing all <code>n</code> nodes in an array, sorting them, and converting the array back into a linked list, resulting in an <code>O(nlogn)</code> time complexity. Can you think of a better way? Perhaps consider leveraging the idea behind merging two sorted linked lists.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can merge two sorted linked lists without using any extra space. To handle <code>k</code> sorted linked lists, we can iteratively merge each linked list with a resultant merged list. How can you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We iterate through the list array with index <code>i</code>, starting at <code>i = 1</code>. We merge the linked lists using <code>mergeTwoLists(lists[i], lists[i - 1])</code>, which returns the head of the merged list. This head is stored in <code>lists[i]</code>, and the process continues. Finally, the merged list is obtained at the last index, and we return its head.
30+
</p>
31+
</details>

‎hints/reverse-nodes-in-k-group.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(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the given list.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute-force solution would involve storing the linked list node values in an array, reversing the <code>k</code> groups one by one, and then converting the array back into a linked list, requiring extra space of <code>O(n)</code>. Can you think of a better way? Perhaps you could apply the idea of reversing a linked list in-place without using extra space.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can avoid extra space by reversing each group in-place while keeping track of the head of the next group. For example, consider the list <code>[1, 2, 3, 4, 5]</code> with <code>k = 2</code>. First, we reverse the group <code>[1, 2]</code> to <code>[2, 1]</code>. Then, we reverse <code>[3, 4]</code>, resulting in <code>[2, 1, 4, 3, 5]</code>. While reversing <code>[3, 4]</code>, we need to link <code>1</code> to <code>4</code> and also link <code>3</code> to <code>5</code>. How can we efficiently manage these pointers?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We create a dummy node to handle modifications to the head of the linked list, pointing its <code>next</code> pointer to the current head. We then iterate <code>k</code> nodes, storing the address of the next group's head and tracking the tail of the previous group. After reversing the current group, we reconnect it by linking the previous group's tail to the new head and the current group's tail to the next group's head. This process is repeated for all groups, and we return the new head of the linked list.
30+
</p>
31+
</details>

‎hints/same-binary-tree.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(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
Can you think of an algorithm that is used to traverse the tree? Maybe in terms of recursion.
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 the tree. Can you think of a way to simultaneously traverse both the trees?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We traverse both trees starting from their root nodes. At each step in the recursion, we check if the current nodes in both trees are either <code>null</code> or have the same value. If one node is <code>null</code> while the other is not, or if their values differ, we return <code>false</code>. If the values match, we recursively check their <code>left</code> and <code>right</code> subtrees. If any recursive call returns <code>false</code>, the result for the current recursive call is <code>false</code>.
30+
</p>
31+
</details>

0 commit comments

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