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

Commit36317d8

Browse files
authored
Added complexity tags 169-226
1 parent03ecc39 commit36317d8

File tree

22 files changed

+252
-12
lines changed

22 files changed

+252
-12
lines changed

‎build.gradle

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,9 +13,9 @@ repositories {
1313

1414
dependencies {
1515
testImplementation'org.junit.jupiter:junit-jupiter:[5.10.0,)'
16-
testRuntimeOnly'org.junit.platform:junit-platform-launcher'
1716
testImplementation'org.hamcrest:hamcrest-core:[2.2,)'
1817
testImplementation'org.zapodot:embedded-db-junit-jupiter:[2.1.1,)'
18+
testRuntimeOnly'org.junit.platform:junit-platform-launcher'
1919
}
2020

2121
test {

‎src.save/main/java/g0101_0200/s0169_majority_element/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Sorting #Counting
44
// #Divide_and_Conquer #Data_Structure_II_Day_1_Array #Udemy_Famous_Algorithm
5-
// #2022_06_25_Time_1_ms_(100.00%)_Space_45.5_MB_(97.51%)
5+
// #Big_O_Time_O(n)_Space_O(1) #2022_06_25_Time_1_ms_(100.00%)_Space_45.5_MB_(97.51%)
66

77
publicclassSolution {
88
publicintmajorityElement(int[]arr) {
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
**Time Complexity (Big O Time):**
2+
3+
The time complexity of this program is O(n), where n is the length of the input array`arr`. Here's why:
4+
5+
1. The first loop iterates through the entire array once (`for (int i = 1; i < arr.length; i++)`).
6+
- Inside this loop, there are constant-time operations (assignments and comparisons) for each element of the array.
7+
- Therefore, this part has a time complexity of O(n).
8+
9+
2. The second loop also iterates through the entire array once (`for (int j : arr)`).
10+
- Inside this loop, there are constant-time operations (comparisons) for each element of the array.
11+
- Therefore, this part also has a time complexity of O(n).
12+
13+
In summary, both loops together contribute to the linear time complexity O(n).
14+
15+
**Space Complexity (Big O Space):**
16+
17+
The space complexity of this program is O(1), which means it uses a constant amount of extra space. Regardless of the size of the input array, the program only uses a fixed number of variables (`count` and`majority`) to keep track of the majority element.
18+
19+
In summary, the time complexity is O(n), where n is the length of the input array, and the space complexity is O(1), indicating a constant amount of additional memory usage.

‎src.save/main/java/g0101_0200/s0189_rotate_array/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
packageg0101_0200.s0189_rotate_array;
22

33
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Math #Two_Pointers
4-
// #Algorithm_I_Day_2_Two_Pointers #Udemy_Arrays
4+
// #Algorithm_I_Day_2_Two_Pointers #Udemy_Arrays #Big_O_Time_O(n)_Space_O(1)
55
// #2022_06_27_Time_0_ms_(100.00%)_Space_58_MB_(96.22%)
66

77
publicclassSolution {
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
**Time Complexity (Big O Time):**
2+
3+
The time complexity of this program is O(n), where n is the length of the input array`nums`. Here's why:
4+
5+
1. The`reverse` method has a while loop that iterates from`l` to`r`, where`l` and`r` are indices within the array. The number of iterations in this loop is proportional to the size of the subarray being reversed.
6+
7+
2. In the`rotate` method, there are three calls to the`reverse` method:
8+
- The first`reverse` call reverses the subarray from index 0 to`t - 1`, where`t` is calculated as`n - (k % n)`.
9+
- The second`reverse` call reverses the subarray from index`t` to`n - 1`.
10+
- The third`reverse` call reverses the entire array from index 0 to`n - 1`.
11+
12+
All three`reverse` calls have time complexity proportional to the size of the subarray being reversed, and they operate on non-overlapping subarrays. Therefore, the overall time complexity is O(n).
13+
14+
**Space Complexity (Big O Space):**
15+
16+
The space complexity of this program is O(1), indicating that it uses a constant amount of additional memory regardless of the size of the input array. The program performs the rotation in-place, and the space used for variables and computations remains constant.
17+
18+
In summary, the time complexity is O(n), where n is the length of the input array, and the space complexity is O(1), indicating constant space usage.

‎src.save/main/java/g0101_0200/s0198_house_robber/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming
44
// #Algorithm_I_Day_12_Dynamic_Programming #Dynamic_Programming_I_Day_3
5-
// #Level_2_Day_12_Dynamic_Programming #Udemy_Dynamic_Programming
5+
// #Level_2_Day_12_Dynamic_Programming #Udemy_Dynamic_Programming #Big_O_Time_O(n)_Space_O(n)
66
// #2022_06_28_Time_0_ms_(100.00%)_Space_39.9_MB_(85.30%)
77

88
publicclassSolution {
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
**Time Complexity (Big O Time):**
2+
3+
The time complexity of this program is O(n), where n is the length of the input array`nums`. Here's why:
4+
5+
1. The program iterates through the`nums` array once in a loop that runs from 2 to`n - 1`, where n is the length of the array. This loop computes the maximum profit that can be obtained up to each house.
6+
7+
2. In each iteration of the loop, the program calculates`profit[i]` based on the previous two values:`profit[i - 1]` and`profit[i - 2]`. These calculations are done in constant time for each house.
8+
9+
3. Therefore, the total number of operations in the loop is proportional to the length of the`nums` array, resulting in a time complexity of O(n).
10+
11+
**Space Complexity (Big O Space):**
12+
13+
The space complexity of this program is O(n), where n is the length of the input array`nums`. Here's why:
14+
15+
1. The program creates an integer array`profit` of the same length as`nums` to store the maximum profit at each house. Therefore, the space required for the`profit` array is O(n).
16+
17+
2. In addition to the`profit` array, the program uses a constant amount of space for other variables and calculations. These additional space requirements are independent of the size of the input and can be considered O(1).
18+
19+
3. Overall, the dominant factor in space complexity is the`profit` array, resulting in a space complexity of O(n).
20+
21+
In summary, the time complexity of the program is O(n) because it iterates through the input array once, and the space complexity is also O(n) due to the`profit` array used to store intermediate results.

‎src.save/main/java/g0101_0200/s0200_number_of_islands/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44
// #Breadth_First_Search #Matrix #Union_Find
55
// #Algorithm_II_Day_6_Breadth_First_Search_Depth_First_Search
66
// #Graph_Theory_I_Day_1_Matrix_Related_Problems #Level_1_Day_9_Graph/BFS/DFS #Udemy_Graph
7-
// #2022_06_28_Time_3_ms_(97.76%)_Space_57.5_MB_(41.23%)
7+
// #Big_O_Time_O(M*N)_Space_O(M*N) #2022_06_28_Time_3_ms_(97.76%)_Space_57.5_MB_(41.23%)
88

99
publicclassSolution {
1010
publicintnumIslands(char[][]grid) {
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
**Time Complexity (Big O Time):**
2+
3+
The time complexity of this program is O(M * N), where M is the number of rows and N is the number of columns in the grid. Here's why:
4+
5+
1. The program uses a nested loop to iterate through each cell of the 2D grid, where the outer loop runs from 0 to the number of rows (M) and the inner loop runs from 0 to the number of columns (N). This results in a total of M * N iterations.
6+
7+
2. For each cell, the program performs a depth-first search (DFS) operation, which may recursively visit adjacent cells if they are part of the same island. The DFS operation has constant time complexity for each cell since it visits each cell once.
8+
9+
3. Therefore, the overall time complexity is O(M * N) since the program performs DFS for each cell in the grid.
10+
11+
**Space Complexity (Big O Space):**
12+
13+
The space complexity of this program is O(1) in terms of auxiliary space (additional data structures) and O(M * N) in terms of stack space due to recursive function calls. Here's why:
14+
15+
1. The program uses a constant amount of auxiliary space for variables like`islands`,`x`, and`y`. These variables do not depend on the size of the input grid and can be considered O(1).
16+
17+
2. The recursive DFS calls result in stack space usage proportional to the depth of the recursion, which is determined by the size of the island being explored. In the worst case, if the entire grid is one large island, the stack space can be as large as M * N.
18+
19+
3. Overall, the space complexity is dominated by the stack space used during DFS, and it can be represented as O(M * N) in the worst case.
20+
21+
In summary, the time complexity is O(M * N) because the program iterates through each cell in the grid, and the space complexity is O(1) for auxiliary space and O(M * N) for stack space used during recursive DFS calls.

‎src.save/main/java/g0201_0300/s0206_reverse_linked_list/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Linked_List #Recursion
44
// #Data_Structure_I_Day_8_Linked_List #Algorithm_I_Day_10_Recursion_Backtracking
5-
// #Level_1_Day_3_Linked_List #Udemy_Linked_List
5+
// #Level_1_Day_3_Linked_List #Udemy_Linked_List #Big_O_Time_O(N)_Space_O(1)
66
// #2022_06_28_Time_0_ms_(100.00%)_Space_43.9_MB_(7.98%)
77

88
importcom_github_leetcode.ListNode;
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
**Time Complexity (Big O Time):**
2+
3+
The time complexity of this program is O(N), where N is the number of nodes in the linked list. Here's why:
4+
5+
1. The program uses a`while` loop that iterates through the linked list once, visiting each node exactly once. Therefore, the number of iterations in the loop is proportional to the number of nodes in the list, which is N.
6+
7+
2. Inside the loop, there are constant-time operations. Assignments and pointer adjustments such as`curr.next = prev` take constant time regardless of the list's size.
8+
9+
3. Overall, the time complexity is linear, O(N), because the program performs a constant amount of work for each node in the list.
10+
11+
**Space Complexity (Big O Space):**
12+
13+
The space complexity of this program is O(1), which means it uses a constant amount of additional space regardless of the size of the input linked list. Here's why:
14+
15+
1. The program uses a constant number of variables (`prev`,`curr`,`next`), and the space required for these variables does not depend on the size of the linked list. Therefore, the space complexity is O(1) for auxiliary space.
16+
17+
2. The program does not create any data structures or arrays whose space requirements depend on the size of the input.
18+
19+
In summary, the time complexity is O(N) because the program iterates through the linked list once, and the space complexity is O(1) because it uses a constant amount of additional space for variables.

‎src.save/main/java/g0201_0300/s0207_course_schedule/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
packageg0201_0300.s0207_course_schedule;
22

33
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search
4-
// #Breadth_First_Search #Graph #Topological_Sort
4+
// #Breadth_First_Search #Graph #Topological_Sort #Big_O_Time_O(N)_Space_O(N)
55
// #2022_06_28_Time_3_ms_(97.58%)_Space_48.2_MB_(49.51%)
66

77
importjava.util.ArrayList;
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
**Time Complexity (Big O Time):**
2+
3+
1. The program constructs an adjacency list representation of the directed graph, where each course is a node and prerequisites define edges. Constructing this graph takes O(E) time, where E is the number of prerequisites (edges). In the worst case, E can be proportional to the number of courses (N), so this step is O(N).
4+
5+
2. The program performs a depth-first search (DFS) on the graph to detect cycles. In the worst case, the DFS may visit all nodes, which is O(N).
6+
7+
3. Within the DFS, for each node, the program explores all of its neighbors. In the worst case, this exploration takes O(N) time.
8+
9+
4. Combining all these steps, the overall time complexity is O(N) + O(N) + O(N) = O(N).
10+
11+
So, the time complexity of this program is O(N).
12+
13+
**Space Complexity (Big O Space):**
14+
15+
1. The program uses additional space for several data structures:
16+
-`adj`: An adjacency list representation of the graph. In the worst case, it has O(E) space, which can be proportional to O(N) in certain scenarios.
17+
-`colors`: An array to keep track of the colors (WHITE, GRAY, BLACK) of nodes. This array requires O(N) space.
18+
- Recursive function call stack for DFS, which can go up to O(N) in the worst case when there are no cycles.
19+
20+
2. Ignoring constant factors and smaller terms, the dominant space complexity factors are O(N).
21+
22+
So, the space complexity of this program is O(N).
23+
24+
In summary, the program has a time complexity of O(N) and a space complexity of O(N), where N is the number of courses or nodes in the graph.

‎src.save/main/java/g0201_0300/s0208_implement_trie_prefix_tree/Trie.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,9 @@
11
packageg0201_0300.s0208_implement_trie_prefix_tree;
22

33
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table #Design #Trie
4-
// #Level_2_Day_16_Design #Udemy_Trie_and_Heap #2022_06_28_Time_34_ms_(99.90%)_Space_51_MB_(94.92%)
4+
// #Level_2_Day_16_Design #Udemy_Trie_and_Heap
5+
// #Big_O_Time_O(word.length())_or_O(prefix.length())_Space_O(N)
6+
// #2022_06_28_Time_34_ms_(99.90%)_Space_51_MB_(94.92%)
57

68
@SuppressWarnings("java:S1104")
79
publicclassTrie {
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
**Time Complexity (Big O Time):**
2+
3+
1.**Insertion (insert):**
4+
- In the`insert` method, the program iterates through the characters of the input word, and for each character, it follows the corresponding child node in the Trie.
5+
- The number of iterations depends on the length of the word, which is O(word.length()).
6+
- Since each character is processed once, the insertion of a single word takes O(word.length()) time.
7+
8+
2.**Search (search):**
9+
- In the`search` method, the program iterates through the characters of the input word, following the corresponding child nodes in the Trie.
10+
- The number of iterations depends on the length of the word, which is O(word.length()).
11+
- In the worst case, when the Trie contains a large number of words with the same prefix, searching for a word could take O(word.length()) time.
12+
13+
3.**StartsWith (startsWith):**
14+
- The`startsWith` method calls the`search` method to find whether any word starts with the given prefix.
15+
- This is similar to the search operation and also takes O(prefix.length()) time.
16+
17+
Overall, the time complexity for insertion, search, and startsWith operations in the Trie is O(word.length()) or O(prefix.length()), depending on the length of the word or prefix being processed.
18+
19+
**Space Complexity (Big O Space):**
20+
21+
1.**TrieNode Array (children):**
22+
- The Trie is represented using a tree structure where each node (TrieNode) has an array of children (of size 26 for lowercase English letters).
23+
- In the worst case, where all words are distinct and there are no common prefixes, the Trie would have a node for each character in all words.
24+
- The space complexity for the TrieNode array is O(N), where N is the total number of characters in all inserted words.
25+
26+
2.**Recursive Call Stack:**
27+
- During insertion and search operations, the program uses recursion, which results in a function call stack.
28+
- The depth of the call stack is bounded by the length of the word or prefix being processed.
29+
- In the worst case, this depth can be O(word.length()) or O(prefix.length()).
30+
31+
3.**Other Variables:**
32+
- The`root` variable is a constant space requirement.
33+
- The`startWith` variable is also constant space.
34+
35+
The dominant factor in the space complexity is typically the TrieNode array, which is O(N), where N is the total number of characters in all inserted words.
36+
37+
In summary, the space complexity of this Trie implementation is O(N), and the time complexity for insertion, search, and startsWith operations is O(word.length()) or O(prefix.length()), depending on the length of the word or prefix being processed.
38+
8

‎src.save/main/java/g0201_0300/s0215_kth_largest_element_in_an_array/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Sorting #Heap_Priority_Queue
44
// #Divide_and_Conquer #Quickselect #Data_Structure_II_Day_20_Heap_Priority_Queue
5-
// #2022_07_02_Time_5_ms_(70.82%)_Space_45.1_MB_(24.69%)
5+
// #Big_O_Time_O(n*log(n))_Space_O(log(n)) #2022_07_02_Time_5_ms_(70.82%)_Space_45.1_MB_(24.69%)
66

77
importjava.util.Arrays;
88

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
**Time Complexity (Big O Time):**
2+
3+
1.**Sorting (Arrays.sort):**
4+
- The primary operation in this program is sorting the input array`nums` using the built-in sorting algorithm.
5+
- The time complexity of the sorting operation in Java's`Arrays.sort` is O(n * log(n)), where "n" is the number of elements in the array.
6+
- Sorting is the most time-consuming step in this algorithm.
7+
8+
2.**Accessing the kth Largest Element:**
9+
- After sorting, accessing the kth largest element by index (nums[n - k]) takes constant time, O(1).
10+
11+
Overall, the dominant factor in terms of time complexity is the sorting step, which is O(n * log(n)).
12+
13+
**Space Complexity (Big O Space):**
14+
15+
1.**Sorting Space:**
16+
- The space complexity for the sorting algorithm used by`Arrays.sort` is typically O(log(n)) for the stack space required for recursion or iteration.
17+
18+
2.**Other Variables:**
19+
- The`int n` variable, which stores the length of the input array, takes constant space (O(1)).
20+
- The sorted array`nums` is modified in place, so it does not contribute to additional space complexity.
21+
22+
In summary, the space complexity is mainly determined by the space required for the sorting algorithm, which is typically O(log(n)). The time complexity is dominated by the sorting operation, which is O(n * log(n)).

‎src.save/main/java/g0201_0300/s0221_maximal_square/Solution.java

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
packageg0201_0300.s0221_maximal_square;
22

33
// #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Matrix
4-
// #Dynamic_Programming_I_Day_16 #2022_07_04_Time_7_ms_(72.35%)_Space_59.5_MB_(10.55%)
4+
// #Dynamic_Programming_I_Day_16 #Big_O_Time_O(m*n)_Space_O(m*n)
5+
// #2022_07_04_Time_7_ms_(72.35%)_Space_59.5_MB_(10.55%)
56

67
publicclassSolution {
78
publicintmaximalSquare(char[][]matrix) {
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
**Time Complexity (Big O Time):**
2+
3+
1.**Initialization:**
4+
- Initializing the`m` and`n` variables based on the dimensions of the input matrix takes O(1) time.
5+
6+
2.**Dynamic Programming (DP) Table Initialization:**
7+
- Creating a 2D DP table`dp` of size`(m + 1) x (n + 1)` takes O(m * n) time, where "m" and "n" are the dimensions of the input matrix.
8+
9+
3.**DP Table Filling:**
10+
- The program uses nested loops to iterate through each cell of the input matrix.
11+
- For each '1' encountered in the input matrix, it updates the corresponding cell in the DP table based on the minimum value of its neighboring cells (above, left, and diagonal upper-left).
12+
- The nested loops iterate through all cells in the matrix once, and the updates for each cell take constant time.
13+
- Therefore, the time complexity for DP table filling is O(m * n).
14+
15+
4.**Maximum Value Search:**
16+
- During DP table filling, the program keeps track of the maximum value seen (`max`) in the DP table.
17+
- This also takes O(m * n) time since it iterates through all cells once.
18+
19+
Overall, the dominant factor in terms of time complexity is the DP table filling step, which is O(m * n).
20+
21+
**Space Complexity (Big O Space):**
22+
23+
1.**DP Table (`dp`):**
24+
- The space complexity of the DP table is O((m + 1) * (n + 1)), which simplifies to O(m * n) since the additional row and column are added for convenience.
25+
- Therefore, the space complexity is O(m * n) for the DP table.
26+
27+
2.**Other Variables:**
28+
- The space complexity for other variables like`m`,`n`, and`max` is O(1), as they occupy constant space.
29+
30+
In summary, the space complexity is primarily determined by the DP table, which is O(m * n), and the time complexity is dominated by the DP table filling step, also O(m * n).

‎src.save/main/java/g0201_0300/s0226_invert_binary_tree/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
// #Easy #Top_100_Liked_Questions #Depth_First_Search #Breadth_First_Search #Tree #Binary_Tree
44
// #Data_Structure_I_Day_12_Tree #Level_2_Day_6_Tree #Udemy_Tree_Stack_Queue
5-
// #2022_07_04_Time_0_ms_(100.00%)_Space_42_MB_(20.73%)
5+
// #Big_O_Time_O(n)_Space_O(n) #2022_07_04_Time_0_ms_(100.00%)_Space_42_MB_(20.73%)
66

77
importcom_github_leetcode.TreeNode;
88

0 commit comments

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