LeetCode [220/221]

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

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

Example 2:

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

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

class Solution(object):
    def firstMissingPositive(self, nums):
        l = len(nums)
        for i in range(l):
            # Note!: here has to be using while
            while (nums[i] > 0 and nums[i] <= l and nums[nums[i] - 1] != nums[i]):
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]

        for i, n in enumerate(nums):
            if (n != i+1):
                return i + 1

        return l + 1

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)

        for i in range(n//2):
            # Shrink the dimension
            # Do not include the last element
            for j in range(i, n-i-1):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[n-1-j][i]
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
                matrix[j][n-1-i] = tmp

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Solution().rotate(matrix)
[print(*line) for line in matrix]

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)

        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        for i in range(n):
            matrix[i].reverse()

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Solution().rotate(matrix)
[print(*line) for line in matrix]

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        curSum = maxSum = nums[0]

        for num in nums[1:]:
          curSum = max(num, curSum+num)
          maxSum = max(curSum, maxSum)

        return maxSum

print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if len(nums) == 0:
            return 0

        ret = nums[0]

        for i in range(1, len(nums)):
            if nums[i - 1] > 0:
                nums[i] += nums[i - 1]

            ret = max(ret, nums[i])

        return ret
print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

reach = max(i + nums[i], reach) if i <= reach

lastPos = i if i + nums[i] >= lastPos

class Solution():
    def canJump(self, nums):
        reach = 0

        for i in range(len(nums)):
            if i <= reach:
                reach = max(i + nums[i], reach)
            else:
              break

        return reach >= len(nums) - 1

print(Solution().canJump([ 2,3,1,1,4 ]))
print(Solution().canJump([ 3,2,1,0,4 ] ))

class Solution():
    def canJump(self, nums):
        lastPos = len(nums) - 1
        for i in reversed(range(len(nums))):
            if i + nums[i] >= lastPos:
                lastPos = i

        return lastPos == 0

print(Solution().canJump([ 2,3,1,1,4 ]))
print(Solution().canJump([ 3,2,1,0,4 ] ))

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:

Input: m = 7, n = 3
Output: 28

dp[i][j] = dp[i-1][j] + dp[i][j-1]

dp[j] = dp[j - 1] + dp[j]

class Solution():
    def uniquePath(self, m, n):
        dp = [[1 for j in range(n)] for i in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

        return dp[-1][-1] if m and n else 0

class Solution():
    def uniquePath(self, m, n):
        dp = [1] * n

        for i in range(1, m):
            for j in range(1, n):
                dp[j] = dp[j - 1] + dp[j]

        return dp[-1] if m and n else 0

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])

        for i in range(m):
            for j in range(n):
                if i == 0:
                    if j == 0:
                        continue
                    else:
                        grid[i][j] += grid[i][j-1]
                else:
                    if j == 0:
                        grid[i][j] += grid[i-1][j]
                    else:
                        grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[-1][-1] if m and n else 0


grid = [[1,3,1],[1,5,1],[4,2,1]]

print(Solution().minPathSum(grid))

import sys
class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])

        dp = [[ 0 for i in range(n+1)] for j in range(m+1)]

        for i in range(len(dp)):
          dp[i][0] = sys.maxsize

        for i in range(len(dp[0])):
            dp[0][i] = sys.maxsize

        dp[1][1] = grid[0][0]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if i == 1 and j == 1:
                    continue
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]


        return dp[-1][-1] if m and n else 0


grid = [[1,3,1],[1,5,1],[4,2,1]]

print(Solution().minPathSum(grid))

import sys


class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])

        dp = [sys.maxsize for i in range(n + 1)]
        dp[1] = grid[0][0]

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                else:
                    dp[j + 1] = min(dp[j + 1], dp[j]) + grid[i][j]

        return dp[-1] if m and n else 0


grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

print(Solution().minPathSum(grid))

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

class Solution():
    def climbStairs(self, n):
        if n < 2:
            return n

        dp = [0] * n

        dp[0] = 1
        dp[1] = 2

        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[-1]

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

class Solution():
    def numsDecodings(self, s):

        if not s:
          return 0

        n = len(s)

        dp = [0] * (n + 1)

        dp[0] = 1

        for i in range(1, n+1):

            if s[i-1: i] != '0':
                dp[i] = dp[i-1]

            if i != 1 and '10' <= s[i-2:i] <= '26':
                dp[i] += dp[i-2]

        return dp[-1]

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).



Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

class Solution(object):
    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """
        if N < 2:
            return N

        dp = [0] * (N + 1)

        dp[0] = 0
        dp[1] = 1

        for i in range(2, N + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[-1]

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?

class Solution:

    def subsets(self, nums):
        res = [[]]
        for i in sorted(nums):
            res += [item+[i] for item in res]

        return res

print(Solution().subsets([1, 2, 3]))

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

class Solution(object):
    def subsets(self, nums):
        res = []
        self.dfs(sorted(nums), 0, [], res)
        return res

    def dfs(self, nums, index, path, res):
        res.append(path)
        for i in range(index, len(nums)):
            self.dfs(nums, i + 1, path + [nums[i]], res)

class Solution:
    def subsets(self, nums):
        res = [[]]
        for i in sorted(nums):
            res += [item+[i] for item in res]
        return res

class Solution(object):

    def subsets(self, nums):
        output = []
        for k in range(0, len(nums)+1):
            temp = []
            self.backtrack(0, k, nums, temp, output)

        return output

    def backtrack(self, begin, length, nums, temp, output):

        if length == len(temp):
            output.append(temp[:])

        for i in range(begin, len(nums)):
            temp.append(nums[i])
            self.backtrack(i+1, length, nums, temp, output)
            temp.pop()


print(Solution().subsets([1, 2, 3]))

class Solution():
  def subsets(self, nums):
    n = len(nums)
    output = []
    for i in range(2**n, 2**(n+1)):
      bitmask = bin(i)[3:]
      output.append([nums[i] for i in range(n) if bitmask[i] == '1' ])

    return output

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, word, 0, i, j):
                    return True
        return False

    def dfs(self, board, word, w, i, j):
        if w == len(word):
            return True

        if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]):
            return False

        if board[i][j] == word[w]:
            board[i][j] = '-'

            for next_i, next_j in [[i + 1, j], [i - 1, j], [i, j - 1],
                                   [i, j + 1]]:
                if self.dfs(board, word, w + 1, next_i, next_j):
                    return True

            board[i][j] = word[w]

        return False

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:

You can assume that you can always reach the last index.

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

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.

Example:

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

class Solution:
    def largestRectangleArea(self, heights):

        if not heights:
            return 0

        n = len(heights)
        res = 0

        left = [ i for i in range(n) ]
        right = [ i for i in range(n) ]

        # caculate for the left edge
        for i in range(n):
            p = i
            while p >= 0:
                if heights[p] < heights[i]:
                    break
                p -= 1
            left[i] = p

        # caculate for the right edge
        for i in range(n):
            p = i
            while p < n:
                if heights[p] < heights[i]:
                    break
                p += 1
            right[i] = p

        for i in range(n):
            res = max(res, heights[i] * (right[i] - left[i] - 1))

        return res

print(Solution().largestRectangleArea([2, 1, 5, 6, 2, 3]))

10

class Solution:
    def largestRectangleArea(self, heights):
        if not heights:
            return 0

        res = 0
        n = len(heights)
        left = [1] * n
        right = [1] * n

        # caculate left[]
        for i in range(n):
            p = i - 1
            while p >= 0:
                if heights[p] >= heights[i]:
                    left[i] += left[p]
                    # jump backward
                    p -= left[p]
                else:
                    break

        # caculate right[]
        for i in range(n - 1, -1, -1):
            p = i + 1
            while p < n:
                if heights[p] >= heights[i]:
                    right[i] += right[p]
                    # jump forward
                    p += right[p]
                else:
                    break

        for i in range(n):
            res = max(res, heights[i] * (left[i] + right[i] - 1))

        return res

print(Solution().largestRectangleArea([2, 1, 5, 6, 2, 3]))

class Solution:
    def largestRectangleArea(self, heights):

        stack = []
        n = len(heights)
        res = 0
        index = 0

        while index < n:

            if not stack or heights[stack[-1]] <= heights[index]:
                stack.append(index)
                index += 1
            else:
                top = stack.pop()
                area = (heights[top] *
                        ((index - stack[-1] - 1) if stack else index))

                res = max(res, area)

        while stack:
            h = stack.pop()
            res = max(
                r

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        valley = prices[0]
        maxProfit = 0
        res = 0

        for price in prices:
            if price - valley < maxProfit:
                valley = price # new valley
                res += maxProfit # add the current maxProfit
                maxProfit = 0 # reset current maxProfit
            else:
                maxProfit = price - valley # update the maxProfit when we still go up

        # remember to add the last maxProfit.
        # 1. When we are on the peak. maxProfit > 0, it should be added
        # 2. When we are in the vally, maxProfit = 0, would not affect the value
        res += maxProfit

        return res

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution:
    def maxProfit(self, prices):
        max_k = 2
        dp = [ [ [0] * 2 for k in range(max_k + 1) ] for i in range(len(prices))]
        for i in range(len(prices)):
            for k in range(1, max_k + 1):
                if i == 0:
                    dp[i][k][0] = 0
                    dp[i][k][1] = -prices[i]
                else:
                    dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
                    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

        return dp[-1][max_k][0]

import sys
class Solution:
    def maxProfit(self, prices):
        buy = [-sys.maxsize] * 3
        sell = [0] * 3
        for price in prices:
            buy[1] = max(buy[1], sell[0]-price)
            buy[2] = max(buy[2], sell[1]-price)
            sell[1] = max(sell[1], buy[1]+price)
            sell[2] = max(sell[2], buy[2]+price)
            print(buy)
            print(sell)
        return sell[2]

print(Solution().maxProfit([3,3,5,0,0,3,1,4]))

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

class Solution:
    def mergeTwoLists(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1

        if l1.val > l2.val:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
        else:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3


But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

class Solution:
    def rob(self, nums):
        robbed, notRobbed = 0, 0
        for i in nums:
            robbed, notRobbed = notRobbed + i, max(robbed, notRobbed)

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

class Solution:
    def lengthOfLIS(self, nums):
        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
               if nums[j] < nums[i]:
                   dp[i] = max(dp[i], dp[j] + 1)

       return max(dp) if nums else 0

class Solution:
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        dp = [nums[0]]
        for i in range(1, len(nums)):
            if nums[i] > dp[-1]:
                dp.append(nums[i])
            else:
                j = self.binarySearch(dp, nums[i])
                dp[j] = nums[i]

        return len(dp)

    def binarySearch(self, nums, target):
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid

        return l

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

class Solution:
    def coinChange(self, coins, amount):
        dp = [float('inf')] * (amount + 1)

        dp[0] = 0

        for i in range(1, amount + 1):
            for j in range(len(coins)):
                if i - coins[j] >= 0:
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1)

        return dp[-1] if dp[-1] != float('inf') else -1

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

class Solution:
    def maxProduct(self, nums):
        if not nums:
            return 0

        dp = [[0] * 2 for i in range(len(nums))]
        res = dp[0][0] = dp[0][1] = nums[0]

        for i in range(1, len(nums)):
            if nums[i] >= 0:
                dp[i][0] = max(nums[i], dp[i - 1][0] * nums[i])
                dp[i][1] = dp[i - 1][1] * nums[i]
            else:
                dp[i][0] = dp[i - 1][1] * nums[i]
                dp[i][1] = min(nums[i], nums[i] * dp[i - 1][0])
            res = max(res, dp[i][0])
        return res

class Solution:
    def maxProduct(self, nums):
        if not nums:
            return 0

        pos = neg = res = nums[0]
        for i in nums[1:]:
            if i>=0:
                pos = max(i, pos*i)
                neg = neg*i
            else:
                tmp = pos # Important: remember the value, because we are gonna alter it.
                pos = neg*i
                neg = min(tmp*i, i) # Use the original value
                # We also can write as this, but we should notice it only works in like python or ruby
                # pos, neg = neg*i, min(pos*i, i), simplify to version 3
            res = max(pos, res)
        return res

class Solution:
    def maxProduct(self, nums):
        if not nums:
            return 0

        pos = neg = res = nums[0]
        for i in nums[1:]:
            if i>=0:
                pos, neg = max(i, pos*i), neg*i
            else:
                pos, neg = neg*i, min(i, pos*i)
            res = max(pos, res)
        return res

class Solution:
    def maxProduct(self, nums):
        rnums = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i-1] or 1
            rnums[i] *= rnums[i-1] or 1
        return max(nums+rnums)

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Cn = 1/(n+1)(2n n) = (2n)!/(n+1)!n!

The first Catalan numbers for n = 0, 1, 2, 3, ... are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190,
6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452

class Solution:
    def numTrees(self, n):
        if n < 1:
            return 0

        dp = [0] * (n+1)
        dp[0] = 1

        for i in range(1, n+1):
            for j in range(0, i):
                dp[i] += dp[j]*dp[i-1-j]

        return dp[n]

import math
class Solution:
    def numTrees(self, n):
        return math.factorial(2*n)/(math.factorial(n)*math.factorial(n+1))

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

class Solution:
    def maximalSquare(self, matrix):
        if not matrix:
            return 0

        dp = [[[0] * 3 for j in range(len(matrix[0]) + 1)] for i in range(len(matrix) + 1)]
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "1":
                    dp[i + 1][j + 1][0] = dp[i][j + 1][0] + 1
                    dp[i + 1][j + 1][1] = dp[i + 1][j][1] + 1
                    dp[i + 1][j + 1][2] = min(dp[i][j][2]+1, dp[i + 1][j + 1][0], dp[i + 1][j + 1][1])
                    res = max(res, dp[i + 1][j + 1][2])

        return res*res

class Solution:
    def maximalSquare(self, matrix):
        if not matrix:
            return 0

        dp = [[0] * 3 for j in range(len(matrix[0]) + 1)]
        res = 0

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "1":
                    dp[j+1][0] = dp[j+1][0] + 1
                    dp[j+1][1] = dp[j][1] + 1
                    dp[j+1][2] = min(dp[j+1][2]+1, dp[j+1][0]+1, dp[j][1]+1)
                    res = max(res, dp[j + 1][2])
                else:
                    dp[j+1][0] = dp[j+1][1] = dp[j+1][2] = 0

        return res*res

class Solution:
    def maximalSquare(self, matrix):
        if not matrix:
            return 0

        dp = [0 for j in range(len(matrix[0]) + 1)]
        res = 0
        prev = 0 # previous diagnol element

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                temp = dp[j+1]
                if matrix[i][j] == "1":
                    dp[j+1] = min(prev, dp[j+1], dp[j]) + 1
                    res = max(res, dp[j + 1])
                else:
                    dp[j+1] = 0

                prev = temp

        return res*res

class Solution:
    def maximalSquare(self, matrix):
        if not matrix:
            return 0
        res = 0
        m = len(matrix)
        n = len(matrix[0])

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "1":
                    if i == 0 or j == 0:
                        matrix[i][j] = 1
                    else:
                        matrix[i][j] = min(matrix[i - 1][j - 1],
                                           matrix[i][j - 1],
                                           matrix[i - 1][j]) + 1
                    res = max(res, matrix[i][j])
                else:
                    matrix[i][j] = 0

        return res * res

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

import math
class Solution:
    dp = [0]
    def numSquares(self, n):
        _dp = self.dp
        if len(_dp) >= n + 1:
            return _dp[n]
        else:
            for i in range(len(_dp), n+1):
                _dp += [min([_dp[i-j*j]+1 for j in range(1, int(math.sqrt(i))+1) if i-j*j >= 0])]
        return _dp[n]

print(Solution().numSquares(12))

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".


Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

The input string length won't exceed 1000.

class Solution:
    def countSubstrings(self, s):
        dp = [[0] * len(s) for i in range(len(s))]
        res = 0
        for r in range(len(s)):
            for l in range(r+1):
                if s[r] == s[l]:
                    if r == l or r+1 == l or dp[l+1][r-1] == 1:
                        dp[l][r] = 1
                        res += 1
        return res
print(Solution().countSubstrings("aba"))

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[0] * len(s) for i in range(len(s))]
        res = ""
        for r in range(len(s)):
            for l in range(r + 1):
                if s[l] == s[r]:
                    if l == r or l + 1 == r or dp[l + 1][r - 1] == 1:
                        dp[l][r] = 1
                        if r - l + 1 > len(res):
                            res = s[l:r + 1]
        return res

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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

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

class Solution:
    def singleNumber(self, nums):
        table = {}
        for i in nums:
            table[i] = table.get(i, 0) + 1
        for k in table:
            if table[k] == 1:
                return k

class Solution:
    def singleNumber(self, nums):

        res = 0

        for i in nums:
            res ^= i

        return res

print(Solution().singleNumber([2, 2, 5, 1, 8, 1, 9, 8, 9]))

from functools import reduce
import operator
nums = [2, 2, 5, 1, 8, 1, 9, 8, 9]
print(reduce(lambda x, y: x ^ y, nums))
print(reduce(operator.xor, nums))

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

class Solution:
    def isHappy(self, n):
        table = {}

        while n != 1:
            x = n
            n = 0
            while x != 0:
                n += (x % 10)**2
                x //= 10

            if table.get(n):
                return False
            else:
                table[n] = 1
        return True


class Solution:
    def isHappy(self, n):
        mem = set()
        while n not in mem:
            mem.add(n)
            n = sum(int(i)**2 for i in str(n))
        return n == 1

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2
Output: [0,1,1]
Example 2:

Input: 5
Output: [0,1,1,2,1,2]

dp[0] = 0
dp[1] = dp[1-1] + 1 = 1
dp[2] = dp[2-2] + 1 = 1
dp[3] = dp[3-2] + 1 = 2
dp[4] = dp[4-4] + 1 = 1
dp[5] = dp[5-4] + 1 = 2
dp[6] = dp[6-4] + 1 = 2
dp[7] = dp[7-4] + 1 = 3
dp[8] = dp[8-8] + 1 = 1
dp[9] = dp[9-8] + 1 = 2
dp[i] = dp[i - log_2 (i)] + 1

A trick using bit manipulation:

8 -> 1000
9 -> 1001
10 -> 1010

9 & 8 -> 1001 & 1000 -> 1000 dp[8] + 1  = 2
10 & 9 -> 1010 & 1001 -> 1000 dp[8] + 1 = 2
11 & 10 -> 1011 & 1010 -> 1010 dp[10] + 1 = 3
12 & 11 -> 1100 & 1011 -> 1000 dp[8] + 1 = 2

dp[i] = dp[i & (i-1)] + 1

class Solution:
    def countBits(self, num):
        offset = 1
        dp = [0] * (num + 1)
        for i in range(1, num + 1):
            if offset * 2 == i:
                offset *= 2
            dp[i] = dp[i - offset] + 1
        return dp

class Solution:
    def countBits(self, num):
        dp = [0] * (num + 1)
        for i in range(1, num + 1):
            dp[i] = dp[i & (i - 1)] + 1
        return dp

class Solution(object):
    def countBits(self, num):
        res=[0]
        while len(res)<=num:
            res+=[i+1 for i in res]
        return res[:num+1]

class Solution:
    def countBits(self, num):
        dp = [0] * (num + 1)
        for i in range(1, num+1):
            if not i % 2:
                dp[i] = dp[i >> 1]
            else:
                dp[i] = dp[i >> 1] + 1

        return dp[num]

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

for j in range(2sum+1):
    if dp[i-1][j] > 0: # only check the ones, which have been reached
      if j+nums[i] < 2sum + 1: # sign + to the current number, we transit from j to j+nums[i]
        dp[i][j+nums[i]] += dp[i-1][j]
      if j-nums[i] >= 0: # sign + to the current number, we transit from j to j-nums[i]
        dp[i][j-nums[i]] += dp[i-1][j]

# the first number with symbols
dp[0][offset+nums[0]] +=1
dp[0][offset-nums[0]] +=1

d[0][0+sum + 1] += 1 -> dp[0][6] = 1
d[0][0+sum - 1] += 1 -> dp[0][4] = 1

d[0][0+sum + 1] += 1 -> dp[0][5] = 1
d[0][0+sum - 1] += 1 -> dp[0][5] = 2

class Solution():
    def findTargetSumWays(self, nums, S):
        l = len(nums)
        n = 2 * sum(nums) + 1
        offset = sum(nums)

        dp = [[0] * n for i in nums]

        if not nums:
            return 0

        # base case
        dp[0][offset - nums[0]] += 1
        dp[0][offset + nums[0]] += 1

        for i in range(1, len(nums)):
            for j in range(n):
                if dp[i-1][j] > 0:
                    if j + nums[i] < n:
                        dp[i][j + nums[i]] += dp[i-1][j]
                    if j - nums[i] >= 0:
                        dp[i][j - nums[i]] += dp[i-1][j]

        return dp[-1][offset + S]


print(Solution().findTargetSumWays([1, 1, 1, 1, 1], 3))

class Solution:
    def findTargetSumWays(self, nums, S):
        if not nums:
            return 0
        l = len(nums)
        n = 2 * sum(nums) + 1
        offset = sum(nums)
        dp = [[0] * n for i in nums]

        dp[0][offset + nums[0]] += 1
        dp[0][offset - nums[0]] += 1

        for i in range(1, l):
            for j in range(n):
                if dp[i - 1][j] > 0:
                    if dp[i - 1][j] < n:
                        dp[i][j + nums[i]] += dp[i - 1][j]
                    if dp[i - 1][j] >= 0:
                        dp[i][j - nums[i]] += dp[i - 1][j]

        return dp[-1][offset + S]

print(Solution().findTargetSumWays([1, 1, 1, 1, 1], 3))

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

class Solution:
    def moveZeros(self, nums):

        p1, p2 = 0, 0

        for p2 < len(nums):
            if nums[p1] != 0:
                p1 += 1
            elif nums[p2] != 0:
                nums[p1], nums[p2] = nums[p2], nums[p1]
                p1 += 1
            p2 += 1

        return nums

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.


Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].


Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

class Solution:
    def canPartition(slef, nums):
        nums_sum = sum(nums)
        if nums_sum % 2 != 0:
            return False

        target = nums_sum//2
        n = target + 1

        dp = [False] * n
        dp[0] = True
        for i in range(len(nums)):
            for j in reversed(range(nums[i], n)):
                dp[j] = dp[j-nums[i]] or dp[j]
                if dp[target]:
                    return True
        return dp[target]

class Solution:
    def canPartition(self, nums):
        s = sum(nums)
        if s%2 != 0:
            return False

        bits = 1
        for i in nums:
            bits |= bits << i

        return (bits >> (s//2)) & 1 == 1

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.



Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.


Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

215. Kth Largest Element in an Array
Medium

3152

222

Add to List

Share
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

class Solution:
    def findKthLargest(self, nums, k):
        l = []

        for i in nums:
            if not l:
                l.append(i)
            else:
                len0 = len(l)
                for j in range(len(l)):
                    if i >= l[j]:
                        l = l[0:j] + [i] + l[j:]
                        break
                if len0 == len(l) and len0 != k:
                    l.append(i)
                l = l[0:k]
        return l[-1]

class Solution:
    def findKthLargest(self, nums, k):
        pos = self.partition(nums, 0, len(nums) - 1)
        if pos + 1 < k:
            return self.findKthLargest(nums[pos + 1:], k - pos - 1)
        elif pos + 1 > k:
            return self.findKthLargest(nums[0:pos], k)
        else:
            return nums[pos]

    def partition(self, nums, l, r):
        p = r

        while(l < r):
            while l < r and nums[l] > nums[p]:
                l += 1
            while l < r and nums[r] <= nums[p]:
                r -= 1
            nums[l], nums[r] = nums[r], nums[l]
        nums[l], nums[p] = nums[p], nums[l]
        return l

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Note:

All inputs will be in lowercase.
The order of your output does not matter.

import collections
class Solution:
    def groupAnagrams(self, strs):
        ans = collections.defaultdict(list)
        for s in strs:
            ans[tuple(sorted(s))].append(s)
        return list(ans.values())

import collections
class Solution:
    def groupAnagrams(self, strs):
        ans = collections.defaultdict(list)
        for s in strs:
            a = [0] * 26
            for c in s:
                a[ord(c) - ord('a')] += 1
            ans[tuple(a)].append(s)
        return list(ans.values())

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.



Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        p1 = p2 = head
        while p2 and p2.next:
            p2 = p2.next.next
            p1 = p1.next

        return p1

class Solution:
    def middleNode(self, head):
        mid = head
        count = 0
        while head:
            count += 1
            if count % 2 == 0:
                mid = mid.next
            head = head.next
        return mid

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
Note:

1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

class Solution:
    def backspaceCompare(self, S, T):
        return self.build(S) == self.build(T)

    def build(self, s):
        res = []

        for c in s:
            if c != "#":
                res.append(c)
            elif res:
                res.pop()

        return "".join(res)

print(Solution().backspaceCompare("ac#cc#", "ab#c"))

from functools import reduce

class Solution:
    def backspaceCompare(self, S, T):
        def back(res, c):
            if c != "#":
                res.append(c)
            elif res:
                res.pop()
            return res

        return reduce(back, S, []) == reduce(back, T, [])

print(Solution().backspaceCompare("ac#cc#", "ab#c"))

class Solution:
    def backspaceCompare(self, S, T):
        pS, pT = len(S) - 1, len(T) - 1
        backS, backT = 0, 0

        while pS >= 0 or pT >= 0:
            while pS >= 0:
                if S[pS] == "#":
                    backS += 1
                    pS -= 1
                elif backS:
                    backS -= 1
                    pS -= 1
                else:
                    break

            while pT >= 0:
                if T[pT] == "#":
                    backT += 1
                    pT -= 1
                elif backT:
                    backT -= 1
                    pT -= 1
                else:
                    break

            if not (pS >= 0 and pT >= 0 and S[pS] == T[pT]):
                return pS == pT == -1

            pS -= 1
            pT -= 1

        return True
print(Solution().backspaceCompare("###ac#b", "ab#b"))

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.


Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.getMin() or self.getMin() >= x:
            self.min.append(x)

    def pop(self) -> None:
        if self.stack:
            x = self.stack.pop()
            if x == self.min[-1]:
                self.min.pop()

    def top(self) -> int:
        if self.stack:
            return self.stack[-1]
        else:
            return None

    def getMin(self) -> int:
        if self.min:
            return self.min[-1]
        else:
            return None

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree
          1
         / \
        2   3
       / \
      4   5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        elif not root.right and not root.left:
            return 0
        elif not root.right:
            return max(self.diameterOfBinaryTree(root.left),
                       1 + self.height(root.left))
        elif not root.left:
            return max(self.diameterOfBinaryTree(root.right),
                       1 + self.height(root.right))
        else:
            return max(self.diameterOfBinaryTree(root.right),
                       self.diameterOfBinaryTree(root.left),
                       self.height(root.left) + self.height(root.right) + 2)

    def height(self, root):

        if not root:
            return 0
        if not root.right and not root.left:
            return 0

        return 1 + max(self.height(root.left), self.height(root.right))

class Solution:
    def diameterOfBinaryTree(self, root):
        self.ans = 0

        def depth(node):
            if not node:
                return 0
            r = depth(node.right)
            l = depth(node.left)
            self.ans = max(self.ans, r+l)
            return 1 + max(r, l)
        depth(root)
        return self.ans

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)



Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

class Solution:
    def lastStoneWeight(self, stones):
        res = [ -s for s in stones ]

        heapq.heapify(res)

        while len(res) > 1 :
            y = heapq.heappop(res)
            x = heapq.heappop(res)
            if y != x:
                heapq.heappush(res, y-x)

        return res[0]*-1 if res else 0

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

Index 0: h[-1] = 0, maxlen = 0
Index 1: h[0] = -1, maxlen = 1 - (-1) = 2
maxlen = 2

class Solution:
    def findMaxLength(self, nums):
        h = {0: -1}

        count = ans = 0
        for i in range(len(nums)):
            count += 1 if nums[0] else -1
            ans = max(ans, h.setdefault(count, i))

        return ans

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:

direction can be 0 (for left shift) or 1 (for right shift).
amount is the amount by which string s is to be shifted.
A left shift by 1 means remove the first character of s and append it to the end.
Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.
Return the final string after all operations.

Example 1:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation:
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:

Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        count = sum([ (-1+2*x)*y for x, y in shift ]) % len(s)
        ds = s + s
        return ds[len(s)-count: 2*len(s) - count]

238. Product of Array Except Self
Medium

4145

358

Add to List

Share
Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        ans = [0] * n
        ans[0] = 1

        for i in range(1, n):
            ans[i] = ans[i-1] * nums[i-1]

        R = 1
        for i in reversed(range(n)):
            ans[i] = ans[i] * R
            R *= nums[i]

        return ans

print(Solution().productExceptSelf([1, 2, 3, 4]))

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note:
The string size will be in the range [1, 100].

class Solution:
    def checkValidString(self, s: str) -> bool:
        counter_max = 0
        counter_min = 0

        for c in s:
            if c == "(":
                counter_max += 1
                counter_min += 1
            elif c == ")":
                counter_max -= 1
                counter_min = max(counter_min-1, 0)
            else:
                counter_max += 1
                counter_min = max(counter_min-1, 0)

            if counter_max < 0:
                return False

        return counter_min == 0

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1
Example 2:

Input:
11000
11000
00100
00011

Output: 3

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        h = len(grid)
        w = len(grid[0])
        ans = 0
        m = [ [0] * w for x in range(h) ]
        for i in range(h):
            for j in range(w):
                if grid[i][j] == "1" and m[i][j] == 0:
                    self.dfs(grid, i, j, m)
                    ans += 1
        return ans

    def dfs(self, grid, i, j, m):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0" or m[i][j] == 1:
            return None
        else:
            m[i][j] = 1
            self.dfs(grid, i, j+1, m)
            self.dfs(grid, i, j-1, m)
            self.dfs(grid, i-1, j, m)
            self.dfs(grid, i+1, j, m)
        return None

Given a collection of distinct integers, return all possible permutations.

Example:

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

class Solution:
    def permute(self, nums):
        ans = []
        self.backtrack([], nums, ans)
        return ans

    def backtrack(self, path, nums, ans):
        if not nums:
            ans.append(path[:])
            return
        for i, v in enumerate(nums):
            self.backtrack(path+[v], nums[:i]+nums[i+1:], ans)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        marked = [False] * len(nums)
        self.dfs(nums, [], marked, ans)
        return ans

    def dfs(self, nums, path, marked, ans):
        if len(path) == len(nums):
            ans.append(list(path))
            return

        for i, n in enumerate(nums):
            if marked[i]:
                continue
            marked[i] = True
            path.append(n)
            self.dfs(nums, path, marked, ans)
            path.pop()
            marked[i] = False

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

ans = []

def backtrack(path, pool):

  if meet condition:
    ans.add(path)
    return

  for selection in pool:

    path.add(selection)
    backtrack(path, new_pool)
    path.remove(selection)

class Solution:
    def permuteUnique(self, nums):
        ans = []
        self.backtrack([], nums, ans)
        return ans

    def backtrack(self, path, pool, ans):
        if not pool:
            ans.append(path[:])
            return

        t = {}

        for i, v in enumerate(pool):
            if v not in t:
                t[v] = 1
                self.backtrack(path+[v], pool[:i]+pool[i+1:], ans)

print(Solution().permuteUnique([1,1,2]))

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

class Solution:
    def bstFromPreorder(self, preorder):
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        self.buildTree(root, 1, preorder, sys.maxsize)
        return root

    def buildTree(self, root, pos, preorder, rmax):
        if pos >= len(preorder) or preorder[pos] > rmax:
            return None

        if preorder[pos] < root.val:
            root.left = TreeNode(preorder[pos])
            pos = self.buildTree(root.left, pos+1, preorder, root.val - 1)

        if pos < len(preorder) and preorder[pos] <= rmax:
            root.right = TreeNode(preorder[pos])
            pos = self.buildTree(root.right, pos+1, preorder, rmax)

        return pos

class Solution:
    pos = 0
    def bstFromPreorder(self, preorder, bound=float('inf')):
        if self.pos >= len(preorder) or preorder[self.pos] > bound:
            return None
        root = TreeNode(preorder[self.pos])
        self.pos += 1
        root.left = self.bstFromPreorder(preorder, root.val)
        root.right = self.bstFromPreorder(preorder, bound)
        return root

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

class Solution:
    def buildTree(self, preorder, inorder):
        if inorder:
            node = TreeNode(preorder.pop(0))
            split = inorder.index(node.val)
            node.left = self.buildTree(preorder, inorder[:split])
            ndoe.right = self.buildTree(preorder, inorder[split+1:])
            return node

class Solution(object):
    def __init__(self):
        self.map = {}

    def buildTree(self, preorder, inorder):
        for i, val in enumerate(inorder):
            self.map[val] = i

        return self.recursive(0, len(preorder) - 1, preorder, inorder)

    def recursive(self, start, end, preorder, inorder):
        if (start > end):
            return None

        node = TreeNode(preorder.pop(0))

        split = self.map[node.val]

        node.left = self.recursive(start, split - 1, preorder, inorder)
        node.right = self.recursive(split + 1, end, preorder, inorder)

        return node

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn't exist, return -1.

You can't access the Binary Matrix directly.  You may only access the matrix using a BinaryMatrix interface:

BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n.
Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you're given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0

Example 4:
Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
#class BinaryMatrix(object):
#    def get(self, x: int, y: int) -> int:
#    def dimensions(self) -> list[]:
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix):
        n, m = binaryMatrix.dimensions()
        ans = m
        for i in range(n):
            x = self.findOne(binaryMatrix, i, 0, m - 1)
            if x != -1:
                ans = min(ans, x)
        return ans if ans != m else -1

    def findOne(self, m, r, i, j):
        if i == j:
            return i if m.get(r, i) == 1 else -1

        mid = (i + j) // 2
        if m.get(r, mid) == 1:
            if mid == 0 or m.get(r, mid - 1) == 0:
                return mid
            else:
                return self.findOne(m, r, i, mid - 1)
        else:
            return self.findOne(m, r, mid+1, j)

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

class Solution:
    def subArraySum(self, nums, k):
        h = {0: 1}
        s = 0
        ans = 0
        for i in nums:
            s += i
            ans += h.get(s-k, 0)
            h[s] = h.get(s, 0) + 1

        return ans

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4
Example 2:

Input: [0,1]
Output: 0

class Solution:
    def rangeBitwiseAnd(self, m, n):
        i = 0
        while m != n:
            m >>= 1
            n >>= 1
            i += 1
        return n << i

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

class LRUCache:

    def __init__(self, capacity: int):
        self.count = 0
        self.capacity = capacity
        self.hash = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.hash:
            node = self.hash[key]
            self._remove(node)
            self._add(node)
            return node.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key not in self.hash:
            node = Node(key, value)
            self.hash[key] = node
            self.count += 1
            self._add(node)
        else:
            node = self.hash[key]
            node.value = value
            self.get(key)

        if self.count > self.capacity:
            n = self.tail.prev
            self.hash.pop(n.key)
            self._remove(n)
            self.count -= 1

    def _connect(self, p, n):
        p.next, n.prev = n, p

    def _add(self, n):
        tmp = self.head.next
        self._connect(self.head, n)
        self._connect(n, tmp)

    def _remove(self, node):
        self._connect(node.prev, node.next)



class Node:
    def __init__(self, key, value):
        self.key = key
        self.value =  value
        self.prev = None
        self.next = None


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.



Follow up:
Could you do both operations in O(1) time complexity?



Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

class Node:
    def __init__(self, key, value):
        self.freq = 1
        self.key = key
        self.value = value
        self.next = None
        self.prev = None


class DoubleLinkedList:
    def __init__(self):
        self._head = Node(0, 0)
        self._tail = Node(0, 0)
        self._head.next = self._tail
        self._tail.prev = self._head
        self._size = 0

    def append(self, node):
        self._connect(node, self._head.next)
        self._connect(self._head, node)
        self._size += 1

    def pop(self, node):
        self._connect(node.prev, node.next)
        node.next = None
        node.prev = None
        self._size -= 1
        return node

    def pop_last(self):
        return self.pop(self._tail.prev)

    def get_size(self):
        return self._size

    def _connect(self, p, n):
        p.next, n.prev = n, p


class LFUCache:
    def __init__(self, capacity):
        self.nodes = {}
        self.freq = {}
        self.min_freq = 1
        self.capacity = capacity

    def get(self, key):
        if key in self.nodes:
            node = self.nodes[key]
            l = self.freq[node.freq]
            l.pop(node)
            if l.get_size() == 0 and self.min_freq == node.freq:
                self.min_freq += 1

            node.freq += 1
            if self.freq.get(node.freq):
                self.freq[node.freq].append(node)
            else:
                l = DoubleLinkedList()
                l.append(node)
                self.freq[node.freq] = l
            return node.value
        else:
            return -1

    def put(self, key, value):

        if self.capacity == 0:
            return

        if key in self.nodes:
            self.nodes[key].value = value
            self.get(key)
        else:
            node = Node(key, value)
            if len(self.nodes) == self.capacity:
                l = self.freq[self.min_freq]
                n = l.pop_last()
                self.nodes.pop(n.key)

            self.nodes[key] = node

            if 1 in self.freq:
                self.freq[1].append(node)
            else:
                l = DoubleLinkedList()
                l.append(node)
                self.freq[1] = l
            self.min_freq = 1


c = LFUCache(3)
c.put(1, 1)
c.put(2, 2)
print(c.get(1))
print(c.get(2))
print(c.get(1))
c.put(3, 3)
print(c.get(2))
print(c.get(3))
c.put(4, 4)

print(c.get(4))

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

class Solution:
    def pathSum(self, root, sum):
        if not root:
            return 0

        return self.pathSum(root.left, sum) + self.pathSum(
            root.right, sum) + self.pathSumFrom(root, sum)

    def pathSumFrom(self, root, sum):

        if not root:
            return 0

        if root.val == sum:
            return 1 + self.pathSumFrom(root.left, 0) + self.pathSumFrom(
                root.right, 0)
        else:
            return self.pathSumFrom(root.left,
                                    sum - root.val) + self.pathSumFrom(
                                        root.right, sum - root.val)

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters.
(eg, "ace" is a subsequence of "abcde" while "aec" is not).
A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0] * (len(text1) + 1) for i in range(len(text2) + 1)]

        for i in range(len(text2)):
            for j in range(len(text1)):
                if text2[i] == text1[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

        return dp[-1][-1]

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2

Output: 2

Explanation:
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6

Output: 3

Example 3:

Input: K = 3, N = 14

Output: 4

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()

        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            if (K, N) in memo:
                return memo[(K, N)]

            res = float('INF')

            for i in range(1, N+1):
                res = min(res, max(dp(K-1, i-1), dp(K, N - i)) + 1)

            memo[(K, N)] = res
            return res

        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()

        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            if (K, N) in memo:
                return memo[(K, N)]

            res = float('INF')
            lo = 1
            hi = N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K - 1, mid - 1)
                not_broken = dp(K, N - mid)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)

            memo[(K, N)] = res
            return res

        return dp(K, N)
print(Solution().superEggDrop(3, 14))

class Solution:
    def superEggDrop(self, K, N):
      dp = [[0]*(K+1) for _ in range(N+1)]
      m = 0
      while dp[m][K] < N:
          m += 1
          for i in range(1, K+1):
              dp[m][i] = dp[m-1][i] + dp[m-1][i-1] + 1
      return m

print(Solution().superEggDrop(2, 6))
print(Solution().superEggDrop(3, 14))

class Solution:
    def superEggDrop(self, K, N):
      m = 0
      dp = [0] * (K+1)
      while dp[K] < N:
          m += 1
          prev = 0
          for i in range(1, K+1):
              tmp = dp[i]
              dp[i] = dp[i] + prev + 1
              prev = tmp
      return m

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

class Solution:
    def __init__(self, pat):
        self.pat = pat
        self.dp = []
        self.KMP(self.pat)

    def KMP(self, pat):

        M = len(pat)
        self.dp = [[0] * 256 for _ in range(M)]
        self.dp[0][ord(pat[0])] = 1
        X = 0

        for j in range(1, M):
            for c in range(256):
                if ord(pat[j]) == c:
                    self.dp[j][c] = j + 1
                else:
                    self.dp[j][c] = self.dp[X][c]

            X = self.dp[X][ord(pat[j])]

    def search(self, txt):
        M = len(self.pat)
        N = len(txt)
        s = 0

        for i in range(N):
            s = self.dp[s][ord(txt[i])]
            if s == M:
                return i - M + 1
        return -1

sol = Solution("ababc")

print(sol.search("ababdabababc"))

from collections import Counter
class Solution:
    def majorityElement(self, nums):
        c = Counter()
        l = len(nums)
        for n in nums:
            c[n] += 1
            if c[n] > l/2:
                return n

print(Solution().majorityElement([1, 1, 2, 2, 2, 2, 4]))

class Solution:
    def majorityElement(self, nums):
        counter = 1
        ans = nums[0]

        for n in nums[1:]:
            if n == ans:
                counter += 1
            else:
                counter -= 1
                if counter < 0:
                    counter = 1
                    ans = n
        return ans
print(Solution().majorityElement([1, 1, 2, 2, 2, 2, 4]))

class Solution:
    def findDisappearedNumbers(self, nums):
        for i in nums:
            j = i
            while nums[j-1] != j:
                nums[j-1], j = j, nums[j-1]

        return [i+1 for i in range(len(nums)) if nums[i] != i+1]

from collections import defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    h = defaultdict(int)

    def maxPathSum(self, root: TreeNode) -> int:
        if not root:
            return -sys.maxsize

        return max(self.maxPathSumFrom(root), self.maxPathSum(root.left),
                   self.maxPathSum(root.right))

    def maxPathSumFrom(self, root):

        if not root:
            return 0

        return max(
            root.val, root.val + self.maxPathSumDfs(root.right),
            root.val + self.maxPathSumDfs(root.left), root.val +
            self.maxPathSumDfs(root.right) + self.maxPathSumDfs(root.left))

    def maxPathSumDfs(self, root):
        if not root:
            return 0

        if root in self.h:
            return self.h[root]
        else:
            rightSum = self.h.get(root.right, self.maxPathSumDfs(root.right))
            leftSum = self.h.get(root.left, self.maxPathSumDfs(root.left))
            ans = max(root.val, root.val + rightSum, root.val + leftSum)
            self.h[root] = ans

        return ans

class Solution:
    ans = -sys.maxsize

    def maxPathSum(self, root):
        self.dfs(root)
        return self.ans

    def dfs(self, root):
        if not root:
            return 0

        left = max(self.dfs(root.left), 0)
        right = max(self.dfs(root.right), 0)

        self.ans = max(self.ans, root.val + left + right)
        return root.val + max(left, right)

class Solution:
    ans = -sys.maxsize

    def maxPathSum(self, root):
        self.dfs(root)
        return self.ans

    def dfs(self, root):
        if not root:
            return 0

        left = self.dfs(root.left)
        right = self.dfs(root.right)

        val = max(root.val, root.val + left, root.val + right)
        self.ans = max(self.ans, val, root.val + left + right)

        return val

You are a product manager and currently leading a team to develop a new product.
Unfortunately, the latest version of your product fails the quality check.
Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad.
Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

class Solution:
    def firstBadVerion(self, n):
        l, r, mid = 1, n, (1+n) // 2

        while l != mid:
            if isBadVersion(mid):
                l = mid
            else:
                r = mid
            mid = (l + r) // 2

        return l if isBadVersion(l) else r

class Solution:
    def firstBadVersion(self, n):
        if n == 1:
            return 1

        l, r = 2, n

        while l <= r:
            mid = (l + r) // 2
            if isBadVersion(mid) and not isBadVersion(mid - 1):
                return mid
            elif isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1
        return 1

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if inorder:
            node = TreeNode(postorder.pop())
            split = inorder.index(node.val)
            node.right = self.buildTree(inorder[split + 1:], postorder)
            node.left = self.buildTree(inorder[:split], postorder)

            return node

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

Your algorithm should run in O(n) complexity.

Example:

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):
        h = dict()
        ans = 0

        for num in nums:
            if num not in h:
                if num - 1 in h and num + 1 in h:
                    h[h[num + 1][1]][0] = h[num - 1][0]
                    h[h[num - 1][0]][1] = h[num + 1][1]
                    h[num] = [h[num - 1][0], h[num + 1][1]]
                elif num - 1 in h:
                    h[h[num - 1][0]][1] += 1
                    h[num] = h[h[num - 1][0]]
                elif num + 1 in h:
                    h[h[num + 1][1]][0] -= 1
                    h[num] = h[h[num + 1][1]]
                else:
                    h[num] = [num, num]
                ans = max(ans, h[num][1] - h[num][0] + 1)

        return ans

class Solution:
    def longestConsecutive(self, nums):
        ans = 0
        nums = set(nums)
        for x in nums:
            if x - 1 not in nums:
                y = x + 1
                while y in nums:
                    y += 1
                ans = max(ans, y - x)
        return ans

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

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

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

class Solution:
    def isValidBST(self, root):
        return self.isValidBSTBound(root, -sys.maxsize, sys.maxisze)

    def isValidBSTBound(self, root, lb, hb):
        if not root:
            return True

        if lb < root.val < hb:
            return self.isValidBSTBound(root.left, lb, root.val) and self.isValidBSTBound(root.right, root.val, hb)
        else:
            return False

Every non-negative integer N has a binary representation.  For example, 5 can be represented as "101" in binary, 11 as "1011" in binary, and so on.  Note that except for N = 0, there are no leading zeroes in any binary representation.

The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1.  For example, the complement of "101" in binary is "010" in binary.

For a given number N in base-10, return the complement of it's binary representation as a base-10 integer.

Example 1:

Input: 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

class Solution:
    def bitwiseComplement(self, num: int) -> int:
        if num == 0:
            return 1

        c = 1
        n = num
        while n:
            c *= 2
            n >>= 1

        return num ^ (c - 1)

1 = 1
1*2 + 1 = 3 = 11
3*2 + 1 = 7 = 111
7*2 + 1 = 15 = 1111

class Solution:
    def bitwiseComplement(self, num):
        x = 1
        while x < num: x = 2 * x + 1
        return x - num

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

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

     3
    / \
   2   3
    \   \
     3   1

Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

class Solution:
    memo = {}
    def rob(self, root):
        return self.robRec(root, False)

    def robRec(self, root, isRobbed):
        if not root:
            return 0

        if (root, isRobbed) in memo:
            return memo[(root, isRobbed)]

        if isRobbed:
            ans = self.robRec(root.left, False) + self.robRec(root.right, False)
        else:
            ans = max(root.val + self.robRec(root.left, True) + self.robRec(root.right, True),
                      self.robRec(root.left, False) + self.robRec(root.right, False))

        memo[(root, isRobbed)] = ans

        return ans

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

The number of nodes in the tree will be between 2 and 100.
Each node has a unique integer value from 1 to 100.

class Solution:
    m = {}

    def isCousins(self, root, x, y):
        if not root:
            return False

        if self.depth(root, x) == self.depth(root, y):
            return self.m[x] != self.m[y]

        return False

    def depth(self, root, val):
        if not root:
            return -1

        if root.val == val:
            return 0
        else:

            left = self.depth(root.left, val)
            right = self.depth(root.right, val)

            if left >= 0:
                self.m[root.left.val] = root.val
                return 1 + left
            elif right >= 0:
                self.m[root.right.val] = root.val
                return 1 + right

        return -1

You are given an array coordinates, coordinates[i] = [x, y],
where [x, y] represents the coordinate of a point.

Check if these points make a straight line in the XY plane.

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        p1 = coordinates[0]
        p2 = coordinates[1]
        slope = self.slope(p1, p2)

        for i in range(2, len(coordinates)):
            if self.slope(coordinates[0], coordinates[i]) != slope:
                return False

        return True

    def slope(self, p1, p2):
        if p1[1] == p2[1]:
            return sys.maxsize

        return (p1[0] - p2[0]) / (p1[1] - p2[1])

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:
Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.
Note:

The length of image and image[0] will be in the range [1, 50].
The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

class Solution:
    def floodFill(self, image, sr: int, sc: int, newColor: int):
        oldColor = image[sr][sc]
        stack = []
        if newColor != oldColor:
            stack.append([sr, sc])

        m = len(image)
        n = len(image[0])

        while stack:
            p = stack.pop()
            x, y = p

            image[x][y] = newColor

            for v in [[1, 0], [0, 1]]:
                for s in [1, -1]:
                    r = v[0] * s
                    c = v[1] * s
                    if 0 <= x + r < m and 0 <= y + c < n and image[x + r][y + c] == oldColor:
                        stack.append([x + r, y + c])

        return image