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

Commitdf08b81

Browse files
authored
Sri Hari: Batch-3/Neetcode-150/Added hints (neetcode-gh#3746)
* Batch-3/Neetcode-150/Added hints* Batch-3/Neetcode-150/Added hints
1 parentac2ef79 commitdf08b81

13 files changed

+323
-12
lines changed

‎articles/design-twitter-feed.md‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -325,10 +325,10 @@ class Twitter {
325325

326326
###Time & Space Complexity
327327

328-
* Time complexity: $O(n \logn)$ for $getNewsFeed()$ and $O(1)$ for remaining methods.
329-
* Space complexity: $O(1)$
328+
* Time complexity: $O(n* m + t\logt)$ foreach$getNewsFeed()$ call and $O(1)$ for remaining methods.
329+
* Space complexity: $O(N * m + N * M)$
330330

331-
>Where $n$ is the number of tweets associated with the $useId$ and its $followeeIds$.
331+
>Where $n$ is thetotalnumber of$followeeIds$ associated with the $userId$, $m$ is the maximum number oftweetsby any user, $t$ is the total number of tweetsassociated with the $userId$ and its $followeeIds$, $N$ is the total number of $userIds$ and $M$ is the maximum number of followees for any user.
332332
333333
---
334334

@@ -778,7 +778,7 @@ class Twitter {
778778

779779
###Time & Space Complexity
780780

781-
* Time complexity: $O(n+\log n)$ for $getNewsFeed()$ and $O(1)$ for remaining methods.
782-
* Space complexity: $O(1)$
781+
* Time complexity: $O(n)$ foreach$getNewsFeed()$ call and $O(1)$ for remaining methods.
782+
* Space complexity: $O(N * m + N * M + n)$
783783

784-
>Where $n$ is the number oftweets associated with the $useId$ and its $followeeIds$.
784+
>Where $n$ is thetotalnumber of$followeeIds$ associated with the $userId$, $m$ is the maximum number of tweets by any user, $N$ is the total number of $userIds$ and $M$ is the maximum number of followees for any user.

‎articles/kth-largest-element-in-an-array.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -76,7 +76,7 @@ class Solution {
7676

7777
---
7878

79-
##2. Heap
79+
##2.Min-Heap
8080

8181
::tabs-start
8282

‎articles/kth-largest-integer-in-a-stream.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -135,7 +135,7 @@ class KthLargest(k: Int, nums: IntArray) {
135135

136136
---
137137

138-
##2. Heap
138+
##2.Min-Heap
139139

140140
::tabs-start
141141

‎articles/task-scheduling.md‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -341,7 +341,7 @@ class Solution {
341341
342342
---
343343

344-
##2. Heap
344+
##2.Max-Heap
345345

346346
::tabs-start
347347

@@ -609,7 +609,7 @@ class Solution {
609609
###Time & Space Complexity
610610

611611
* Time complexity: $O(m)$
612-
* Space complexity: $O(m)$
612+
* Space complexity: $O(1)$ since we have at most $26$ different characters.
613613

614614
> Where $m$ is the number of tasks.
615615

@@ -780,7 +780,7 @@ class Solution {
780780
###Time & Space Complexity
781781

782782
* Time complexity: $O(m)$
783-
* Space complexity: $O(1)$
783+
* Space complexity: $O(1)$ since we have at most $26$ different characters.
784784

785785
> Where $m$ is the number of tasks.
786786

@@ -956,6 +956,6 @@ class Solution {
956956
###Time & Space Complexity
957957

958958
* Time complexity: $O(m)$
959-
* Space complexity: $O(1)$
959+
* Space complexity: $O(1)$ since we have at most $26$ different characters.
960960

961961
> Where $m$ is the number of tasks.

‎hints/combination-target-sum.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(2^(t/m))</code> time and <code>O(t/m)</code> space, where <code>t</code> is the given <code>target</code> and <code>m</code> is the minimum value in the given array.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
Can you think of this problem in terms of a decision tree, where at each step, we have <code>n</code> decisions, where <code>n</code> is the size of the array? In this decision tree, we can observe that different combinations of paths are formed. Can you think of a base condition to stop extending a path? Maybe you should consider the target value.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use backtracking to recursively traverse these paths and make decisions to choose an element at each step. We maintain a variable <code>sum</code>, which represents the sum of all the elements chosen in the current path. We stop this recursive path if <code>sum == target</code>, and add a copy of the chosen elements to the result. How do you implement it?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We recursively select elements, increasing the <code>sum</code> and appending the element to the temporary list, which tracks the chosen elements in the current path. At each step, we have the option to consider all elements in the array, but we only proceed with elements that, when added to <code>sum</code>, do not exceed the <code>target</code>. We iterate through the entire array at each step, choosing elements accordingly.
30+
</p>
31+
</details>
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(logn)</code> time for <code>addNum()</code>, <code>O(1)</code> time for <code>findMedian()</code>, and <code>O(n)</code> space, where <code>n</code> is the current number of elements.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A naive solution would be to store the data stream in an array and sort it each time to find the median, resulting in <code>O(nlogn)</code> time for each <code>findMedian()</code> call. Can you think of a better way? Perhaps using a data structure that allows efficient insertion and retrieval of the median can make the solution more efficient.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
If we divide the array into two parts, we can find the median in <code>O(1)</code> if the left half can efficiently return the maximum and the right half can efficiently return the minimum. These values determine the median. However, the process changes slightly if the total number of elements is odd — in that case, the median is the element from the half with the larger size. Can you think of a data structure which is suitable to implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use a Heap (Max-Heap for the left half and Min-Heap for the right half). Instead of dividing the array, we store the elements in these heaps as they arrive in the data stream. But how can you maintain equal halves of elements in these two heaps? How do you implement this?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We initialize a Max-Heap and a Min-Heap. When adding an element, if the element is greater than the minimum element of the Min-Heap, we push it into the Min-Heap; otherwise, we push it into the Max-Heap. If the size difference between the two heaps becomes greater than one, we rebalance them by popping an element from the larger heap and pushing it into the smaller heap. This process ensures that the elements are evenly distributed between the two heaps, allowing us to retrieve the middle element or elements in <code>O(1)</code> time.
38+
</p>
39+
</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(nlogk)</code> time and <code>O(k)</code> space, where <code>n</code> is the size of the input array, and <code>k</code> is the number of points to be returned.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A naive solution would be to sort the array in ascending order based on the distances of the points from the origin <code>(0, 0)</code> and return the first <code>k</code> points. This would take <code>O(nlogn)</code> time. Can you think of a better way? Perhaps you could use a data structure that maintains only <code>k</code> points and allows efficient insertion and removal.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a Max-Heap that keeps the maximum element at its top and allows retrieval in <code>O(1)</code> time. This data structure is ideal because we need to return the <code>k</code> closest points to the origin. By maintaining only <code>k</code> points in the heap, we can efficiently remove the farthest point when the size exceeds <code>k</code>. 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 initialize a Max-Heap that orders points based on their distances from the origin. Starting with an empty heap, we iterate through the array of points, inserting each point into the heap. If the size of the heap exceeds <code>k</code>, we remove the farthest point (the maximum element in the heap). After completing the iteration, the heap will contain the <code>k</code> closest points to the origin. Finally, we convert the heap into an array and return it.
30+
</p>
31+
</details>
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 as good or better than <code>O(nlogk)</code> time and <code>O(k)</code> space, where <code>n</code> is the size of the input array, and <code>k</code> represents the rank of the largest number to be returned (i.e., the <code>k-th</code> largest element).
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A naive solution would be to sort the array in descending order and return the <code>k-th</code> largest element. This would be an <code>O(nlogn)</code> solution. Can you think of a better way? Maybe you should think of a data structure which can maintain only the top <code>k</code> largest elements.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a Min-Heap, which stores elements and keeps the smallest element at its top. When we add an element to the Min-Heap, it takes <code>O(logk)</code> time since we are storing <code>k</code> elements in it. Retrieving the top element (the smallest in the heap) takes <code>O(1)</code> time. How can this be useful for finding the <code>k-th</code> largest element?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
The <code>k-th</code> largest element is the smallest element among the top <code>k</code> largest elements. This means we only need to maintain <code>k</code> elements in our Min-Heap to efficiently determine the <code>k-th</code> largest element. Whenever the size of the Min-Heap exceeds <code>k</code>, we remove the smallest element by popping from the heap. How do you implement this?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We initialize an empty Min-Heap. We iterate through the array and add elements to the heap. When the size of the heap exceeds <code>k</code>, we pop from the heap and continue. After the iteration, the top element of the heap is the <code>k-th</code> largest element.
38+
</p>
39+
</details>
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(mlogk)</code> time and <code>O(k)</code> space, where <code>m</code> is the number of times <code>add()</code> is called, and <code>k</code> represents the rank of the largest number to be tracked (i.e., the <code>k-th</code> largest element).
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 sorting the array in every time a number is added using <code>add()</code>, and then returning the <code>k-th</code> largest element. This would take <code>O(m * nlogn)</code> time, where <code>m</code> is the number of calls to <code>add()</code> and <code>n</code> is the total number of elements added. However, do we really need to track all the elements added, given that we only need the <code>k-th</code> largest element? Maybe you should think of a data structure which can maintain only the top <code>k</code> largest elements.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a Min-Heap, which stores elements and keeps the smallest element at its top. When we add an element to the Min-Heap, it takes <code>O(logk)</code> time since we are storing <code>k</code> elements in it. Retrieving the top element (the smallest in the heap) takes <code>O(1)</code> time. How can this be useful for finding the <code>k-th</code> largest element?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
The <code>k-th</code> largest element is the smallest element among the top <code>k</code> largest elements. This means we only need to maintain <code>k</code> elements in our Min-Heap to efficiently determine the <code>k-th</code> largest element. Whenever the size of the Min-Heap exceeds <code>k</code>, we remove the smallest element by popping from the heap. How do you implement this?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We initialize a Min-Heap with the elements of the input array. When the <code>add()</code> function is called, we insert the new element into the heap. If the heap size exceeds <code>k</code>, we remove the smallest element (the root of the heap). Finally, the top element of the heap represents the <code>k-th</code> largest element and is returned.
38+
</p>
39+
</details>

‎hints/last-stone-weight.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 as good or better than <code>O(nlogn)</code> time and <code>O(n)</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 solution would involve simulating the process by sorting the array at each step and processing the top <code>2</code> heaviest stones, resulting in an <code>O(n * nlogn)</code> time complexity. Can you think of a better way? Consider using a data structure that efficiently supports insertion and removal of elements and maintain the sorted order.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a Max-Heap, which allows us to retrieve the maximum element in <code>O(1)</code> time. We initially insert all the weights into the Max-Heap, which takes <code>O(logn)</code> time per insertion. We then simulate the process until only one or no element remains in the Max-Heap. At each step, we pop two elements from the Max-Heap which takes <code>O(logn)</code> time. If they are equal, we do not insert anything back into the heap and continue. Otherwise, we insert the difference of the two elements back into the heap.
22+
</p>
23+
</details>

0 commit comments

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