# Week 1: Basic Algorithms

Continuing last week, we are going to go over those basic algorithms that appear in coding interviews frequently. Note that the content below is just an overview, and we will discuss them later with full details. In this week, just learn what they are and how they work superficially, in BFS manner.

## Recursion and Divide and Conquer:

LeetCode #50. Pow(x, n) (medium)

LeetCode #169. Majority Element (easy)

More problems can be found here:

## Greedy Algorithm:

Greedy Algorithm usually doesn’t appear in a coding interview. In fact greedy algorithm is not a certain algorithm, maybe we should just call it “greedy approach”. If you design a perfect algorithm using greedy approach for a problem, most likely it won’t apply to another problem, even they look similar. That is, greedy approach is not universal, and it requires quite a bit cleverness. As a result, this category doesn’t appear in coding interviews that often. That means, you don’t have to study really hard on this topic. Your task in this week is just to read through and memorize the following solutions, and you are good to go.

Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

```Input: [3,2,3]
Output: 3```

Example 2:

```Input: [2,2,1,1,1,2,2]
Output: 2```

Algorithm:

The main idea is that if we eliminate every pair of majority element and non-majority element, the majority element will still be majority in the new list, since it appears more than `⌊ n/2 ⌋` times. The algorithm is the following: suppose the first element in `nums` is the majority element, and initialize `count` to 1. Loop the rest of `nums`. If the next element is still the same, increment `count`; otherwise, decrement `count`. If `count` is decreased to 0, suppose the next element is the majority element, and keep looping. The code is here:

Solution:

```class Solution:
def majorityElement(self, nums: List[int]) -> int:
majority = nums[0]
count = 1
for i in range(1, len(nums)):
if majority == nums[i]:
count += 1
else:
count -= 1
if count == 0:
if i == len(nums):
break
else:
majority = nums[i + 1]
return majority
```

Analysis:

This algorithm uses a for loop that runs $n - 1$ times, and all operations inside the for loop takes time $O(1)$, so the overall running time is $O(n)$. It is also an in-place algorithm, thus takes $O(1)$ space.

LeetCode #122. Best Time to Buy and Sell Stock II (easy)

## Rabin-Karp Algorithm:

LeetCode #28. Implement strStr() (easy)