# Week 1: Greedy Algorithm

Greedy Algorithm is very unlikely to appear in a coding interview. That means, you don’t have to learn that hard on this topic. Your task in this week is just to memorize the following solutions, then you are good to go.

## 1. Majority Element

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.

## 2. Create Maximum Number

Given two arrays of length `m` and `n` with digits `0-9` representing two numbers. Create the maximum number of length `k <= m + n` from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the `k` digits.

Note: You should try to optimize your time and space complexity.

Example 1:

```Input:
nums1 = `[3, 4, 6, 5]`
nums2 = `[9, 1, 2, 5, 8, 3]`
k = `5`
Output:
`[9, 8, 6, 5, 3]````

Example 2:

```Input:
nums1 = `[6, 7]`
nums2 = `[6, 0, 4]`
k = `5`
Output:
`[6, 7, 6, 0, 4]````

Example 3:

```Input:
nums1 = `[3, 9]`
nums2 = `[8, 9]`
k = `3`
Output:
`[9, 8, 9]````