Month: November 2018

Link: Most Stones Removed with Same Row or Column

Thought

When I saw the question, I realized its a Union Find question – For any union, I can keep only one stone form it. Then it convert to a count how many unique union finds exist question. 

So, only need to count all unique union find, and use all nodes to minus it. 

Code

class Solution:
    def removeStones(self, stones):
        """
        :type stones: List[List[int]]
        :rtype: int
        """
        N = len(stones)
        nodes = dict()
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        counter = set()
        for x, y in stones: # pre process
            nodes[(x,y)] = (x,y)
            cols[x].add(y)
            rows[y].add(x)
        def find(x,y):
            if nodes[(x,y)]!= (x,y):
                nx,ny = find(*nodes[(x,y)])
                nodes[(x,y)] = (nx,ny)
            return nodes[(x,y)]
        def union(x,y,x2,y2):
            n_x , n_y = find(x,y)
            nn_x, nn_y = find(x2,y2)
            nodes[(nn_x,nn_y)] = (n_x, n_y)
        for x, y in stones:
            for y2 in cols[x]:
                union(x,y,x,y2)
            for x2 in rows[y]:
                union(x,y, x2,y)
        maxx = 0
        for x,y in stones:
            r_x, r_y = find(x,y)
            counter.add((r_x,r_y))
        return N - len(counter) 

Runtime

Time: O(n^2)

Space: O(n)

Link:  validate stack sequences

Thought

Its pretty straight forward, just stimulate a stack and push/pop as the sequence shows. 

Code

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        stack = []
        visited = set()
        N = len(popped)
        j = 0
        for i in pushed:
            stack.append(i)
            while stack and stack[-1] == popped[j] and j < N:
                stack.pop()
                j += 1
        if stack:
            return False
        return True

Runtime

Time: O(n)

Space: O(n)

Link: Bag of Tokens

Thought

For this question, I find we could do 2 things: spend any cost form the tokens, and get 1 point. Or, spend 1 point, get any power from the tokens. So it turns to be pretty clear that I will firstly sort all tokens by value, and trying to get as much point as possible by flipping from left(smaller) side. If I can not flip any more, try to gain as much power as possible(AKA from right side).

And during the same time, keep tracking the maximum points I can get.

Code

class Solution(object):
    def bagOfTokensScore(self, tokens, P):
        """
        :type tokens: List[int]
        :type P: int
        :rtype: int
        """
        tokens.sort()
        init = 0
        maxx = 0
        lindx = 0
        rindx = len(tokens) - 1
        while lindx <= rindx:
            while lindx <= rindx and tokens[lindx] <= P:
                P -= tokens[lindx]
                init += 1
                lindx += 1
            maxx = max(maxx, init)
            if init == 0:
                break
            if lindx <= rindx:
                init -= 1
                P += tokens[rindx]
                rindx -= 1
        return maxx

Runtime

Time: O(NlogN)

Space: O(1)

Link Minimum Increment to Make Array Unique

Thought

Firstly, I try to enumerate all existing number, and I got TLE :(. Then I realized I could sort the origin array and maintain a upper boundary, for any number, if it smaller than upper boundary, means I can only move it to upper boundary + 1 and count the moves. Otherwise, set the upper boundary to that number and keep going. 

Code

class Solution(object):
    def minIncrementForUnique(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if not A:
            return 0
        p = dict()
        A.sort()
        cnt = 0
        upper = A[0]
        for i in A[1:]:
            if i <= upper:
                upper +=1
                cnt += upper - i
            else:
                upper = i 
        return cnt

Runtime

Time: O(nlogn)
Space: O(1)

link: Minimum Area Rectangle

Thought

I plan to use sweep line to solve. Firstly I put a dictionary with x-val as key, all y-val with coordinate x-val as value. Then, once I check x1, x2, if they has intersection, means there could be a rectangle. So I could enumerate all possible rectangles and record the smallest one. 

Code

class Solution:
    def minAreaRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if not points or len(points) < 4:
            return 0
        res = 0
        lookup = collections.defaultdict(set)
        minimum = 2**32
        for node in points:
            lookup[node[0]].add(node[1])
        keys = list(lookup.keys())
        keys.sort()
        for j in range(len(keys)):
            for i in range(j):
                cross = list(lookup[keys[i]].intersection(lookup[keys[j]]))
                if len(cross) >= 2:
                    cross.sort()
                    for k in range(len(cross) - 1):
                        if (cross[k + 1] - cross[k]) * (keys[j] - keys[i]) < minimum:
                            minimum = (cross[k + 1] - cross[k]) * (keys[j] - keys[i])
                            res = minimum
        return res

Runtime

Time: O(n^3)
Space: O(n)

link: Range Sum of BST

Thought

When first saw this question, I think using tree traverse could solve it and it did works.

Code

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

class Solution:
    def rangeSumBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: int
        """
        self.res = 0
        def helper(root): # helper function to traverse tree
            if not root:
                return
            if L <= root.val <= R:
                self.res += root.val
                helper(root.left)
                helper(root.right)
            elif root.val < L:
                helper(root.right)
            else:
                helper(root.left)
        helper(root)
        return self.res

Runtime

Time O(n)
Space O(n)

link Distinct Subsequences II

Thought

The very first thought here is use DFS to find all distinct subsequences. However it will time out. So my next idea is using dynamic programming to solve it. I’ll define a DP array, where DP[i + 1] stands for how many distinct subsequences if I use 0,1,…i characters to build sub sequences, end with character i. DP[0] is special because it stands for empty condition and should always be 1.

Then, the state transfer funtion is:

DP[i] = sum(DP[i-1], DP[i-2], … DP[0])

Next, lets think about dumplicate. Assume the case “abaca”. When I see the last ‘a’, what should I put in DP[5]? I should only count DP[3],DP[4] cause DP[2] + ‘a’ is already computed in DP[3]. So I put another dictionary, with character as key, its last index so far as value. Then the state transfer function change a little bit to:

DP[i] = sum(DP[i-1], DP[i-2], … DP[last_time_same_character_appears])

And remember DP[0] stands for empty result, when we count final results, we should emit it.

Code

class Solution:
    def distinctSubseqII(self, S):
        """
        :type S: str
        :rtype: int
        """
        MOD = 10**9 + 7
        N = len(S)
        DP = [0] * (N + 1)
        DP[0] = 1
        lookup = collections.defaultdict(int)
        for index, val in enumerate(S):
            q = index
            prev = lookup[val]
            DP[index + 1] = sum(DP[prev:])  % MOD
            lookup[val] = index + 1
        return sum(DP[1:]) % MOD

Runtime

Time: O(n^2)
Space: O(n)

link: Number of Recent Calls

Thought

Question ask for numbers of calls in 3000. So sliding windows is my choice here – it will move and drop calls earlier than 3000 – which I don’t care, and keep tracing incoming calls.

Code

class RecentCounter:

    def __init__(self):
        self.t = collections.deque()
        self.cnt = 0

    def ping(self, t):
        """
        :type t: int
        :rtype: int
        """
        while self.t and self.t[0] < t - 3000:
            self.t.popleft()
            self.cnt -= 1
        self.t.append(t)
        self.cnt += 1
        return self.cnt

Runtime

Time: O(n)
Space: O(n)

link Knight Dialer

Thought

Since it ask how many distinct numbers could be generated, DP jumps to my mind immediately. Firstly, the relation is, if knight stop at number 6, it has to come from 1, 7, or 0. So I keep a DP array, DP[j][i] stands for how many unique numbers it could generate if knight jumps j steps and stops at i position. Then, I find actually DP[j+i] only depends on DP[j] level, so I could optimize 2D DP array into 1D array.

One tircky part to notice: DP[1][5] is 1, other than that, DP[j][5] is 0 iif j > 1.

Code

class Solution:
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        MOD = 10**9 + 7
        DP = [1] * 10 #init state
        for hops in range(N-1):
            Q = [0] * 10
            Q[0] = (DP[4] + DP[6]) % MOD
            Q[1] = (DP[8] + DP[6]) % MOD
            Q[2] = (DP[7] + DP[9]) % MOD
            Q[3] = (DP[4] + DP[8]) % MOD
            Q[4] = (DP[3] + DP[0] +DP[9]) % MOD
            Q[6] = (DP[1] +DP[7] + DP[0]) % MOD
            Q[7] = (DP[2] + DP[6]) % MOD
            Q[8] = (DP[1] + DP[3]) % MOD
            Q[9] = (DP[4] + DP[2]) % MOD
            DP = Q
        return sum(DP) % MOD

Runtime

Time: O(n) Space: O(n)

link: Shortest Bridge

Thought

Since the question ask for shortest, so BFS probabely the best algorithms to solve it. But notice, I will use 2 bfs funciton, one to find the edge of first island, the other one is to reach another island based on first edge.

BFS1:

input: start position
stop condition: queue empty
generate & expansion rule: find all its neighbors, mark as visited, and put ‘1’ to queue -> will put that node in queue for further processing.
put ‘0’ to result queue ->thats what we want to return!

BFS2

input: edge of first island
stop condition: reach any grid with number ‘1’ -> find second island
generate & expansion rule: for any node in que, expend its unvisited neighbors in queue. And also record the level number.

Code

class Solution:
    def shortestBridge(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        delta = ((0,1), (1,0), (0,-1), (-1,0))
        N = len(A)
        visited = set()
        def bfs1(x,y):
            # get the edge of first one
            visited.add((x,y))
            que = collections.deque()
            que.append((x,y))
            result = collections.deque()
            while que:
                c_x,c_y = que.popleft()
                if A[c_x][c_y] == 0:
                    result.append((c_x,c_y))
                    continue
                for dx,dy in delta:
                    nx,ny = dx+c_x, dy+c_y
                    if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:
                        que.append((nx,ny))
                        visited.add((nx,ny))
            return result
        def bfs2(starts):
            cnt = 0
            while starts:
                siz = len(starts)
                for i in range(siz):
                    c_x,c_y = starts.popleft()
                    if A[c_x][c_y] == 1:
                        return cnt
                    for dx,dy in delta:
                        nx,ny = dx+c_x, dy+c_y
                        if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:
                            starts.append((nx,ny))
                            visited.add((nx,ny))
                cnt += 1
        for i in range(N):
            for j in range(N):
                if A[i][j] == 1: # find start position 
                    t = bfs1(i,j) # get the edge
                    return bfs2(t) # get level number

Runtime

Time: O(n^2)
Space: O(n^2)