# Python Algorithms

### Time Complexity

#### O(1)

1 | # Example 1 |

#### O(n)

1 | # Example 1 |

#### O(n^2)

1 | # Example 1 |

#### O(log(n))

1 | # Example 1 |

#### O(nlog(n))

1 | # Example 1 |

### Two Sum (Two Number Sum)

https://leetcode.com/problems/two-sum

https://www.algoexpert.io/questions/Two%20Number%20Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1 | Given nums = [2, 7, 11, 15], target = 9, |

#### Potential Solutions

##### Solution 1

- Add up all of the elements in the array one by one.
- Return the elements matching the targetSum.

$$ n \choose 2 $$

1 | # O(n^2) time | O(n) space |

`array`

has 8 element, which means there are $n \choose 2$ results. And some results may be same.

##### Solution 2

- Current Number = x, x + y = target, y = target - x
- Make a hash table.
- If y in the elements, then give it
`True`

value in the hash table. - In this example ,
`10 - 11`

is not in the hash table since we do not calculate`10 - (-1)`

yet. But when we calculate`10 - (-1)`

,`11`

is in the hash table. So we are done and the program should return`[11, -1]`

.

1 | # O(n) time | O(n) space |

##### Solution 3

See Best Solution below.

#### Best Solution

- Sort the array.
- Set a Left Pointer and R Pointer.

After we sort a list, we could define two indicators: L & R.

If the sum of L&R == target, then we get the correct result.

If the sum of L&R < target, then we should move L right.

If sum of L&R == targe > target, then we should move R left.

L cannot over then R

Time = O(nlog(n))

Space = O(1)

1 | # O(nlog(n)) time | O(1) space |

1 | class Solution(object): |

### Is Subsequence (Validate Subsequence)

https://leetcode.com/problems/is-subsequence/

https://algoexpert.io/questions/Validate%20Subsequence

Given a string **s** and a string **t**, check if **s** is subsequence of **t**.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `"ace"`

is a subsequence of `"abcde"`

while `"aec"`

is not).

#### Solution 1

- Subsequence must be a subset. A subset with proper order of items is sequence.
- Traverse the sequence.
- Remove the current item in array and add the its index to list
`array_ind`

. - If item is not in array, it is not a subset.
- If the order of the subset is correct, it is subsequence.

1 | def isValidSubsequence(array, sequence): |

#### Solution 2

- Set two pointers named
`arrIdx`

and`seqIdx`

respectively for`array`

and`sequence`

. - Traverse
`sequence`

and`array`

. - If the item matched, move forward the pointer.

1 | # O(n) time | O(1) space |

#### Solution 3

- Set a pointer named
`seqIdx`

for`sequence`

. - Traverse
`array`

and check if item in`sequence`

. - If so, move forward the pointer.

1 | def isValidSubsequence(array, sequence): |

### （BST Construction)

- Split the root node in two subtrees.
- Notice: every time we have three elements from the BST: current node(
`self.value`

), the left subnode(`self.left`

), and the right subnode(`self.right`

).

The Comparison Process in Insertion Method

1 | insert(12) |

#### Methods

- Insertion: every time we compare the current node and the value, then skip one of the subtrees. It means we only explore the half and the half and the half of the whole BST.
- Searching: similar with Insertion method.
- Deletion: grab the smallest value of the right subtree since all of them are greater or equal than the root node, which means the smallest value of the right subtree is greater than all of the values from the lest subtree. And consider the following scenarios:
- when we find the value position:

1 | def insert(self, value): |

1 | def contains(self, value): |

1 | def remove(self, value, parentNode = None): |

1 | def getRootValue(self): |

1 | def getMinValue(self): |

1 | def getMaxValue(self): |

#### Solution 1

1 | class BST: |

1 | p = BST(10) |

#### Solution 2

1 | class BST: |

#### (Find Closest Value in BST)

https://www.algoexpert.io/questions/Find%20Closest%20Value%20In%20BST

## One More Thing

Python Algorithms - Words: 2,640

Python Crawler - Words: 1,663

Python Data Science - Words: 4,551

Python Django - Words: 2,409

Python File Handling - Words: 1,533

Python Flask - Words: 874

Python LeetCode - Words: 9

Python Machine Learning - Words: 5,532

Python MongoDB - Words: 32

Python MySQL - Words: 1,655

Python OS - Words: 707

Python plotly - Words: 6,649

Python Quantitative Trading - Words: 353

Python Tutorial - Words: 25,451

Python Unit Testing - Words: 68