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

Commit357b76b

Browse files
authored
Sri Hari: Batch-3/Neetcode-150/Added hints (neetcode-gh#3740)
* Batch-3/Neetcode-150/Added hints* Batch-3/Neetcode-150/Added hints* Batch-3/Neetcode-150/Added hints
1 parent72e7e01 commit357b76b

14 files changed

+425
-6
lines changed

‎articles/is-anagram.md‎

Lines changed: 11 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -116,8 +116,10 @@ class Solution {
116116

117117
###Time & Space Complexity
118118

119-
* Time complexity: $O(n \log n)$
120-
* Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.
119+
* Time complexity: $O(n \log n + m \log m)$
120+
* Space complexity: $O(1)$ or $O(n + m)$ depending on the sorting algorithm.
121+
122+
>Where $n$ is the length of string $s$ and $m$ is the length of string $t$.
121123
122124
---
123125

@@ -268,9 +270,11 @@ class Solution {
268270

269271
###Time & Space Complexity
270272

271-
* Time complexity: $O(n)$
273+
* Time complexity: $O(n + m)$
272274
* Space complexity: $O(1)$
273275

276+
>Where $n$ is the length of string $s$ and $m$ is the length of string $t$.
277+
274278
---
275279

276280
##3. Hash Table (Optimal)
@@ -434,5 +438,7 @@ class Solution {
434438

435439
###Time & Space Complexity
436440

437-
* Time complexity: $O(n)$
438-
* Space complexity: $O(1)$
441+
* Time complexity: $O(n + m)$
442+
* Space complexity: $O(1)$
443+
444+
>Where $n$ is the length of string $s$ and $m$ is the length of string $t$.

‎hints/anagram-groups.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)</code> space, where <code>m</code> is the number of strings and <code>n</code> is the length of the longest string.
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 each string and group them using a hash map. This would be an <code>O(m * nlogn)</code> solution. Though this solution is acceptable, can you think of a better way without sorting the strings?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
By the definition of an anagram, we only care about the frequency of each character in a string. How is this helpful in solving the problem?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
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. Then, we can use this array as the key in the hash map to group the strings.
30+
</p>
31+
</details>

‎hints/duplicate-integer.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
<br>
22
<detailsclass="hint-accordion">
33
<summary>Recommended Time & Space Complexity</summary>
4-
<p>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.
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 size of the input array.
56
</p>
67
</details>
78

‎hints/is-anagram.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 + m)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the string <code>s</code> and <code>m</code> is the length of the string <code>t</code>.
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 sort the given strings and check for their equality. This would be an <code>O(nlogn + mlogm)</code> solution. Though this solution is acceptable, can you think of a better way without sorting the given strings?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
By the definition of the anagram, we can rearrange the characters. Does the order of characters matter in both the strings? Then what matters?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can just consider maintaining the frequency of each character. We can do this by having two separate hash tables for the two strings. Then, we can check whether the frequency of each character in string <code>s</code> is equal to that in string <code>t</code> and vice versa.
30+
</p>
31+
</details>

‎hints/is-palindrome.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 input string.
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 create a copy of the string, reverse it, and then check for equality. This would be an <code>O(n)</code> solution with extra space. Can you think of a way to do this without <code>O(n)</code> space?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Can you find the logic by observing the definition of pallindrome or from the brute force solution?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
A palindrome string is a string that is read the same from the start as well as from the end. This means the character at the start should match the character at the end at the same index. We can use the two pointer algorithm to do this efficiently.
30+
</p>
31+
</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)</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 brute force solution would be to consider every element from the array as the start of the sequence and count the length of the sequence formed with that starting element. This would be an <code>O(n^2)</code> solution. Can you think of a better way?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Is there any way to identify the start of a sequence? For example, in <code>[1, 2, 3, 10, 11, 12]</code>, only <code>1</code> and <code>10</code> are the beginning of a sequence. Instead of trying to form a sequence for every number, we should only consider numbers like <code>1</code> and <code>10</code>.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can consider a number <code>num</code> as the start of a sequence if and only if <code>num - 1</code> does not exist in the given array. We iterate through the array and only start building the sequence if it is the start of a sequence. This avoids repeated work. We can use a hash set for <code>O(1)</code> lookups by converting the array to a hash set.
30+
</p>
31+
</details>

‎hints/max-water-container.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 brute force solution would be to try all pairs of bars in the array, compute the water for each pair, and return the maximum water among all pairs. This would be an <code>O(n^2)</code> solution. Can you think of a better way?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Can you think of an algorithm that runs in linear time and is commonly used in problems that deal with pairs of numbers? Find a formula to calculate the amount of water when we fix two heights.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use the two pointer algorithm. One pointer is at the start and the other at the end. At each step, we calculate the amount of water using the formula <code>(j - i) * min(heights[i], heights[j])</code>. Then, we move the pointer that has the smaller height value. Can you think why we only move the pointer at smaller height?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
In the formula, the amount of water depends only on the minimum height. Therefore, it is appropriate to replace the smaller height value.
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+
A brute-force solution would be to iterate through the array with index <code>i</code> and compute the product of the array except for that index element. This would be an <code>O(n^2)</code> solution. Can you think of a better way?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Is there a way to avoid the repeated work? Maybe we can store the results of the repeated work in an array.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use the prefix and suffix technique. First, we iterate from left to right and store the prefix products for each index in a prefix array, excluding the current index's number. Then, we iterate from right to left and store the suffix products for each index in a suffix array, also excluding the current index's number. Can you figure out the solution from here?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use the stored prefix and suffix products to compute the result array by iterating through the array and simply multiplying the prefix and suffix products at each index.
38+
</p>
39+
</details>

‎hints/string-encode-and-decode.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)</code> time and <code>O(1)</code> space for each <code>encode()</code> and <code>decode()</code> call, where <code>m</code> is the sum of lengths of all the strings.
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 use a non-ascii character as a delimiter. Can you think of a better way?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Try to encode and decode the strings using a smart approach based on the lengths of each string. How can you differentiate between the lengths and any numbers that might be present in the strings?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use an encoding approach where we start with a number representing the length of the string, followed by a separator character (let's use <code>#</code> for simplicity), and then the string itself. To decode, we read the number until we reach a <code>#</code>, then use that number to read the specified number of characters as the string.
30+
</p>
31+
</details>

‎hints/three-integer-sum.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(n^2)</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 brute force solution would be to check for every triplet in the array. This would be an <code>O(n^3)</code> solution. Can you think of a better way?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Can you think of an algorithm after sorting the input array? What can we observe by rearranging the given equation in the problem?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
we can iterate through nums with index <code>i</code> and get <code>nums[i] = -(nums[j] + nums[k])</code> after rearranging the equation, making <code>-nums[i] = nums[j] + nums[k]</code>. For each index <code>i</code>, we should efficiently calculate the <code>j</code> and <code>k</code> pairs without duplicates. Which algorithm is suitable to find <code>j</code> and <code>k</code> pairs?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
To efficiently find the <code>j</code> and <code>k</code> pairs, we run the two pointer approach on the elements to the right of index <code>i</code> as the array is sorted. When we run two pointer algorithm, consider <code>j</code> and <code>k</code> as pointers (<code>j</code> is at left, <code>k</code> is at right) and <code>target = -nums[i]</code>, if the current sum <code>num[j] + nums[k] < target</code> then we need to increase the value of current sum by incrementing <code>j</code> pointer. Else if the current sum <code>num[j] + nums[k] > target</code> then we should decrease the value of current sum by decrementing <code>k</code> pointer. How do you deal with duplicates?
38+
</p>
39+
</details>
40+
41+
<br>
42+
<detailsclass="hint-accordion">
43+
<summary>Hint 5</summary>
44+
<p>
45+
When the current sum <code>nums[j] + nums[k] == target</code> add this pair to the result. We can move <code>j</code> or <code>k</code> pointer until <code>j < k</code> and the pairs are repeated. This ensures that no duplicate pairs are added to the result.
46+
</p>
47+
</details>

0 commit comments

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