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

### 2. when calculating the sum of an array with the combination, backtracking should be considered first

### 3. Dynamic programming

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

e.g. get the best result of the problem.

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 ++

```
class Solution:
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
hashTable = [[0]* (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[0]
minpre = nums[0]
maxnow = maxpre
minnow = minpre
maxsofar = nums[0]
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 n*C, v = a*C + 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

### 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[0])
maxcount = 0
dp = [ [[0]*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][0] = dp[r][c-1][0] + 1 if c > 0 else 1
dp[r][c][1] = dp[r-1][c][1] + 1 if r > 0 else 1
dp[r][c][2] = dp[r-1][c+1][2] +1 if r > 0 and c < columns -1 else 1
dp[r][c][3] = dp[r-1][c-1][3] +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[0])
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= [[0]*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[0] = 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[0]*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[0].start

end =intervals[0].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!!

Please check it out!

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]
```