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

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

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).

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

Leave a Reply

Your email address will not be published. Required fields are marked *