|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->

|-|-|-|-|-|-

| 0082 |[Remove Duplicates from Sorted List II](src/main/java/g0001_0100/s0082_remove_duplicates_from_sorted_list_ii/Solution.java)| Medium | Two_Pointers, Linked_List | 0 | 100.00

| 0015 |[3Sum](src/main/java/g0001_0100/s0015_3sum/Solution.java)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n^2)_Space_O(1) | 27 | 97.93

| 0015 |[3Sum](src/main/java/g0001_0100/s0015_3sum/Solution.java)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n*log(n))_Space_O(n^2) | 27 | 97.93

| 0977 |[Squares of a Sorted Array](src/main/java/g0901_1000/s0977_squares_of_a_sorted_array/Solution.java)| Easy | Array, Sorting, Two_Pointers | 1 | 100.00

| 0026 |[Remove Duplicates from Sorted Array](src/main/java/g0001_0100/s0026_remove_duplicates_from_sorted_array/Solution.java)| Easy | Top_Interview_Questions, Array, Two_Pointers | 1 | 98.56

| 0042 |[Trapping Rain Water](src/main/java/g0001_0100/s0042_trapping_rain_water/Solution.java)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Two_Pointers, Stack, Monotonic_Stack, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00

| 0015 |[3Sum](src/main/java/g0001_0100/s0015_3sum/Solution.java)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n^2)_Space_O(1) | 27 | 97.93

| 0015 |[3Sum](src/main/java/g0001_0100/s0015_3sum/Solution.java)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n*log(n))_Space_O(n^2) | 27 | 97.93

|-|-|-|-|-|-

| 0136 |[Single Number](src/main/java/g0101_0200/s0136_single_number/Solution.java)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 1 | 99.97

| 0169 |[Majority Element](src/main/java/g0101_0200/s0169_majority_element/Solution.java)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Sorting, Counting, Divide_and_Conquer, Big_O_Time_O(n)_Space_O(1) | 1 | 100.00

| 0015 |[3Sum](src/main/java/g0001_0100/s0015_3sum/Solution.java)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n^2)_Space_O(1) | 27 | 97.93

| 0015 |[3Sum](src/main/java/g0001_0100/s0015_3sum/Solution.java)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n*log(n))_Space_O(n^2) | 27 | 97.93

importjava.util.ArrayList;

importjava.util.Arrays;

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

Thetime complexity of this program isO(n^2), where"n" represents thenumber ofelements inthe`nums`array. Here's the breakdown:

1. Sorting:Theprogram sorts the input array`nums`. Sorting typically takesO(n * log(n)) time complexity, where'n' is thelength of the array.

1.The programstarts by sortingthe`nums` array, which has a time complexity of O(n * log(n)), where "n" isthelength of the array.

2. Main Loop:The programuses nested loops. The outer loop runs from 0 to`len - 2`, where`len` isthelength of the sorted array`nums`. The inner while loop has two pointers (`l` and`r`) that move towards each other. Intheworst case, theinner loop can go through the entirearray, so its time complexity is O(n).

2. After sorting, the program uses nested loops:

- The outer loop runs for`i` from 0 to`len - 2`, where "len" is the length of the array. This loop iterates through each element of the array once, so it has a time complexity of O(n).

3. The code inside the inner loop contains constant-time operations, such as addition, comparison, and list creation.

- The inner loop uses two pointers (`l` and`r`) and runs until`r`isgreater than`l`. Within the innerloop, constant-time operations are performed, such as calculating the sumofthree elements and adjustingthepointers.

Overall, the dominant time complexity is determined by the sorting step, whichisO(n * log(n)). Theloop inside the sorting step has a complexityofO(n), but it doesn't dominatetheoverall complexity.

3. Inside the inner loop, there are additional while loops that skip duplicate elements. These while loops also perform constant-time operations.

Since the sorting step has a time complexity of O(n * log(n)), and the nested loops contribute O(n) iterations, the overall time complexity is dominated by the sorting step, resulting in O(n * log(n)).

So, the total time complexity of the program is O(n * log(n)) due to the sorting step.

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

The space complexity of this program is O(1) because it uses a constant amount of extra space. The program creates a few integer variables (`l`,`r`,`sum`, and`len`), but the space used by these variables is independent of the input size. Additionally, the`result` list stores the output, but its space is not considered part of the space complexity analysis, as it's required to store the program's output.

The space complexity of the program is determined by the space used for the output list`result`. In the worst case, when there are many unique triplets that sum to zero, the size of`result` can be significant.

1. The input array`nums` and the variables`len`,`l`, and`r` all use constant space.

2. The`result` list stores the triplets, and its size can be at most O(n^2) when there are many unique triplets.

3. Other variables and temporary lists used inside the loops use constant space.

So, the space complexity of the program is O(n^2) for the`result` list when considering the worst case.

Therefore, theoverallspace complexityis O(1).

In summary, theprovided program has a time complexity of O(n * log(n)) due to sorting and aspace complexityof O(n^2) for the`result` list when considering the worst-case scenario.