Recently I tried to solve the interesting questions on leetcode. I think the thinking strategy should be recorded here.
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
link
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 = [[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
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).
If the target is not found in the array, return[-1, -1].
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] == 3
l r
1 2 3 3 3 4 5 mid = 1 nums[1] == 2 <3
l r
1 2 3 3 3 4 5 mid = 1 nums[1] == 2 <3
l r
1 2 3 3 3 4 5 mid = 2 nums[2] == 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[2] = 3
l r
3 3 3 4 5 mid = 3 nums[3] > 3
l r
3 3 3 4 5 mid = 2 nums[2] = 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[2] = 3
l r
3 3 3 4 5 mid = 3 nums[3] > 3
l r
3 3 3 4 5 mid = 3 nums[3] =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[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]
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
link
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[0] is the root node.
Then we can find this PRE[0] in IN, say it’s IN[5].
Now we know that IN[5] is root, so we know that IN[0] – IN[4] is on the left side, IN[6] 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
Greedy Example linke
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
link
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
Follow up for “Remove Duplicates”:
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
