# Implementing Quicksort in Python

Just like Mergesort, Quicksort is another favorite sorting algorithm with best case O(n logn) but worst case O(n^2). However, compare to merge sort, this algorithm doesn’t use extra space at all. Find the article on wikipedia if you haven’t seen this algorithm yet: https://en.wikipedia.org/wiki/Quicksort

The idea is as below:

• Pick pivot number (any number, but someone said pick middle or random to minimize the worst case)
• Reorder the array so that elements less than pivot come before the pivot, and elements greater than pivot come after. After this, pivot is in its final position. This process is called partitioning.
• Recursively apply the above to sublists elements with smaller values and separately with greater values.
```def quicksort(nums):
sort(nums, 0, len(nums)-1)

def sort(nums, first, last):
if first < last:
pivot = partition(nums, first, last)
sort(nums, first, pivot-1)
sort(nums, pivot+1, last)

def partition(nums, first, last):
pivot = first + (last - first + 1)/2
swap(nums, pivot, last)
for i in range(first, last):
if nums[i] <= nums[last]:
swap(nums, i, first)
first += 1
swap(nums, first, last)
return first

def swap(nums, left, right):
nums[left], nums[right] = nums[right], nums[left]

```

# Implementing Merge Sort in Python

Merge Sort

Merge sort is a popular example for divide and conquer algorithm. Divide the lists and merge it back in sorted order. Check out the wikipedia if you haven’t seen it before, it’s cool: https://en.wikipedia.org/wiki/Merge_sort

The basic idea of the algorithm is as follow:

• Given list of numbers, divide into sublist until we have n number of list that contain 1 number each
• Repeatedly merge the two sublists together until we obtain sorted list

The solution in python is as below:

```def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums)/2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)

def merge(left, right):
if not left:
return right
if not right:
return left
if left < right:
return [left] + merge(left[1:], right)
return [right] + merge(left, right[1:])
```

# Remove Element and Move Zeros in Array: using two pointers

Part I

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

My Solution

The idea is to keep pointer to position index and store here if we found element that is not zero. The time complexity is O(n).

```def remove(nums):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
if not nums:
return 0
i = 0
for n in nums:
if n != val:
nums[i] = n
i += 1
return i

```

Part II

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

My Solution

The idea is similar to the first one. Keep a pointer to indicate the position of array to store to. The time complexity is O(n).

```def move_zero(nums):
i = 0
for n in nums:
if n != 0:
nums[i] = n
i += 1
while i<len(nums):
nums[i] = 0
i += 1
```

# Remove Duplicates from Sorted Array: using two pointers

Part I

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = `[1,1,2]`,

Your function should return length = `2`, with the first two elements of nums being `1` and `2` respectively. It doesn’t matter what you leave beyond the new length.

My Solution

The idea is very simple to get time complexity of O(n). Use the first pointer to point the position which element is being stored to, and the other pointer to iterate the elements. If the current element and the previous element are different, store the current element in the first pointer and move one. Make exception for the first element and in case element is only 0 or 1 size.

```def remove_duplicates(nums):
if not nums:
return 0
idx = 0
for i in range(len(nums)):
if i==0 or nums[i] != nums[i-1]:
nums[idx] = nums[i]
idx += 1
return idx
```

Part II

What if duplicates are allowed at most twice?

For example,
Given sorted array nums = `[1,1,1,2,2,3]`,

Your function should return length = `5`, with the first five elements of nums being `1``1``2``2` and `3`. It doesn’t matter what you leave beyond the new length.

My Solution

The idea is to skip the middle element and check the previous and next elements. If these are different, store the current element to the position index. The time complexity for this would be O(n).

```def max_two_duplicates(nums):
if len(nums) < 3:
return len(nums)
idx = 1
for i in range(1, len(nums)-1):
if nums[i-1] != nums[i+1]:
nums[idx] = nums[i]
idx += 1
nums[idx] = nums[-1]
return idx + 1
```

# Summary Ranges: using two pointers to return summary of an array

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given `[0,1,2,4,5,7]`, return `["0->2","4->5","7"].`

My Solution

The idea is using two pointers to maintaining the start index and end index, then format it correctly. If the start and end index are the same, format it without the arrow, otherwise add arrow in between. The time complexity would be O(n) and the space is O(n) since I use extra space array to store the result.

```def summary_range(nums):
if not nums:
return []
start, i, res = 0, 0, []
while i<len(nums)-1:
if nums[i+1]-nums[i] != 1:
format_range(res, nums, start, i)
start = i+1
i += 1
# for the last element or in case of 1 element
format_range(res, nums, start, i)
return res

def format_range(res, nums, start, end):
if start == end:
res.append(str(nums[start]))
else:
res.append(str(nums[start]) + "->" + str(nums[end]))
```

# Spiral Matrix

This question was asked during my second round interview with Yahoo search team.

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

```[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
```

You should return `[1,2,3,6,9,8,7,4,5]`.

My Solution

This is pretty straight forward O(mn) solution by traversing right, down, left, and up until it reaches the center. But careful with the duplication by restricting left and up traversal with the start/end indexes.

```def spiral_order(matrix):
if not matrix:
return []
res = []
rowStart, rowEnd = 0, len(matrix)
colStart, colEnd = 0, len(matrix)

# traverse until the center matrix
while rowStart < rowEnd and colStart < colEnd:
# traverse right
for i in range(colStart, colEnd):
res.append(matrix[rowStart][i])
rowStart += 1

# traverse down
for j in range(rowStart, rowEnd):
res.append(matrix[j][colEnd-1])
colEnd -= 1

# traverse left, careful on the duplication
if rowStart < rowEnd:
for k in range(colEnd-1, colStart-1, -1):
res.append(matrix[rowEnd-1][k])
rowEnd -= 1

# traverse up, careful on the duplication
if colStart < colEnd:
for l in range(rowEnd-1, rowStart-1, -1):
res.append(matrix[l][colStart])
colStart += 1

return res

```

# Word Search II

This question is a follow up from my previous post (Word Search) that was asked in Airbnb.

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = `["oath","pea","eat","rain"]` and board =

```[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
```

Return `["eat","oath"]`.

Note:
You may assume that all inputs are consist of lowercase letters `a-z`.

My Solution

Unlike previous question, this has to be optimized to accommodate large test cases as we currently have list of words instead of just one word (see my previous post). This can be done by immediately stop the backtrack if current candidate doesn’t exist in all words prefix. The idea is to build up the prefix of all words using trie, and limit our scope of search in a trie to speedup the computation. And again do DFS to search all possible paths/strings and append to the result. During the traversal, if we reach the leaf of a node, it means we have found a path, add it to the result but keep going as other words might also contain this word as their prefixes. Return if a letter doesn’t exist in the trie at all.

```def word_search(board, words):
if not board or not words:
return None
# build up the prefix trie
trie = {}
for w in words:
t = trie
for c in w:
if c not in trie:
t[c] = {}
t = t[c]
t["#"] = "#"  # mark the leaf node

res = []
for i in range(len(board)):
for j in range(len(board)):
dfs_helper(board, i, j, trie, '', res)
return list(set(res))  # a word might have more than one path, use set to remove duplicates

def dfs_helper(board, i, j, trie, path, res):
# we found leaf node, do not return here but keep going
if "#" in trie:
res.append(path)  # add to res array, remember in python array is referred by reference, not value like Java

if i<0 or j<0 or i>=len(board) or j>=len(board) or board[i][j] not in trie:
return
tmp = board[i][j]  # first letter found
board[i][j] = "@"  # mark visited

res = dfs_helper(board, i-1, j, trie[tmp], path+tmp, res) or \
dfs_helper(board, i+1, j, trie[tmp], path+tmp, res) or \
dfs_helper(board, i, j-1, trie[tmp], path+tmp, res) or \
dfs_helper(board, i, j+1, trie[tmp], path_tmp, res)
```