packageg0101_0200.s0138_copy_list_with_random_pointer;

importcom_github_leetcode.random.Node;

**Time Complexity (Big O Time):**

1.**First Pass**: In the first pass, the program iterates through the original linked list and creates a cloned node for each node in the original list. This operation takes O(N) time, where N is the number of nodes in the original list, as it processes each node once.

2.**Second Pass**: In the second pass, the program updates the random pointers of the cloned nodes based on the random pointers of the original nodes. This operation also takes O(N) time since it processes each node once.

3.**Third Pass**: In the third pass, the program separates the cloned linked list from the original linked list and restores the original linked list's next pointers. This final pass also takes O(N) time, as it processes each node once.

Overall, the time complexity of the program is O(N), where N is the number of nodes in the linked list. All three passes contribute linearly to the time complexity.

**Space Complexity (Big O Space):**

The space complexity of the program is O(N), where N is the number of nodes in the linked list. Here's how the space is allocated:

1.**Cloned Nodes**: During the first pass, the program creates cloned nodes for each node in the original linked list. This results in N additional nodes, each taking constant space. Therefore, the space used for the cloned nodes is O(N).

2.**Random Pointers**: No additional space is used for random pointers since the program manipulates the existing nodes in the original linked list to connect to their corresponding cloned nodes.

3.**New Head Node**: A single variable`newHead` is used to store the head of the cloned linked list. This variable takes constant space.

4.**Other Variables**: The program uses a few additional variables (`curr`,`clonedNode`) to traverse and manipulate the linked list. These variables take constant space.

Overall, the space complexity is O(N) due to the cloned nodes created during the first pass, which directly corresponds to the number of nodes in the linked list.

importjava.util.HashSet;

**Time Complexity (Big O Time):**

-**HashSet Initialization**: Initializing the`HashSet` with the words from the`wordDict` takes O(M) time, where M is the total length of all words in the dictionary.

-**Maximum Length Calculation**: In the first loop, the program calculates the maximum word length in the`wordDict`. This takes O(M) time, as it iterates through all the words.

-**DFS Function Calls**: The main work is done in the`dfs` function. The function is called multiple times with different`end` values (from 1 to the maximum word length). The number of calls depends on the maximum word length, which we denoted as "max." Therefore, the time complexity of the DFS portion is O(max * N), where N is the length of the input string`s`.

-**Flag Array**: The program uses a`flag` array to memoize subproblem results to avoid redundant work. Initializing this array takes O(N) time since it has a length equal to the length of the input string`s`.

Combining these steps, the overall time complexity of the program is O(M + max * N), where M is the total length of all words in the dictionary, N is the length of the input string`s`, and max is the maximum word length in the dictionary.

**Space Complexity (Big O Space):**

-**HashSet Space**: The`HashSet``set` is used to store the words from the dictionary. It consumes O(M) space, where M is the total length of all words in the dictionary.

-**Flag Array**: The`flag` array is used for memoization, and it has a length equal to the length of the input string`s`, so it consumes O(N) space.

-**DFS Recursive Calls**: The depth of the recursive calls in the`dfs` function can go up to "max," where "max" is the maximum word length in the dictionary. This contributes to the call stack space. Therefore, in the worst case, the space complexity due to recursive calls is O(max).

Combining these space requirements, the overall space complexity of the program is O(M + N + max).

In summary, the time complexity is O(M + max * N), and the space complexity is O(M + N + max), where M is the total length of all words in the dictionary, N is the length of the input string`s`, and max is the maximum word length in the dictionary.

packageg0101_0200.s0141_linked_list_cycle;

importcom_github_leetcode.ListNode;

**Time Complexity (Big O Time):**

- The program uses two pointers,`fast` and`slow`, to traverse the linked list.

- The`fast` pointer moves twice as fast as the`slow` pointer in each iteration.

The key insight here is that if there is a cycle in the linked list, the`fast` and`slow` pointers will eventually meet (i.e.,`fast == slow`). If there is no cycle, the`fast` pointer will reach the end of the list (i.e.,`fast == null` or`fast.next == null`) before the`slow` pointer.

Therefore, the time complexity of this algorithm is O(N), where N is the number of nodes in the linked list. This is because in the worst case, when there is no cycle, both pointers will traverse the entire linked list once.

**Space Complexity (Big O Space):**

The space complexity of this algorithm is O(1), which means it uses a constant amount of extra space regardless of the size of the input linked list. This is because it only uses two additional pointers (`fast` and`slow`) to traverse the list and does not rely on additional data structures or recursion that would consume additional memory.

In summary, the time complexity of this program is O(N), and the space complexity is O(1), where N is the number of nodes in the linked list.

importcom_github_leetcode.ListNode;

**Time Complexity (Big O Time):**

- The program uses two pointers,`fast` and`slow`, to traverse the linked list.

- The first while loop is used to determine if there is a cycle and find the meeting point of`fast` and`slow`. This loop runs until`fast` and`slow` meet inside the loop or reach the end of the list.

If there is no cycle, both pointers will reach the end of the list in O(N) time, where N is the number of nodes in the linked list.

If there is a cycle, the`fast` and`slow` pointers will meet inside the loop. The maximum number of iterations needed to detect the cycle and find the meeting point is less than or equal to N. Therefore, the time complexity remains O(N).

The second while loop is used to find the starting node of the cycle. It starts from the head of the list and moves`slow` and`fast` pointers at the same speed until they meet at the starting node of the cycle. This loop runs in O(N) time.

Overall, the time complexity of this algorithm is O(N).

**Space Complexity (Big O Space):**

The space complexity of this algorithm is O(1), which means it uses a constant amount of extra space regardless of the size of the input linked list. It only uses a few additional pointers (`fast` and`slow`) to traverse the list and does not rely on additional data structures or recursion that would consume additional memory.

In summary, the time complexity of this program is O(N), and the space complexity is O(1), where N is the number of nodes in the linked list.

packageg0101_0200.s0146_lru_cache;

importjava.util.HashMap;

importjava.util.Map;

**Time Complexity (Big O Time):**

1.`get(int key)` Method:

- Accessing an element from the`cacheMap` is done in constant time (O(1)).

- Moving a node to the head in the`moveToHead` method also operates in constant time (O(1)).

- Overall, the`get` method's time complexity is O(1).

2.`put(int key, int value)` Method:

- Updating the value of an existing key in the`cacheMap` is done in constant time (O(1)).

- Adding a new node to the cache is done in constant time if the cache is not full (O(1)).

- If the cache is full, it removes the node at the tail, which is also done in constant time (O(1)).

- Recursively calling the`put` method when the cache is full does not result in nested loops because the eviction operation happens once in each recursion.

- Overall, the`put` method's time complexity is O(1) on average, but in the worst case (when eviction happens multiple times), it can be considered O(N), where N is the capacity of the cache.

3.`moveToHead(LruCacheNode node)` Method:

- Moving a node to the head of the cache is done in constant time (O(1)) because it involves changing pointers.

- The time complexity of this method is O(1).

Overall, the time complexity of most operations in the LRU cache is O(1), except for the`put` method in the worst-case scenario.

**Space Complexity (Big O Space):**

The space complexity of this LRU cache implementation is O(capacity), where "capacity" represents the maximum number of key-value pairs the cache can store. The primary space usage comes from the`cacheMap`, which stores the key-value pairs, and the linked list of nodes (`head` and`tail`) used to maintain the order of access. Additionally, each node in the linked list consumes space proportional to the key and value sizes.

In summary, the space complexity of the LRU cache is determined by its capacity, and the primary space-consuming data structure is the`cacheMap`, resulting in an overall space complexity of O(capacity).

packageg0101_0200.s0148_sort_list;

importcom_github_leetcode.ListNode;

**Time Complexity (Big O Time):**

The time complexity of the`sortList` method in this program is O(N*log(N)), where N is the number of nodes in the linked list. Here's the breakdown:

- The recursive`sortList` function divides the linked list into two halves. This division step is performed in O(N/2) time, and it happens recursively, so it results in O(N*log(N)) time complexity.

- The merging step, where the two sorted halves are merged together, takes O(N) time in each recursive call.

Therefore, the overall time complexity of the`sortList` method is O(N*log(N)).

**Space Complexity (Big O Space):**

The space complexity of the`sortList` method is O(log(N)) on average due to the recursive function calls. This is because the space required for the function call stack during the recursion grows logarithmically with the number of elements in the list. Each recursive call creates a new stack frame with its own local variables.

Additionally, the program uses a few extra variables for pointers and a dummy node (`res`). These variables consume a constant amount of space, so they don't significantly affect the overall space complexity.

In summary, the primary space consumption is due to the recursion stack, resulting in an average space complexity of O(log(N)) for this program.

publicclassSolution {

publicintmaxProduct(int[]arr) {

**Time Complexity (Big O Time):**

The time complexity of this program is O(N), where N is the length of the`arr` input array. The program makes two passes over the array:

1.**Forward Pass:** In the first pass, it iterates through the array from left to right, calculating the cumulative product of elements in the`cprod` variable. It also keeps track of the maximum product seen so far in the`ans` variable. This pass takes O(N) time.

2.**Backward Pass:** In the second pass, it iterates through the array from right to left, again calculating the cumulative product in`cprod` and updating the maximum product in`ans`. This pass also takes O(N) time.

Both passes run in linear time, and there are no nested loops or recursive calls, so the overall time complexity is O(N).

**Space Complexity (Big O Space):**

The space complexity of this program is O(1), meaning it uses a constant amount of additional space that does not depend on the size of the input array`arr`. The program uses a fixed number of variables (`ans`,`cprod`,`i`,`j`) and doesn't create any data structures or data collections with a size proportional to`N`.

In summary, this program has a time complexity of O(N) and a space complexity of O(1).

packageg0101_0200.s0153_find_minimum_in_rotated_sorted_array;

publicclassSolution {

**Time Complexity (Big O Time):**

The time complexity of this program is O(log N), where N is the number of elements in the`nums` array. The reason for this is that the program performs a binary search to find the minimum element in the rotated sorted array.

In each recursive call to`findMinUtil`, the program divides the search range in half by calculating the midpoint (`mid`) and then recursively searches either the left half or the right half based on certain conditions. This binary search process reduces the search range by half in each step. Therefore, the time complexity is logarithmic, specifically O(log N).

**Space Complexity (Big O Space):**

The space complexity of this program is O(log N) as well. This is because the program uses the call stack to keep track of recursive function calls. In the worst case, when the array is divided in half in each recursive call, the maximum depth of the call stack will be logarithmic in terms of the number of elements in the`nums` array.

So, both the time and space complexity of this program are O(log N), where N is the number of elements in the`nums` array.

publicclassMinStack {

privatestaticclassNode {

**Time Complexity (Big O Time):**

1.**push(int val):** The`push` operation has a time complexity of O(1). It involves creating a new node and updating pointers, both of which are constant time operations.

2.**pop():** The`pop` operation also has a time complexity of O(1). It simply involves moving the`currentNode` pointer to the previous node.

3.**top():** The`top` operation has a time complexity of O(1) because it directly accesses the`data` field of the current node.

4.**getMin():** The`getMin` operation has a time complexity of O(1) because it directly accesses the`min` field of the current node.

Overall, all the stack operations (push, pop, top, getMin) have a constant time complexity of O(1).

**Space Complexity (Big O Space):**

The space complexity of this MinStack implementation is O(N), where N is the number of elements pushed onto the stack.

- Each element pushed onto the stack consumes space for a new node, which contains integer values (`min`,`data`), a reference to the previous node (`previousNode`), and a reference to the next node (`nextNode`).

- As you push more elements onto the stack, the memory usage increases linearly with the number of elements.

It's important to note that the space complexity is related to the number of elements in the stack (N), not the total number of operations performed. Each element added to the stack consumes additional memory.

In summary, the time complexity of all stack operations is O(1), and the space complexity is O(N), where N is the number of elements pushed onto the stack.

packageg0101_0200.s0160_intersection_of_two_linked_lists;

importcom_github_leetcode.ListNode;

**Time Complexity (Big O Time):**

The time complexity of this program is O(M + N), where M is the length of the first linked list (headA) and N is the length of the second linked list (headB). Here's why:

- The two pointers`node1` and`node2` traverse their respective linked lists until they either meet at the intersection or reach the end of their lists.

- In the worst case, where there is no intersection, both`node1` and`node2` will traverse both linked lists completely.

- Therefore, each of the two pointers will perform a total of M + N operations (M for the first list and N for the second list).

The program terminates as soon as`node1` and`node2` meet or both become null.

**Space Complexity (Big O Space):**

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 linked lists. The program only uses a fixed number of pointers (`node1`,`node2`) and variables to keep track of the intersection point.

In summary, the time complexity is O(M + N) where M and N are the lengths of the two linked lists, and the space complexity is O(1), indicating a constant amount of additional memory usage.