Reverse Pairs

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.


Input: [1,3,2,3,1]
Output: 2


Input: [2,4,3,5,1]
Output: 3


  1. The length of the given array will not exceed 50,000.
  2. All the numbers in the input array are in the range of 32-bit integer.
# Solution 1: Using Binary Index Tree, which has O(nlogn) time complexity.

class BIT():
    def __init__(self, n):
        self.n = n + 1
        self.sums = [0] * self.n

    def update(self, i, delta):
        while i < self.n:
            self.sums[i] += delta
            i += i & (-i)

    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        sorted_nums = sorted(list(set(nums + [x * 2 for x in nums])))
        tree = BIT(len(sorted_nums))

        res = 0
        ranks = {}

        for i, n in enumerate(sorted_nums):
            ranks[n] = i + 1

        for n in nums[::-1]:
            res += tree.query(ranks[n] - 1)
            tree.update(ranks[n * 2], 1)

        return res
# Solution 2: At this time, we are going to use bisect. Got inspiration from Merge Sort (Divide and Conquer).

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        ranks = list()
        ans = 0

        for n in reverse(nums):
            ans += bisect.bisect_left(ranks, n)
            bisect.insort_left(ranks, n * 2)

        return ans

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.


Input: [2,1,5,6,2,3]
Output: 10

Actually, I have met this problem on the online assessment of Amazon a few days ago.


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [-1]
        ans = 0
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, h * w)

        return ans

Is Graph Bipartite?

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
The graph looks like this:
|    |
|    |
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
The graph looks like this:
| \  |
|  \ |
We cannot find a way to divide the set of nodes into two independent subsets.


  • graph will have length in range [1, 100].
  • graph[i] will contain integers in range [0, graph.length - 1].
  • graph[i] will not contain i or duplicate values.
  • The graph is undirected: if any element j is in graph[i], then i will be in graph[j].
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = collections.defaultdict(lambda: -1)
        def dfs(v, cur_color):
            if color[v] != -1: return color[v] == cur_color
            color[v] = cur_color
            return all(dfs(e, cur_color ^ 1) for e in graph[v])
        return all(dfs(v, 0) for v in range(len(graph)) if color[v] == -1)

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.


  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
# TLE solution
class Solution:
    def helper(self, s):
        if not s: return True
        return any(self.helper(s[len(word):]) for word in self.wordDict if s.startswith(word))
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.wordDict = wordDict
        return self.helper(s)
# Basic DP
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * len(s)    
        for i in range(len(s)):
            for word in wordDict:
                if s[:i+1].endswith(word) and (dp[i-len(word)] or i-len(word) == -1):
                    dp[i] = True
        return dp[-1]
# Advanced DP
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True]
        for i in range(1, len(s)+1):
            dp += any(dp[j] and s[j:i] in wordDict for j in range(i)),
        return dp[-1]

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

History is always recurrent.

At the very first, I thought it is a typical dp question, and then I wrote a classical dp solution, and then I got a TLE…

This AC solution I actually checked it out from discuss board, that is really smart.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        N = len(nums)
        first = float("inf")
        second = float("inf")

        for i in range(N):
            if nums[i] < first:
                first = nums[i]
            elif first < nums[i] < second:
                second = nums[i]
            if nums[i] > second:
                return True

        return False

Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = dict()
        # Build graph
        for (a, b), value in zip(equations, values):                
            graph[a] = graph.get(a, []) + [(b, value)]
            graph[b] = graph.get(b, []) + [(a, 1/value)]

        def check(source, target):   
            # If there is any one number of the query didn't appear in the graph, answer certainly doesn't exist.
            if source not in graph or target not in graph:
                return -1.0
            visited = set()
            stack = collections.deque([(source, 1.0)])
            while stack:
                front, current = stack.popleft()
                if front == target:
                    return current
                for back, value in graph[front]:
                    if back not in visited:
                        stack.append((back, current * value))
            return -1.0
        return [check(source, target) for (source, target) in queries]

Implement Trie (Prefix Tree)



到了州立图书馆之后,本来是说要去吃DonDon的,但是想到学校旁边的Don Tojo就突然想吃点别的了。于是找了一家网红店吃了一份鳗鱼饭。



之后回学校坐定开始学校,打算随手水道题,于是瞄了一眼问题列表,选了Trie Tree。

以前写Trie都是要写好久的,但是这次居然五分钟不到就一次性Bug Free了,蛮开心的。

↓Code inside ↓

Continue reading

Missing Ranges

Given a sorted integer array nums, where the range of elements are in the inclusive range [lowerupper], return its missing ranges.


Input:   nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]
class Solution:
    def findMissingRanges(self, nums, lower: int, upper: int):
        nums.insert(0, lower-1) # Left Bound
        nums.append(upper+1)    # Right Bound
        res = []

        for i in range(len(nums)-1):
            left, right = nums[i], nums[i + 1]

            if left != right:
                if right - left == 2:
                elif right - left > 2:
                    res.append(str(left+1) + "->" + str(right-1))

        return res

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.


Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        ans = 0
        for x in nums:
            # Find the first element in one segment
            if x-1 not in nums:
                y = x + 1
                # reach the last consecutive element in one element  
                while y in nums:
                    y += 1
                ans = max(ans, y - x)
        return ans
class Solution:
    def longestConsecutive(self, nums) -> int:
        UF = {}
        nums = set(nums)

        if not nums:
            return 0

        # for num in nums:
        #     UF[num] = num

        def find(x):
            if x != UF[x]:
                UF[x] = find(UF[x])
            return UF[x]

        def union(x, y):
            UF.setdefault(x, x)
            UF.setdefault(y, y)
            UF[find(x)] = find(y)

        for n in nums:
            if (n - 1) in nums:
                union(n - 1, n)
            if (n + 1) in nums:
                union(n, n + 1)

        ans = 1

        for num in nums:
            if num in UF:
                ans = max(ans, find(num) - num + 1)
        return ans