## Summary of Array algorithms questions (medium)

Recently I tried to solve the interesting questions on leetcode. I think the thinking strategy should be recorded here.

### 1. max chunks to make sorted

The question is about finding the max amount of divided arrays for an unsorted array.

The idea is:

select k elements (1, 2, … k-1) from left to right, if all elements are smaller than the rest of elements then it should be divided.

It can be converted to:

find the max amount of left array, if the amount is equal to the index (specific condition for that question), then the array can be divided

### 3. Dynamic programming

When to use: if the problem can be abstracted to a subtask which is depended on the previous result or results

the best result of n is based on the best result of n-1

Another good example about dynamic programming
The current result is based on previous result
e.g. length ++

Don’t limit the format of DP. Not all dp need something like the stock
e.g.

``````class Solution:
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
row = len(triangle)
if row == 0:
return 0
for r in range(1, row):
for c in range(len(triangle[r])):
if c == 0:
triangle[r][c] = triangle[r-1][c] + triangle[r][c]
elif c == len(triangle[r]) -1:
triangle[r][c] = triangle[r-1][c-1] + triangle[r][c]
else:
triangle[r][c] = min(triangle[r-1][c-1], triangle[r-1][c]) + triangle[r][c]
minisum = min(triangle[row-1])
return minisum

``````
``````class Solution:
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
hashTable = [* (len(B)+1) for _ in range(len(A)+1)]
for x in range(len(A)-1, -1, -1):
for y in range(len(B)-1 , -1, -1):
if A[x] == B[y]:
hashTable[x][y] = hashTable[x+1][y+1] + 1
maxcount = 0
maxcount = max([max(hashTable[x]) for x in range(len(hashTable))])
return maxcount
``````
``````class Solution:
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
maxpre = nums
minpre = nums
maxnow = maxpre
minnow = minpre
maxsofar = nums
nl = len(nums)
for x in range(1,nl):
maxnow = max(max(minpre*nums[x], maxpre* nums[x]), nums[x])
minnow = min(min(minpre*nums[x], maxpre*nums[x]), nums[x])
maxsofar = max(maxnow, maxsofar)
maxpre = maxnow
minpre = minnow
return maxsofar
``````

### 4. backtracing questions

Backtracking can be solved always as follows:

``````Pick a starting point.
while(Problem is not solved)
For each path from the starting point.
check if selected path is safe, if yes select it
and make recursive call to rest of the problem
before which undo the current move.
End For
If none of the move works out, return false, NO SOLUTON.
``````

a good example about back tracking is getting all substring of a string or all subset of a array

e.g.

``````class Solution:
def backTrace(self, candidates, index, curList, remain, res):
if remain == 0:
res.append(curList)
return
elif remain < 0:
return
else:
for x in range(index, len(candidates)):
self.backTrace(candidates, x, curList + [candidates[x]], remain-candidates[x], res)

def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res=[]
candidates.sort()
self.backTrace(candidates, 0, [], target, res)
return res
``````

### 5. Cycle Detection

Cycle detection can be used within array or queue or link Assume that the first time slow point meets the fast point at M

Assume the cycle length is C

The dis of slow point is v= a*C + m + p

The dis of fast point is 2v= b*C + m + p

2v-v = v = (b-a)C=n*C

So v is nC, v = aC + m + p, Therefore m+p is n*C

Therefore, we let fast point back to the start and both fast and slow points move at the same speed.  Assume they meet the second time:

Fast point moved p

The dis between cycle entry and slow point is m, and slow point moved p

m +p  is n*C . So the fast and slow points will meet and the entry of the cycle

Usually array value and index can be a potential cycle

e.g.

index 0 1 2 3 4 5

value  1 2 3 4 2 5

if we keep getting nums[nums[i]],  it will become a cycle

### 6. Scope classification

e.g

``````_______|___________|_____________|_______|__________

start1       end1         start2    end2
``````

how to judge a point is within multiple scopes?

The best option is the binary tree

We can define a tree structure with python:

``````class Node:
__slots__ = 'start','end','left','right'
def __init__(self, start, end):
self.start = start
self.end = end
self.left = self.right = None

def insert(self, node):
if node.start = self.end:
if not self.right:
self.right = node
return True
return self.right.insert(node)
elif node.end <= self.start:
if not self.left:
self.left = node
return True
return self.left.insert(node)
else:
return False
``````

### 7. binary search

If we want to find a point in a set of numbers and the set is sorted. Then it may be a classisic binary search problem
Be careful about the +1 / -1 and return l or r or mid

``````int binarySearch(int nums[], int l, int r, int x) {
while (r >= l && r < nums.length) {
int mid = (l + r) / 2;
if (nums[mid] >= x)
r = mid - 1;
else
l = mid + 1;
}
return l;
}
``````

when using binary searching, we need to be careful about the mid selection. for example, left+right / 2 or left+right +1 /2 for odd or even.
Later I should go deep into the extrame situation of binary search

Now it’s time to go deep into the question!

Assume:

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order ofO(logn).

For example, Given[5, 7, 7, 8, 8, 10]and target value 8, return[3, 4].

The idea is first use binary search to find the left side of the target and then use the same method to find the right side.

To find the left side:

mid = int(l+r)/2 // this will always get the low integer e.g. int(1.6) == 1

Since it’s an ascending order, if nums[mid] < target, then target exist in (mid, r], we should have l=mid +1

If nums[mid] > target, the target exist in [l, mid) so we should have r = mid -1

if nums[mid] == target, we have 2 situation:

target start == mid
target start < mid
Therefore target start <= mid, so target start is within [l, mid], we should have r = mid

1 2 3 3 3 4 5

l r

1 2 3 3 3 4 5 mid = 3 nums == 3

l r

1 2 3 3 3 4 5 mid = 1 nums == 2 <3

l r

1 2 3 3 3 4 5 mid = 1 nums == 2 <3

l r

1 2 3 3 3 4 5 mid = 2 nums == 3

lr
l=r and nums[l] is the target left side

Now we have target left side == l. The next step is to find the right side

The right side is within [l, len(nums)-1]

l = l

r = len(nums)-1

mid = int(l+r)/2

if nums[mid] > target, then the target end should within the [l, mid] therefore r = mid -1

if nums[mid] == target, then 2 situation

target end is on the right side of mid, then l = mid +1

target end is mid, l = mid

Therefore target end >= mid, target end is within [mid r], then l = mid

3 3 3 4 5 mid = 2 nums = 3

l r

3 3 3 4 5 mid = 3 nums > 3

l r

3 3 3 4 5 mid = 2 nums = 3 l=

l r
Then we have the problem that at some stage we alway have l = min

So l pointer stops moving.

To avoid this we can let mid = l+r+1/2, So everytime we get the highest integer as mid

3 3 3 4 5 mid = 2 nums = 3

l r

3 3 3 4 5 mid = 3 nums > 3

l r
3 3 3 4 5 mid = 3 nums =4 > 3

l r
3 3 3 4 5

l=r=2

### 8. Linear scan instead of brute force

Some time we will meet the brute force situation.
e.g. 3sum smaller  or the validntriangle number

If we use brute force solution to solve the problem, we will meet the time exceed issue

Obviously, for those questions we can sort the array first and then try to get the extrame limit. We can use the binary search to get that limit or use the linear scan to get the result

### 9. 3D dynamic programming

Similar to dynamic programming
We go through the matrix once but for each element, we need the previous value for the calculation. Therefore, we need a 3D array to hold previous values

``````class Solution:
def longestLine(self, M):
if len(M) == 0:
return 0
rows, columns = len(M), len(M)
maxcount = 0
dp = [ [*4 for c in range(columns)] for r in range(rows)]
for r in range(rows):
for c in range(columns):
if M[r][c] == 1:
dp[r][c] = dp[r][c-1] + 1 if c > 0 else 1
dp[r][c] = dp[r-1][c] + 1 if r > 0 else 1
dp[r][c] = dp[r-1][c+1] +1 if r > 0 and c < columns -1 else 1
dp[r][c] = dp[r-1][c-1] +1 if r >0 and c>0 else 1
maxcount = max(maxcount,max(dp[r][c]))
return maxcount
``````

### 10. Matrix direction switch

Assume the point in a matrix move in clockwise, we can easily check if we need to change the direction by the limit of border and direction=direction+1%4

``````example1:
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
ans=[]
rnum=len(matrix)
if rnum == 0:
return []
cnum=len(matrix)
if cnum == 0:
return []

seen= [[False] * cnum for x in range(rnum)]
dr= [0, 1, 0, -1]
dc= [1, 0, -1, 0]
r=c=di = 0
for _ in range(rnum * cnum):
ans.append(matrix[r][c])
seen[r][c] = True
rnext,cnext = r + dr[di],c+dc[di]
if rnext >= 0 and rnext<rnum and cnext >= 0 and cnext < cnum and not seen[rnext][cnext]:
r,c = rnext,cnext
else:
di = (di +1) %4
r,c = r + dr[di],c+dc[di]
return ans
``````
``````another good example based on the privous solution:
class Solution:
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
res= [*n for x in range(n)]
count = 1
r=c=di=0
dr= [0,1,0,-1]
dc= [1,0,-1,0]
for _ in range(n*n):
res[r][c]=count
count+=1
rn,cn=r+dr[di],c+dc[di]
if 0<=rn<n and 0<=cn<n and res[rn][cn] == 0:
r,c = rn,cn
else:
di = (di+1)%4
r,c=r+dr[di],c+dc[di]
return res
``````

### 11. culumative sum

A simple idea of culumative sum is:
Assume we have an array contains n integer, the sum of subarray between i and j is equal to the sum from 0 to i minus the sum from 0 to j , and: i<j

e.g. subarray sum equals k

``````class Solution:
def subarraySum(self, nums, k):
sumhash = {}
sumhash = 1 // need to add 1 to 0 because if sum == k (sum - k ==0), we need to count 1 for each sum == k
sumN = 0
count = 0
for x in range(len(nums)):
sumN=sumN + nums[x]
if (sumN-k) in sumhash:
count += sumhash[(sumN-k)]
if sumN in sumhash:
sumhash[sumN] += 1
else:
sumhash[sumN] = 1
return count

``````

### 12. 2Sum, 3Sum, 4Sum, KSum

The main idea of those questions is to downgrade the Nsum to N-1 sum. We also try to reduce the calculation with different limitation

e.g. 3Sum

``````class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
ans = []
for x in range(len(nums)-2):
if nums[x] > 0:
break
if x > 0 and nums[x] == nums[x-1]:
continue
y = x+1
z = len(nums) -1
while y < z:
cursum = nums[x] + nums[y] + nums[z]
if cursum == 0:
ans.append([nums[x],nums[y],nums[z]])
while y<z and nums[y] == nums[y+1]:
y+= 1
while y<z and nums[z] == nums[z-1]:
z-=1
y+=1
z-=1
elif cursum <0:
y += 1
else:
z -= 1
return ans

``````

4Sum

``````class Solution:
def threeSum(self, nums, target, ans,index, previous, lnum):
for i in range(index, lnum-2):
if (3 * nums[i]) > target:
return
if (3*nums[lnum-1])<target:
return
if i > index and nums[i] == nums[i-1]:
continue
l = i+1
r = lnum -1
while l < r:
cursum = nums[i] + nums[l] + nums[r]
if cursum == target:
ans.append([previous, nums[i], nums[l], nums[r]])
while l<r and nums[l] == nums[l+1]:
l = l+1
while l < r and nums[r] == nums[r-1]:
r =r-1
l = l+1
r= r-1
elif cursum < target:
l +=1
else:
r-=1
return

def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
ans = []
nums.sort()
lnum = len(nums)
if lnum <4:
return ans
if nums*4 > target:
return ans
if nums[lnum-1] * 4 < target:
return ans
for i in range(lnum-3):
if (nums[i] + 3*nums[lnum-1]) < target:
continue
if (nums[i]+ 3*nums[i+1]) > target:
continue
if i>0 and nums[i] == nums[i-1]:
continue
if nums[i] * 4 == target:
if i+3 < lnum and nums[i] == nums[i+3]:
ans.append([nums[i]]*4)
continue
self.threeSum(nums, target - nums[i], ans, i+1, nums[i], lnum)

return ans
``````

### 12. Merge interval

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

The idea is to first sort the list with start
and then check for each element if the next one’s start is in the previous range

Tips:
* python sorted can use lambda function
* we don’t need to use binary tree for this one, a simple sort can solve the problem

```python class Solution: def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ res=[] if len(intervals) == 0: return res intervals = sorted(intervals, key=lambda interval: interval.start) start =intervals.start end =intervals.end for i, interval in enumerate(intervals): if interval.start <= end: start = min(start, interval.start) end = max(end, interval.end) else: res.append(Interval(start, end)) start = interval.start end = interval.end res.append(Interval(start, end)) return res```
### 13. Majority Element
For those who aren’t familiar with Boyer-Moore Majority Vote algorithm,
I found a great article (http://goo.gl/64Nams) that helps me to understand this fantastic algorithm!!

The essential concepts is you keep a counter for the majority number X. If you find a number Y that is not X, the current counter should deduce 1. The reason is that if there is 5 X and 4 Y, there would be one (5-4) more X than Y. This could be explained as “4 X being paired out by 4 Y”.

And since the requirement is finding the majority for more than ceiling of [n/3], the answer would be less than or equal to two numbers.
So we can modify the algorithm to maintain two counters for two majorities.

``````class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
count1 =0
count2 =0
cand1 =0
cand2=1
for x, n in enumerate(nums):
if n == cand1:
count1 +=1
elif n == cand2:
count2 +=2
elif count1 == 0:
cand1 = n
count1 +=1
elif count2 == 0:
cand2 =n
count2 +=1
else:
count1 -= 1
count2 -= 1
return [n for n in (cand1, cand2) if nums.count(n) > len(nums)/3]

``````

### 14. Permutation

Usually the idea of getting permutation is to:
– limit the condition
– use backtrace to get all possible results

There is one question to get next permutation

The idea is to assume the next permutation should be follow the order. We can use single-pass method to get the result

``````class Solution:
def swap(self, nums, i, j):
tem = nums[i]
nums[i] = nums[j]
nums[j] = tem
def reverse(self, nums, i, j):
while i <= j:
self.swap(nums, i, j)
i+=1
j-=1
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = len(nums) - 2
while i >= 0 and nums[i+1] <= nums[i]:
i -=1
if i >= 0:
j = len(nums) -1
while j >=0 and nums[j] <= nums[i]:
j -=1
self.swap(nums,i, j)
self.reverse(nums, i+1, len(nums) - 1)

``````

### 15. Palindrome

we need to consider different situation
e.g. if the string is Palindrome
– all char is even
– one char is odd, all others are even

Then we can convert this question into the permutation issue and use back trace to get the result

``````class Solution:
def backTracing(self, nums, ans, pos, res, oddc):
# print(ans)
if len(ans) == len(nums):
ans += [oddc] + ans[::-1]
res.append(''.join(str(ans[y]) for y in range(len(ans))))
return
else:
dup = []
for x in range(len(nums)):
# print("x:",x,"nums[x]:",nums[x],"dup:",dup, "pos:",pos, "ans:",ans)
if not x in pos and not nums[x] in dup:
dup.append(nums[x])
self.backTracing(nums, ans + [nums[x]], pos+[x], res, oddc)
return

def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
if len(s) == 0:
return []

ul = dict()
for x in s:
if not x in ul:
ul.setdefault(x, 1)
else:
ul[x] += 1

oddc = ''
oddCount = 0
for x in ul.keys():
if ul[x] %2 != 0:
oddc = x
oddCount += 1
ul[x] = int((ul[x]-1)/2)
else:
ul[x] = int(ul[x]/2)
if oddCount >1:
return []
nums = []
for x in ul.keys():
while ul[x] >0:
nums += [x]
ul[x] -=1
res = []
# print(nums)
self.backTracing(nums, [], [], res, oddc)
return res

``````

### 16. preorder and inorder of tree

The basic idea is here:
Say we have 2 arrays, PRE and IN.
Preorder traversing implies that PRE is the root node.
Then we can find this PRE in IN, say it’s IN.
Now we know that IN is root, so we know that IN – IN is on the left side, IN to the end is on the right side.
Recursively doing this on subarrays, we can build a tree out of it 🙂

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def build(self, preorder, postart, poend, inorder, iostart, ioend):
if postart > poend or iostart > ioend:
return None
root = TreeNode(preorder[postart])
inorderBreakMark = iostart
for x in range(iostart, ioend+1):
if inorder[x] == preorder[postart]:
inorderBreakMark = x
leftL = inorderBreakMark-iostart
root.left = self.build(preorder, postart+1, postart+leftL, inorder, iostart, inorderBreakMark-1)
root.right = self.build(preorder, postart+leftL + 1, poend, inorder, inorderBreakMark+1, ioend)
return root

def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
root = self.build(preorder, 0, len(preorder)-1, inorder, 0 ,len(inorder)-1  )
return root

``````

### 17 Greedy

Greedy is a special case of DP
Greedy: for each step we only consider the current best solution, because we belive if we choose the current best solution for each step, the final result is the best solution for all

DP: We calculate all solution

``````class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
lastpos = len(nums)-1
for x in range(len(nums)-2, -1, -1):
if x + nums[x] >= lastpos:
lastpos = x
return lastpos == 0

``````

a good example to tell the difference between greedy and dp is link

### 18 quick sort

this is a good example about quick sort
We can use the simple solution: two points from left to right and swap if it is min

Another good solution is:
The idea is to sweep all 0s to the left and all 2s to the right, then all 1s are left in the middle.

It is hard to define what is a “one-pass” solution but this algorithm is bounded by O(2n), meaning that at most each element will be seen and operated twice (in the case of all 0s). You may be able to write an algorithm which goes through the list only once, but each step requires multiple operations, leading the total operations larger than O(2n).

``````class Solution:
def swap(self, nums, start, end):
temp = nums[start]
nums[start] = nums[end]
nums[end] = temp

def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
low = 0
high = len(nums) - 1
i = low
while i <= high:
if nums[i] == 0:
self.swap(nums, i, low)
low += 1
i += 1
elif nums[i] == 2:
self.swap(nums, i, high)
high -= 1
else:
i += 1
``````

### 19 Two points

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.

``````class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 0
for num in nums:
if count < 2 or nums[count-2] < num:
nums[count] = num
count += 1
return count

``````

## Summary of Array algorithms questions (easy)

Recently I spent few hours on going through algorithm questions in leetcode. I haven’t touched the algorithm question for 2 years but I think it’s a good time to review those questions in a better way.

From my experience,  the thinking strategy of solving similar problems is limited. Those strategies cannot help you solve all problems relevant to Array but it may be a good beginning of analyzing those algorithm tricks.

The core is the math

1. Hash Table
2. shifting the array from beginning to the end or with odd & even order
3. use *-1 as a mark
4. two indexes, two-way or one-way moving,  or 1 , n-1
5. convert the index into other marks e.g. content vice versa
6. if it’s matrix, sum the columns and rows
7. switch i and i+1  bubble sort
8. use mid number  quicksort