Leetcode Problem 001-099

1. Two Sum 🌟

O(N^2) Time Constant space

Brute force - check every pair of numbers.

O(N) Time and O(N) space

The basic idea is to maintain a hash table for each element num in nums
using num as key and its index (0-based) as value. For each num, search for target - num in the hash table.
If it is found and is not the same element as num, then we are done.

2. Add Two Numbers 🌟🌟

This question only have optimal solution

In an interview you should kill some time and ask interviewer some questions.
like what if l1 have more length than l2, or vice versa or what if both have sam length, and other edge cases.
TC: O(max(n1,n2))
SC: O(len(l1) + len(l2))
Explained in code.

3. Longest Substring Without Repeating Characters 🌟🌟

O(N^3) Time, O(N) space

Brute force
We can consider all substrings one by one and check for each substring whether it contains all unique characters or not.
There will be n*(n+1)/2 substrings.
Whether a substring contains all unique characters or not can be checked in linear time by scanning it from left to right and keeping a map of visited characters.
Time complexity of this solution would be O(n^3).

O(N^2) Time O(N) space, Sliding window

For every i in string we check, How long the substring starting with index i have unique characters

O(N) Time O(N) space, Sliding window

We keep track of unique characters in a hashmap(unordered_set).
l is left index and r is right index, these indicates unique substring’s start and end.
if r’th character is not present in set, we add it and increment r also update maxLength = max(maxLength, r-l);
if r’th character is present in set, we remove it from set and increment l pointer.
finally return maxLength.

8. String to Integer (atoi) 🌟🌟

Solution

We only need to handle four cases:

discards all leading whitespace
sign of the number
overflow
invalid input

11. Container With Most Water 🌟🌟

Brute force (TLE)

Try all possible combinations of lines and find the maximum area out of them.
take min of heights of two lines and multiply it with the distance between them.
Time complexity: O(n^2)
Space complexity: O(1)

Two pointer approach

To optimize the brute force approach, we can use two pointer approach.
we need to maximize the area, so we will start with the maximum width possible.
take one pointer at the start and one at the end.
calculate or update the area.
now we got an area but can we do better? may be we find more taller line and area will increase.
to do it, lets move the pointer which is pointing to the shorter line to the next line.
repeat the process until both the pointers meet.
Time complexity: O(n)
Space complexity: O(1)

12. Integer to Roman 🌟🌟

Greedy solution

Ask interviewer if there could be negative numbers or 0.
Ask if the number is guaranteed to be in the range 1 to 3999.
We create 2 arrays to store the Roman numerals and their corresponding values.
Greedily we try to subtract largest possible number from the input number, and assign their corresponding Roman numeral to the result string.
We repeat this process until the input number becomes 0.
Time complexity: O(n)=O(1), where n is the number of Roman numerals, here constant because we know the number of Roman numerals is 13.
Space complexity: O(n)=O(1), where n is the number of Roman numerals, here constant because we know the number of Roman numerals is 13.

Fun solution

As human being came so far they evolved and they created some flexing solutions, but just don’t flex this solution before interviewer.
TC: O(1), indeed.
SC: O(1), indeed.
Don’t evolve more and create 4*10 array to store all the Roman numerals.

15. 3Sum 🌟🌟

O(N^3 Log m) Brute force

Travel all the triplets which sums to 0.
Pseudo code

    for(i=0,n-1)
        for(j=i+1,n-1)
            for(k=j+1,n-1)
                a+b+c==0, cnt++

To get unique triplets, we can use set data structure.
N^3 for for loop and Log M for inserting unique triplets in the set.
SC: O(M), M is all unique triplets.

O(N^2 Log M) Time and O(N)+O(M) Space

we can run 2 for loops for a and b.
store c in hashmap with its frequency
while running loops we have to decrease frequency of a and b inorder to find unique c.
then we find c=-(a+b) in the hashmap.
store the 3 numbers in sorted order in set so we will not have duplicates.
O(N^2) for 2 loops, Log(M) for inserting in set.
O(N) for map and O(M) For set.

Two pointers.

Sort the array.
Fix a and you just need to find b+c=-a which is two sum problem.
To not get duplicates we increment pointer in such way that they are not equal to their previous values.
TC:O(N*N)
SC:O(M), M is the number of triplets.

18. 4Sum 🌟🌟

O(N^4) brute force

using 4 for loops we can solve this question.

Sort + 3ptr + BinarySearch (int overflow)

TC: O(N^3) - 2loops and finding 2 elements in O(N) time.
SC: O(N^2) - set of vectors
we keep i,j,k pointers and find l using binary search.

TIP:

We can use following code to remove duplicates from vector.

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

See my GFG Solution for better understanding.

Sort + 2ptr + BinarySearch

TC: O(N^3) - 2loops and finding 2 elements in O(N) time.
SC: O(1)
we keep i,j pointers and find l and r using binary search.
We can overcome int overflow by calculating target in every loop.(see code)
We can also overcome extra space by processing pointers until duplicates occurs.(see code)

19. Remove Nth Node From End of List 🌟🌟

O(N) Time and O(1) Space Complexity

Get the length of the linked list.
if n = length then return head->next
n = length - n
go to n-1th node then set its next to its next->next.
delete the space of removed node, else it will cause memory leak.
return head

O(N) Time and O(1) Space Complexity, two pointers

We take 2 pointers, fast and slow. (here both move equally i.e. 1 node at a time)
move fast pointer n times.
if fast is null return head->next
now move slow and fast pointers together until fast->next != NULL.
slow->next = slow->next->next
Delete deleted node.
NOTE: This method have same complexity as above method.

20. Valid Parentheses 🌟

O(N) Time and O(N) Space, straightforward solution

if the string is empty, return true
if the string has an odd number of characters, return false
Create a stack to store parenthesis.
if character is any opening parenthesis, push it to the stack
after first if, if stack is empty, which means the character is closing parenthesis, return false
else
- current character is matching parenthesis of top char of stack, pop that opening character from stack.
- else push it in the stack.
return true if stack is empty else false.

Some slight simplification

we don’t need to push extra closing parenthesis in the stack, if extra parenthesis appears return false.

21. Merge Two Sorted Lists 🌟

O(N+M) Time and O(N+M) space

If any list is empty, return the other list
Create dummy node to store new sorted lists
traverse until one of the list is empty
- if l1 is smaller, add l1 to new list, and move l1 to its next node
- if l2 is smaller, add l2 to new list, and move l2 to its next node
- move dummy pointer
if l2 is empty, add l1 to new list
if l1 is empty, add l2 to new list
Return next pointer of dummy node

O(N+M) Time and O(1) space, in-place

if any list is empty, return the other list
l1 will always contain list of smaller value
- l1 will contain smaller val always;
- store l1 in result;
until any list is empty, run loop
- Create a temp node which points to nullptr
- while l1 has smaller element than l2, add l1 to temp
- after loop l2 will have smaller value than l1
- by swapping l1 and l2, l1 will contain smaller value
return final result which is pointer to l1 list

O(N+M) Time and O(1) Space, Recursive

We will recursively join two linked list such that they will be always sorted.

22. Generate Parentheses 🌟🌟

Backtracking

For each time we have the choice of choking opening or closing parenthesis.
We can choose opening parenthesis when it is greater than 0.
We can choose closing parenthesis when it is greater than the number of opening parenthesis.
and if both opening parenthesis and closing parenthesis are 0 then we got the answer, push-back it in the ans vector.

24. Swap Nodes in Pairs 🌟🌟

By swapping values

By swapping Nodes

26. Remove Duplicates from Sorted Array 🌟

Naive Solution

Store the elements in a set. then add them in the original vector in sorted order.
return the size of the set.
TC: O(N log N), N for the traversal and log N for inserting elements in the set.
SC: O(N), N for the set.

2 pointer solution

Place pointe i to start and j to start + 1.
If nums[i] == nums[j], increment j.
else increment i and set nums[i] = nums[j].
return i + 1.
TC: O(N), N for the traversal.
SC: O(1), since we are modifying the array in place.

31. Next Permutation 🌟🌟

Brute Force

We first generate all the permutations and store them in permutations vector.
Then we find the given vector in the permutations vector.if we found then we return its next vector as and.
If given the last vector return the first vector from the permutations vector.
TC: O(N!*N) - Because there are N! orders and N is the length of every array.
SC: O(N!) - To store the all permutations, there are N! permutations.

O(N) Time solution.

INTUITION:- If we Observe the dictionary of order(permeation order) we can find that there is always Triangle like structure.
For better understanding here is striver’s video
ALGORITHM:- 1. From back find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, just reverse nums and done. 2.From back find the largest index l > k such that nums[k] < nums[l]. 3.Swap nums[k] and nums[l]. 4.Reverse the sub-array nums[k + 1:].
REFERENCE:- C++ from Wikipedia

Inbuilt next_permutation

we can also solve the problem in-place using in-built next_permutation(a.being(),a.end()) function in c++.
But in an interview this is not expected.

35. Search Insert Position

O(log N) Time solution

Modification of BS.
l<r
- if target greater than element at mid.
  - l = mid+1
- else
  - r = mid // not mid-1;
return l

36. Valid Sudoku 🌟🌟

Implementation

37. Sudoku Solver 🌟🌟🌟

Backtracking (16ms-AC)

Solve function algorithm:
- if index of row exceed the board size, we got our solution, return true.
- if index of column exceed the board size, we are done for current row, move to next row.
- if current cell is already marked, move to the next cell.
- else current cell is empty so we try all characters from ‘1’ to ‘9’ for current cell.
  - if its valid to put i’th character in current cell,
    - put i’th character in current cell,
    - recursively call solve function for next cell,
      - if it returns true, we got our solution, return true.
      - else we can not put i’th character in current cell,
    - remove the i’th character from current cell
- if we are done with all characters for current cell, we can not get our solution, return false.
isValid function algorithm:
- check if the current number appeared before in the row.
- check if the current number appeared before in the column.
- check if the current number appeared before in the 3x3 sub-box.
  - we can traverse the ith box with, ` int newRow = (row / 3) * 3, newCol = (col / 3) * 3; int iindex = newRow + i, jindex = newCol + j;`

39. Combination Sum 🌟🌟

42. Trapping Rain Water 🌟🌟🌟

Brute force

For every index find the max water that can be trapped.
This can be done with the formula min(maxLeft(i),maxRight(i))-a[i]
TC: O(N^2), 2nd loop for finding left and right max.
SC: O(1)

PrefixSum Optimized

We can pre-compute left max in an array and right max from back into the another array, so the 2 loop is not necessary.
TC: O(N)
SC: O(2*N)–>O(N)

2-pointer

We can find left max and right max with 2 pointer approach.
Explained in code.
TC: O(N)
SC: O(1)

46. Permutations 🌟🌟

Backtracking

Backtracking is a general technique for solving problems that uses DFS and finds ALL POSSIBLE SOLUTIONS.
General idea:
```
Step 1: DO
Step 2: RECUR
Step 3: UNDO
```
Make sure to use base conditions.

48. Rotate Image 🌟🌟

O(N^2) Time and O(N^2) space Solution

We can take 1 more 2D matrix and perform the operation
But this is not allowed.

O(N^2) Time O(1) Space Solution

Clockwise 90deg rotation
1. Reverse the matrix.
2. Transpose the matrix.

 clockwise rotate
 first reverse up to down, then swap the symmetry
 1 2 3     7 8 9     7 4 1
 4 5 6  => 4 5 6  => 8 5 2
 7 8 9     1 2 3     9 6 3

Anticlockwise 90deg rotation
1. Transpose the matrix
2. Rotate the matrix.

Anticlockwise rotate
 first swap the symmetry, then reverse up to down
 1 2 3     1 4 7     3 6 9
 4 5 6  => 2 5 8  => 2 5 8
 7 8 9     3 6 9     1 4 7

MUST READ:

49. Group Anagrams 🌟🌟

Hash map + sorting

By sorting s[i] we can use it as key for out hashmap.
Store the sorted string as key and the original string as value.
TC: O(NKlogK), where N is the length of strs, and K is the maximum length of a string in strs. The outer loop has complexity O(N) as we iterate through each string. Then, we sort each string in O(KlogK) time.
SC: O(N), the total information content stored in res.

50. Pow(x, n) 🌟🌟

O(N) Time Brute force

if n is 0, return 1.0
set ans = x
We iterate N times and multiply ans with x.
If N is negative, we convert it to positive and then multiply with x and finally return 1/result.
But there is one edge case, given that n is integer and range of integers is -2,147,483,648 to 2,147,483,647 so if we convert -2,147,483,648 to positive, it will overflow.
To tackle this edge case, we can use long type.

O(log2_N) optimized

Math concept 2^5 = 2*(2^4) = 2*(4^2) = 2*16 = 32
if n is even we can divide it half and do multiplication
if n is odd we can multiply 1 x with ans and reduce it to even number.
when it will be 0 we stop the loop.

Recursive

51. N-Queens 🌟🌟🌟

Brute force backtracking (8ms-AC)

Main Algorithm - we iterate over each row in the board, i.e. once we reach the last row of the board, we should have explored all the possible solutions. - At each iteration (we are located at certain row), we then further iterate over each column of the board, along the current row. At this second iteration, we then can explore the possibility of placing a queen on a particular cell. - Before, we place a queen on the cell with index of (row, col), we need to check if this cell is under the attacking zone of the queens that have been placed on the board before. We can do it with isSafe() function. - Once the check passes, we then can proceed to place a queen. Along with the placement, one should also mark out the attacking zone of this newly-placed queen. We achieve this with placeQueen() function. - As an important behavior of backtracking, we should be able to abandon our previous decision at the moment we decide to move on to the next candidate. We achieve this with removeQueen() function.
The time complexity of nQueens problem is dependent of how we implement isSafe() function.
isSafe() function:
- We can check if the queen is placed in current row, current column, or the positive diagonal or negative diagonal.
- BUT, we don’t need to do some redundant checks. like chekiang for the same row, lower column, lower positive and negative diagonal as we haven’t traverse them yet.
- We just check upper positive and negative diagonal as well as upper column.
- We can do it by simple simulation.

3 vectors optimized backtracking (3ms-AC)

All the algorithm is same but we can optimize the isSafe() function by using extra space.
isSafe() function:
- We can have the colSet vector to store the column index of the queens that are placed on the board.
- also we can have posDig and negDig vectors to store the positive and negative diagonal indices of the queens that are placed on the board.
- We can get the positive diagonal index with col + row
- We can get the negative diagonal index with col - row + n - 1

1 vector optimized backtracking (7ms-AC)

Again same algorithm but we just used 1 vector instead of 3 vectors.
isSafe() function:
- flag[0] to flag[n - 1] to indicate if the column had a queen before.
- flag[n] to flag[3 * n - 2] to indicate if the 45° diagonal had a queen before.
- flag[3 * n - 1] to flag[5 * n - 3] to indicate if the 135° diagonal had a queen before.
- So we will declare flag(5 * n - 3) vector to store the information of the board.
- We can get the positive diagonal index with n + col + row
- We can get the negative diagonal index with 4 * n - 2 + col - row

52. N-Queens II 🌟🌟🌟

Same problem as 51. N-Queens, Just need to change result vector with count variable.

For explanation refer previous question nQueens-1

53. Maximum Subarray 🌟

O(N) time constant space(DP)

We maintain a maximum sum and current sum(if element itself is max)
for each i=(0,n)
- add current element to current sum
- mx = max(current sum , mx);
- current sum will be max(0,current sum);
finally we return mx

56. Merge Intervals 🌟🌟

O(N^2) Time Solution

Brute force.
sort the intervals by start time.(NlogN Time)
for every interval i, check if it overlaps with any interval j.
if it does, merge the two intervals.
if it doesn’t, add it to the result.

O(NlogN) Time O(N) Space Solution

Check for invalid case.
Sort the intervals by start time.
Take first pair of interval.
iterate over intervals and check if they overlap or not.
if they overlap, then change temp pair to max(temp[1],x[1]).
else push temp pair to result and change temp pair to x.

O(NlogN) Time O(1) Space Solution

If we not consider the vector ans, which we have to return this problem can be solved without using temp vector.
We can simply use vector.back and do the operations on it.

61. Rotate List 🌟🌟

Brute force

Pick up the last node and put it to the first, do this k times.
TC: O(k*N)
SC: O(1)

Optimized

Get the length of the linked list.
point last nodes next to head.
point the len-kth nodes next to null
TC: O(N)
SC: O(1)

62. Unique Paths 🌟🌟

Recursive Solution (TLE)

To reach at the end we can either go down or right, so we do it by recursion.
when we reach the goal we return 1.
if we go out of boundary we return 0
Time Complexity: O(2^n)

Recursive + Memoization

remember to store calculated values in a dp - last line.
Time complexity: m x n
Space complexity: m x n

Tabulation Solution

Time complexity: m x n
Space complexity: m x n

Combinatorics Solution

Time complexity: O(min(m,n))
Explained in striver’s video.

READ

Recursive, memoization and dynamic programming solutions

63. Unique Paths II 🌟🌟

Recursion (TLE)

The straightforward solution is to use recursion.
We have choice to go right or go down.
we return right + left as we want to find all the paths.
the base case arises when we reach to our destination i.e.(m-1, n-1), we return 1.
also if we encounter an obstacle Or one of our indexes goes out of range, we return 0.

Memoization (AC)

The above recursion solution calculates same subproblem again and again results in TLE.
We can use memoization to store the result of subproblems in dp table.
If we already calculated the solution return it.
TC: O(m*n)
SC: O(m*n)

Tabulation (AC)

We can also use tabulation to solve this problem.
But here are some edge case that we have to take care.
we fill first row with 1 and first column with 1.
but at any point in 1st row or column we encounter an obstacle, we set the all farther value to 0.
other things are same as recursion.
TC: O(m*n)
SC: O(m*n)

64. Minimum Path Sum 🌟🌟

Recursion (TLE)

For a cell in grid we can go either right or down.
We take minimum of right path and down path with current cell’s value.
The base case arises when we reach to the last cell, then we return that cell’s value.
also if we go out of bound the we return INT_MAX, because we are taking minimum of right and down.

Memoization (AC)

The recursive solution will result in TLE, because of representing subproblems.
We can use memoization table to remember the result of subproblems.
If we have already computed the values of the subproblem then we directly return it from the table.
If we encounter new subproblem then we store it in the table.
TC: O(m*n)
SC: O(m*n)

Tabulation (AC)

We can convert memoization method to tabulation method.
first we fill the bottom-right corner with the value of grid[m-1][n-1], because it Don’t have any other choice.
Then we fill last row and last column, because they have Only one choice.
Rest we can fill with regular method, they have Two choices we take minimum of both.
TC: O(m*n)
SC: O(m*n)
The above code can also written as:

70. Climbing Stairs 🌟

Dynamic Programming

71. Simplify Path 🌟🌟

Using stack

We create stringstream objects to store the path
We use a stack to store the directories
Iterate those the path,
- if it is “.” or ““(we get “” when multiple ‘//’ appears) continue
- if it is “..” and stack is not empty, pop the stack.
- if it is a directory, push it to the stack
append the stack to the result string.
NOTE: Appending from front is O(N^2) operation, we can reduce it by reversing the stack and appending to last of result string.
If result string is empty, return “/” else return result string.
TC: O(N^2) OR reverse the stack O(N)
SC: O(N)

73. Set Matrix Zeroes 🌟🌟

Brute Force

For every 0 in matrix we set its entire row and column to -1(if all values are positive)
after whole matrix is traversed, we set all -1 to 0;
Time Complexity: O(m*n) * (m+n)
- m*n : to traverse the array
- m+n : to traverse the row and column for the element.
Space Complexity: O(1)

O(m+n) space optimization

We take 2 vectors 1 for row and 1 for column.
We traverse in matrix and if the element is 0, we set the corresponding row and column vector index to 0.
After the traversal, we again traverse the matrix and if any of the row or column vector at that index is 0, we set the element to 0.
Time complexity: 2*O(N*M) –> O(N*M)

O(1) Space Optimization

Instead of creating 2 new vectors for row and column we can take first row and first column of matrix for marking.
We traverse the whole array and if the element is 0, we set the corresponding row and column vector index to 0.
For the first col there is one special case, if we set first col to 0 so the row will unnecessarily have 0’s in them.
to tackle this case we take col variable and set it true initially. while traversing the array if we got any 0 in first column so we change col = false.
Now we traverse from bottom-right to top-left and if we found 0 in any marker vector we set current element to 0.
for the first column, if col==false we set it to 0.
Time complexity: 2*O(N*M) –> O(N*M)

74. Search a 2D Matrix 🌟🌟

O(N*M) Time and constant space solution

Brute force.
Traverse through the matrix and check for the target.
If the target is found, return true.
finally return false.

O(N*logM) Time and constant space solution

Search using binary search.

O(log(N*M)) Time and O(1) space

Complete Binary search on matrix.
mid/m : row , mid%m : column

75. Sort Colors 🌟🌟

O(N log N) Time Complexity with sort function.

sort the vector using stl sort() function.

O(N)+O(N) Time using counting sort.

count number of 0’s, 1’s, and 2’s and push them in increasing order according to their frequency.

O(N) Time, 3 Pointers, dutch national flag algorithm.

We take 3 pointers low, mid and high.
low and mid points to 0 while high points to the last element.
we assume following conditions.
- Towards the left of low everything is 0.
- Towards the right of high everything is 2.
- In between low and high, everything is 1.
while(mid<=high) we do following.
- When we encounter 0.
  - we swap low and mid.
  - we increment low and mid.
- When we encounter 1.
  - we increment mid.
- When we encounter 2.
  - we swap mid and high.
  - we decrement high.

76. Minimum Window Substring 🌟🌟🌟

Sliding Window + Hashmap

We use sliding window with hashmap and counter for this problem.
counter indicates if characters are present in the window or not. if positive then present, if negative then not present.
Other Code is self explanatory.
TC: O(n)
SC: O(n)

77. Combinations 🌟🌟

Backtracking: solution-1 (28ms-AC)

Backtracking is a general technique for solving problems that uses DFS and finds ALL POSSIBLE SOLUTIONS.
General idea:
```
Step 1: DO
Step 2: RECUR
Step 3: UNDO
```
Make sure to use base conditions.

Solution-2 (10ms-AC)

78. Subsets 🌟🌟

Recursive solution

For a number we have 2 choices: either we can include it OR not in include it.

82. Remove Duplicates from Sorted List II 🌟🌟

Solution

Explained in code.
TC: O(N)
SC: O(1)

83. Remove Duplicates from Sorted List 🌟

O(N) Time and O(1) Space

if value of current node is equal to the value of the next node, delete the next node
else traverse next node,

86. Partition List 🌟🌟

88. Merge Sorted Array 🌟

O(M+N) Time and O(M+N) space

Create new array with m+n elements.
Traverse through both the given array, find min and insert in the new array.

O(M*N) without using extra Space

Traverse through both the given array
If arr1[i]>arr2[i] then swap the elements and sort the second array.(here sorting means just put swapped element at its right position not real sorting)

O(M+N) Time and O(1) Space

Code is self explanatory on leetcode

Using GAP algorithm

O(Log2N * O(N)) time and O(1) space
We Will take GAP between two pointers and if the are not sorted we swap them.
first GAP = ceil(n1+n2/2) then next time it will be half of previous GAP.
If GAP is 1 then next time we stop.
Striver Video 7:47

91. Decode Ways 🌟🌟

Recursive solution (TLE)

For a character in string we have 2 choices:
- We can use it as single character OR
- We can use it as a part of a two-character string
The base case arises when we cross length of the string, it means we have decoded all the characters.return 1.
And if character in string starts with ‘0’ we cannot decode it, return 0.
finally we return way1+way2 because we want to find all the possible ways to decode the string.
TC: O(2^N)

Memoization (AC)

The recursive solution results in TLE, because of repeated calculation.
We can use memoization to store the result of subproblems.
If the subproblem is already calculated, we can return the result from the memoization table.
TC: O(N)
SC: O(N)

Tabulation (AC)

In tabulation we use iteration to calculate the result.
It starts from base case and calculate the result for each subproblem.
TC: O(N)
SC: O(N)

94. Binary Tree Inorder Traversal 🌟

O(N) Time and O(N) auxillary space, recursive

if root is null, Return.
Traverse Left subtree.
Visit the root (store data).
Traverse Right subtree.

O(N) Time and O(N) Space, iterative

if root is null, Return.
while true
- if left node present, then traverse all the way left.& push node in the stack.
- if stack is empty, break the loop.
- get the top in node variable and push it in ans vector.
- now move to the right.
return inorder(ans) vector.

O(N) Time and O(1) Space, Morris Traversal

Soon…

96. Unique Binary Search Trees 🌟🌟

MUST READ 👇:

There are a few ways to solve this problem. I have explained all the solutions and approach to optimize it from Brute-Force to Dynamic Programming to solving using Catalan formula in: ✅[ Simple Solution w/ Explanation

Optimization from Brute-Force to DP](https://leetcode.com/problems/unique-binary-search-trees/discuss/1565543/Simple-Solution-w-Explanation-or-Optimization-from-Brute-Force-to-DP)

Brute-Force ( Time: O(3^N), Space: O(N) )
Dynamic Programming - Memoization ( Time: O(N^2), Space: O(N) )
Dynamic Programming - Tabulation ( Time: O(N^2), Space: O(N) )
Catalan Numbers ( Time: O(N), Space: O(1) )
Catalan Numbers (2nd Approach) ( Time: O(N), Space: O(1) )

[C++ Easy & Clean Solution

Fastest

All (4+) Methods

Detailed Explanation & Comments](https://leetcode.com/problems/unique-binary-search-trees/discuss/1565544/C%2B%2B-Easy-and-Clean-Solution-or-Fastest-or-All-(3%2B)-Methods-or-Detailed-Explanation-and-Comments)

DP Solution(Tabulation)

We have base conditions of dp[0] = dp[1] = 1.
Then we calculate result for each number of nodes i from 2...n.
For i nodes. we can consider each of the node j from 1...i as the root node.
Considering the jth node as the root node in BST having total of i nodes, the result is summation for all j from 1...i of dp[j-1] * dp[i-j]. (Comparing to above solution dp[j-1] = numTrees(j-1) and dp[i-j]=numTrees(i-j))

97. Interleaving String 🌟🌟

98. Validate Binary Search Tree 🌟🌟

O(N) Time and O(N) space

Inorder traversal of the binary tree gives sorted array.
we can traverse the tree inorder and check if the array is sorted or not.

O(N) Time solution

we will check if value is less than maximum and greater than minimum
Refer This , if you are not able to understand.

99. Recover Binary Search Tree 🌟🌟

Recursive using inorder traversal

We know that inorder traversal of BST is sorted, so we can use this fact to find the two nodes swapped.(In question it’s confirmed that only two nodes are swapped)
We can use inorder traversal to find the two nodes swapped.
TC: O(n)