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

Commit822c53a

Browse files
authored
Sri Hari: Batch-6/Neetcode-150/Added-hints (neetcode-gh#3909)
* Batch-6/Neetcode-150/Added-hints* Batch-6/Neetcode-150/Added-hints* Batch-6/Neetcode-150/Added-hints* Batch-6/Neetcode-150/Added-hints* Batch-6/Neetcode-150/Added-hints
1 parent3a66f08 commit822c53a

File tree

53 files changed

+1594
-28
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

53 files changed

+1594
-28
lines changed

‎articles/counting-bits.md

Lines changed: 18 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -124,8 +124,10 @@ class Solution {
124124

125125
###Time & Space Complexity
126126

127-
* Time complexity: $O(n)$
128-
* Space complexity: $O(1)$
127+
* Time complexity: $O(n \log n)$
128+
* Space complexity:
129+
* $O(1)$ extra space.
130+
* $O(n)$ space for the output array.
129131

130132
---
131133

@@ -248,8 +250,10 @@ class Solution {
248250

249251
###Time & Space Complexity
250252

251-
* Time complexity: $O(n)$
252-
* Space complexity: $O(1)$
253+
* Time complexity: $O(n \log n)$
254+
* Space complexity:
255+
* $O(1)$ extra space.
256+
* $O(n)$ space for the output array.
253257

254258
---
255259

@@ -338,8 +342,10 @@ class Solution {
338342

339343
###Time & Space Complexity
340344

341-
* Time complexity: $O(n)$
342-
* Space complexity: $O(1)$
345+
* Time complexity: $O(n \log n)$
346+
* Space complexity:
347+
* $O(1)$ extra space.
348+
* $O(n)$ space for the output array.
343349

344350
---
345351

@@ -470,7 +476,9 @@ class Solution {
470476
###Time & Space Complexity
471477

472478
* Time complexity: $O(n)$
473-
* Space complexity: $O(1)$
479+
* Space complexity:
480+
* $O(1)$ extra space.
481+
* $O(n)$ space for the output array.
474482

475483
---
476484

@@ -567,4 +575,6 @@ class Solution {
567575
###Time & Space Complexity
568576

569577
* Time complexity: $O(n)$
570-
* Space complexity: $O(1)$
578+
* Space complexity:
579+
* $O(1)$ extra space.
580+
* $O(n)$ space for the output array.

‎articles/insert-new-interval.md

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -221,7 +221,9 @@ class Solution {
221221
###Time & Space Complexity
222222

223223
* Time complexity: $O(n)$
224-
* Space complexity: $O(1)$
224+
* Space complexity:
225+
* $O(1)$ extra space.
226+
* $O(n)$ space for the output list.
225227

226228
---
227229

@@ -515,7 +517,9 @@ class Solution {
515517
###Time & Space Complexity
516518

517519
* Time complexity: $O(n)$
518-
* Space complexity: $O(1)$
520+
* Space complexity:
521+
* $O(1)$ extra space.
522+
* $O(n)$ space for the output list.
519523

520524
---
521525

@@ -708,4 +712,6 @@ class Solution {
708712
###Time & Space Complexity
709713

710714
* Time complexity: $O(n)$
711-
* Space complexity: $O(1)$
715+
* Space complexity:
716+
* $O(1)$ extra space.
717+
* $O(n)$ space for the output list.

‎articles/merge-intervals.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -169,7 +169,9 @@ class Solution {
169169
###Time & Space Complexity
170170

171171
* Time complexity: $O(n \log n)$
172-
* Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.
172+
* Space complexity:
173+
* $O(1)$ or $O(n)$ space depending on the sorting algorithm.
174+
* $O(n)$ for the output list.
173175

174176
---
175177

‎articles/plus-one.md

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -139,7 +139,7 @@ class Solution {
139139

140140
---
141141

142-
##2. Iteration
142+
##2. Iteration - I
143143

144144
::tabs-start
145145

@@ -148,7 +148,7 @@ class Solution:
148148
defplusOne(self,digits: List[int]) -> List[int]:
149149
one=1
150150
i=0
151-
digits= digits[::-1]
151+
digits.reverse()
152152

153153
while one:
154154
if i<len(digits):
@@ -161,7 +161,9 @@ class Solution:
161161
digits.append(one)
162162
one=0
163163
i+=1
164-
return digits[::-1]
164+
165+
digits.reverse()
166+
return digits
165167
```
166168

167169
```java
@@ -344,11 +346,11 @@ class Solution {
344346
###Time & Space Complexity
345347

346348
* Time complexity: $O(n)$
347-
* Space complexity: $O(1)$
349+
* Space complexity: $O(1)$ or $O(n)$ depending on the language.
348350

349351
---
350352

351-
##3. Iteration(Optimal)
353+
##3. Iteration- II
352354

353355
::tabs-start
354356

@@ -479,4 +481,4 @@ class Solution {
479481
###Time & Space Complexity
480482

481483
* Time complexity: $O(n)$
482-
* Space complexity: $O(1)$
484+
* Space complexity: $O(n)$

‎articles/set-zeroes-in-matrix.md

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

213213
###Time & Space Complexity
214214

215-
* Time complexity: $O(m * n)$
215+
* Time complexity: $O((m * n) * (m + n))$
216216
* Space complexity: $O(m * n)$
217217

218218
>Where $m$ is the number of rows and $n$ is the number of columns.

‎articles/spiral-matrix.md

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -203,7 +203,9 @@ class Solution {
203203
###Time & Space Complexity
204204

205205
* Time complexity: $O(m * n)$
206-
* Space complexity: $O(min(m, n))$
206+
* Space complexity:
207+
* $O(min(m, n))$ space for recursion stack.
208+
* $O(m * n)$ space for the output list.
207209

208210
>Where $m$ is the number of rows and $n$ is the number of columns.
209211
@@ -467,7 +469,9 @@ class Solution {
467469
###Time & Space Complexity
468470

469471
* Time complexity: $O(m * n)$
470-
* Space complexity: $O(1)$
472+
* Space complexity:
473+
* $O(1)$ extra space.
474+
* $O(m * n)$ space for the output list.
471475

472476
>Where $m$ is the number of rows and $n$ is the number of columns.
473477
@@ -655,6 +659,8 @@ class Solution {
655659
###Time & Space Complexity
656660

657661
* Time complexity: $O(m * n)$
658-
* Space complexity: $O(1)$
662+
* Space complexity:
663+
* $O(1)$ extra space.
664+
* $O(m * n)$ space for the output list.
659665

660666
>Where $m$ is the number of rows and $n$ is the number of columns.

‎articles/string-encode-and-decode.md

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -286,8 +286,8 @@ class Solution {
286286

287287
###Time & Space Complexity
288288

289-
* Time complexity: $O(m)$ for $encode()$ and $decode()$.
290-
* Space complexity: $O(n)$ for $encode()$ and $decode()$.
289+
* Time complexity: $O(m)$ foreach$encode()$ and $decode()$ function calls.
290+
* Space complexity: $O(m +n)$ foreach$encode()$ and $decode()$ function calls.
291291

292292
>Where $m$ is the sum of lengths of all the strings and $n$ is the number of strings.
293293
@@ -510,7 +510,7 @@ class Solution {
510510

511511
###Time & Space Complexity
512512

513-
* Time complexity: $O(m)$ for $encode()$ and $decode()$.
514-
* Space complexity: $O(1)$ for $encode()$ and $decode()$.
513+
* Time complexity: $O(m)$ foreach$encode()$ and $decode()$ function calls.
514+
* Space complexity: $O(m + n)$ foreach$encode()$ and $decode()$ function calls.
515515

516516
>Where $m$ is the sum of lengths of all the strings and $n$ is the number of strings.

‎articles/subarrays-with-k-different-integers.md

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

247247
---
248248

249-
##3.Slidingt Window (One Pass) - I
249+
##3.Sliding Window (One Pass) - I
250250

251251
::tabs-start
252252

‎hints/burst-balloons.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 ^ 3)</code> time and <code>O(n ^ 2)</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+
Try to simulate the process recursively by passing the array to the recursive function. At each step, iterate through the array, pop an element, and recursively apply the same process to the two subarrays on both sides of the popped element, returning the maximum result from all recursive paths. This approach is exponential. Can you think of a way to optimize it? Maybe you should consider observing the subproblems instead of modifying the array.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Instead of passing the array, we can pass the range of indices <code>l</code> and <code>r</code> that need to be processed. We pad the input array with <code>1</code>s on both sides for easier computation, but <code>l</code> and <code>r</code> represent the first and last indices of the original input array. Can you think of a reverse engineering approach for popping elements?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We determine the result by considering each element as the last one to be popped in the current range. For each element, we calculate its value by multiplying it with the elements at <code>l - 1</code> and <code>r + 1</code>, then recursively solve the subproblems for the ranges <code>(l, i - 1)</code> and <code>(i + 1, r)</code>, where <code>i</code> is the current element in the given range. Can you think of a way to optimize and avoid redundant calculations?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a <code>2D</code> array can be used to store results since the recursive function parameters <code>l</code> and <code>r</code> are within the range of the input array size.
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 as good or better than <code>O(n)</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+
Try to think in terms of recursion and visualize it as a decision tree. Can you determine the possible decisions at each recursion step? Also, can you identify the base cases and the essential information that needs to be tracked during recursion?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
At each recursion step, we can buy only if we haven't already bought a coin, or we can sell if we own one. When buying, we subtract the coin value, and when selling, we add it. We explore all possible buying and selling options recursively, iterating through the coins from left to right using index <code>i</code>. For the cooldown condition, if we buy a coin, we increment the index <code>i</code> by two.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use a boolean variable <code>canBuy</code> to indicate whether buying is allowed at the current recursive step. If we go out of bounds, we return <code>0</code>. This approach is exponential. Can you think of a way to optimize it?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use memoization to cache the results of recursive calls and avoid recalculations. A hash map or a <code>2D</code> array can be used to store these results.
38+
</p>
39+
</details>

‎hints/coin-change-ii.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 as good or better than <code>O(n * a)</code> time and <code>O(n * a)</code> space, where <code>n</code> is the number of coins and <code>a</code> is the given amount.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
As we need to find the total number of combinations, think in terms of recursion and visualize it as a decision tree where multiple coin choices are available at each recursion step. Can you determine a way to allow picking the same coin multiple times? Maybe you should consider the decisions made at each recursion step.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
The given coins are unique. We recursively iterate through the coins array using index <code>i</code>, tracking the collected amount along the current path. At each step, we can either skip the current coin or pick it, ensuring the total does not exceed the target. To allow picking the same coin multiple times, we recurse with the same index but an updated amount, generating different combinations.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
If we reach the target amount, we return <code>1</code>. The recursion stops if the index goes out of bounds. We count all possible ways and return the total. This approach is exponential. Can you think of a way to optimize it? Maybe you should consider an approach to avoid redundant computations.
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a <code>2D</code> array can be used to store these results.
38+
</p>
39+
</details>

‎hints/count-paths.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 as good or better than <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+
Try to think in terms of recursion and visualize it as a decision tree, where we have two choices at each step. Can you determine the base condition and recurrence relation?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We recursively traverse the grid using row <code>i</code> and column <code>j</code>. At each step, we explore both possibilities: moving down or moving right, ensuring we do not go out of bounds. If we reach the bottom-right cell, we return <code>1</code>.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
This approach has exponential complexity. Can you think of a way to optimize the recursion? Maybe you should consider using a dynamic programming approach.
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use memoization to cache the results of recursive calls and avoid recalculations. A hash map or a <code>2D</code> array can be used to store these results.
38+
</p>
39+
</details>

0 commit comments

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