[LeetCode] 279. Perfect Squares

 Problem : https://leetcode.com/problems/perfect-squares/

I know there is a much better solution. But this memorization approach is easy to understand for me.

class Solution {
    HashMap<Integer, Integer> memo = new HashMap();
    
    {
        memo.put(0, 0);
    }
    
    public int numSquares(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        int result = Integer.MAX_VALUE;
        
        for (int x = 1; x * x <= n; x++) {   
            result = Math.min(result, 1 + numSquares(n - x*x));
        } 
        
        memo.put(n, result);
        return result;
    }
}

A buttom-up solution:

class Solution:
    def numSquares(self, n: int) -> int:
        INT_MAX = 2**31 - 1
        
        dp = [INT_MAX] * (n+1)
        dp[0] = 0
        
        i = 1
        while i * i < n:
            dp[i*i] = 1
            i += 1
        
        for i in range(1, n+1):
            if dp[i] != INT_MAX: continue
                
            for j in range(1, int(math.sqrt(i)) + 1):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        return dp[n]

Edited on 12/02/2021. Update the top-down solution.

[LeetCode] 278. First Bad Version

Problem : https://leetcode.com/problems/first-bad-version/

Time complexity = O ( Log N )

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        left, right = 0, n
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if not isBadVersion(mid):
                left = mid + 1
            else:
                right = mid - 1

        return left

[LeetCode] 275. H-Index II

 Problem : https://leetcode.com/problems/h-index-ii/

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        N = len(citations)
        left, right = 0, N - 1
        
        while left <= right:
            mid = left + (right - left) // 2    
            h = N - mid
                        
            if citations[mid] == h:
                return h
            
            if citations[mid] < h:
                left = mid + 1
            else:
                right = mid - 1
        
        return N - left

[LeetCode] 274. H-Index

Problem : https://leetcode.com/problems/h-index/

Sort citations in ascending order.

Iterate from the first item. If value of current item > = number of remaining items (includes current item). Return the number of remaining items as H-index.

class Solution:
    def hIndex(self, citations: List[int]) -> int:   
        citations.sort()
        N = len(citations)
        
        for i in range(N):
            # N - i = number of remaining paper
            if citations[i] >=  N - i:
                return N - i
        
        return 0

[LeetCode] 273. Integer to English Words

Problem : https://leetcode.com/problems/integer-to-english-words/

Split the number into hundreds, then convert hundred into words.

class Solution:
    def numberToWords(self, num: int) -> str:
        ones = ['One', 'Two', 'Three', 'Four', \
                'Five', 'Six', 'Seven', 'Eight', \
                'Nine']
        
        odds = ['Eleven', 'Twelve',\
                    'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen',\
                    'Seventeen', 'Eighteen', 'Nineteen']
        
        tens = ['Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', \
                'Sixty', 'Seventy', 'Eighty', 'Ninety']
        
        
        def hundreds(n, output):           
            if n >= 100:
                output.append(ones[(n//100) - 1])
                output.append("Hundred")
                hundreds(n%100, output)
            elif n == 10 or n >= 20:
                output.append(tens[n // 10 -1])    
                hundreds(n%10, output)          
            elif 10 < n < 20:
                output.append(odds[n - 11])
            elif n > 0:
                output.append(ones[n-1])
        
        if num == 0:
            return "Zero"
        
        output = []
        
        while num > 0:
            if num < 1000:
                hundreds(num, output)
                break
            elif 1000 <= num < 1000 * 1000:
                hundreds(num // 1000, output)
                output.append('Thousand')
                num = num % 1000
            elif 1000 * 1000 <= num < 1000 * 1000 * 1000:
                hundreds(num // (1000 * 1000), output)
                output.append('Million')
                num = num % (1000 * 1000)
            else:
                hundreds(num // (1000 * 1000 * 1000), output)
                output.append('Billion')
                num = num % (1000 * 1000 * 1000)
        
        return ' '.join(output)    

[LeetCode] 268. Missing Number

Problem : https://leetcode.com/problems/missing-number/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        memo = set(nums)
        
        for n in nums:
            if n < len(nums) and n + 1 not in memo:
                return n + 1
        
        return 0

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
    
        for i, n in enumerate(nums):
            missing ^= i ^ n
            
        return missing

As it mentioned, the numbers are from 0 to n.

Now we use all of the valid indices [0, n] to XOR with all numbers. The result is the missing number.

[LeetCode] 264. Ugly Number II

Problem : https://leetcode.com/problems/ugly-number-ii/

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        result = [1] * n
        
        l1 = l2 = l3 = 0
        i = 0
        
        for i in range(n-1):
            n1 = result[l1] * 2
            n2 = result[l2] * 3
            n3 = result[l3] * 5
            
            tmp = min(n1, n2, n3)
            if n1 == tmp:
                l1 += 1
            if n2 == tmp:
                l2 += 1
            if n3 == tmp:
                l3 += 1
        
            result[i+1] = tmp
        
        return result[-1]

An ugly number must be multiplied by either 2, 3, 5 from a smaller ugly number.

The smallest ugly number is 1. So starts from 1 and multiple to 2, 3, 5, then find the smallest as the next ugly number

A naive implementation.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp2 = [2]
        dp3 = [3]
        dp5 = [5]
        
        i = j = k = 0

        x = 1
        
        for _ in range(1, n):
            mi = min(dp2[i], dp3[j], dp5[k])
                   
            if mi == dp2[i]:
                i += 1
                dp2.append(mi * 2)
                dp3.append(mi * 3)
                dp5.append(mi * 5)
            elif mi == dp3[j]:
                j += 1
                dp3.append(mi * 3)
                dp5.append(mi * 5)
            else:
                k += 1
                dp5.append(mi * 5)

            x = mi
            
        return x

Edited on 05/16/2021. Add the naive implementation.

[LeetCode] 263. Ugly Number

 Problem : https://leetcode.com/problems/ugly-number/

Time Complexity = O ( Log N )

class Solution:
    def isUgly(self, num: int) -> bool:
        
        if num <= 0:
            return False
        
        while num % 2 == 0:
            num = num // 2
        
        while num % 3 == 0:
            num = num // 3
        
        while num % 5 == 0:
            num = num // 5
            
        return num == 1

Use division to remove the prime factor 2, 3, 5 from the given number. Then check the remains of the number equals to 1

[LeetCode] 260. Single Number III

 Problem : https://leetcode.com/problems/single-number-iii/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        return [x[0] for x in filter(lambda x: x[1] == 1, Counter(nums).items())]

Sort first then count numbers solution:

Time complexity = O ( N * LogN )

Space complexity = O ( 1 )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        nums.sort()
        
        a = cntA = 0
        b = cntB = 0
        
        for n in nums:
            if cntA == 0:
                a = n
                cntA += 1
            elif a == n:
                cntA -= 1
            elif cntB == 0:
                b = n
                cntB += 1
            elif b == n:
                cntB -= 1
        
        
        return [a, b]

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution {
    public int[] singleNumber(int[] nums) {
        // Since all numbers except A and B appear twice
        // XOR = A ^ B
        int XOR = 0;
        for (int n : nums) {
            XOR ^= n;
        }
        
        // Find the first bit of the XOR from the right where bit == 1.
        // Because XR = A ^ B, this bit is either contribute by A or B.
        int offset = 0;
        while (offset < 32 && (XOR & (1 << offset)) == 0 ) {
            offset += 1;
        }
                
        // Use the bit of 'offset' as a flag to separate the original numbers to 2 groups
        // Group 1 : A, other numbers except B
        // Group 2 : B, other numbers except A
        // A = accumulated xor of numbers in group 1 
        // B = accumulated xor of number in group 2
        int A = 0, B = 0;
        for (int n : nums) {
            if ((n & (1 << offset)) != 0) {
                A ^= n;
            } else {
                B ^= n;
            }
        }
        
        return new int[] {A, B};
    }
}

Assume A and B are the 2 single numbers. Because all other numbers appear exactly twice. 

xor all numbers  =  A ^ B.

Then find the first bit of A ^ B = 1.   This bit is either from A or from B.

Use this bit to split the nums into 2 groups. Group 1 includes A and all other numbers except B. Group 2 includes B and all other numbers except A.

Since in each group there is only one single number,  result of xor all numbers in the group equals to the single number.

Edited on 11/07/2021. Update bit manipulation solution.

Edited on 05/31/2024. Update bit manipulation solution.

[LeetCode] 258. Add Digits

Problem : https://leetcode.com/problems/add-digits/

A naive solution:

class Solution:
    def addDigits(self, num: int) -> int:
        sums = 0
        
        while num > 0:
            sums += num % 10
            num = num // 10
        
        return sums if sums < 10 else self.addDigits(sums)

A mathematic solution:

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        
        return 9 if num % 9 == 0 else num % 9

Assume there is a 3 digits number   abc.

Then abc = a * 100 + b * 10 + c

Let sums =  a + b + c,  then  abc - sums = 99 * a + 9 * b

So, sums = abc - (99 * a  +  9 *b) 

Because  (99 * a + 9 * b)  is divisible by 9,     sums % 9 = abc % 9.

So we return  num % 9 as result.  If num % 9 = 0,  return 9.  As we only need to repeatedly add all digits until the result has only one digit.

[LeetCode] 257. Binary Tree Paths

Problem : https://leetcode.com/problems/binary-tree-paths/

DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        
        def dfs(node):
            if node:
                suffix = []
                
                if node.left:
                    suffix += dfs(node.left)
                    
                if node.right:
                    suffix += dfs(node.right)
                
                return [[str(node.val)] + s for s in suffix] if suffix else [[str(node.val)]]
                
        
        return ['->'.join(path) for path in dfs(root)]

Iterative DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        # dfs
        stack = [(root, [root.val])]
        result = []
        
        while stack:
            node, path = stack.pop()
            
            if not node.left and not node.right:
                result.append('->'.join(map(str, path)))
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
            
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
                
        return result

BFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        queue = deque([[root]]) if root else deque()
        result = []
        
        while queue:
            path = queue.popleft()
            
            if path[-1].left:
                queue.append(path + [path[-1].left])
            if path[-1].right:
                queue.append(path + [path[-1].right])
            
            if not path[-1].left and not path[-1].right:
                result.append(path)
        
        return map(lambda p: '->'.join(p), map(lambda path: map(lambda n: str(n.val), path), result))

Edited on 04/22/2021. Refactor DFS solution by appending suffix collected from lower level.

Edited on 06/06/2021. Add iterative DFS solution.

[LeetCode] 242. Valid Anagram

 Problem : https://leetcode.com/problems/valid-anagram/

Use hash table to count the characters in the string.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

[LeetCode] 241. Different Ways to Add Parentheses

Problem : https://leetcode.com/problems/different-ways-to-add-parentheses/

Use divide-and-conquer approach to split the expression into 2 sub-expression.

Continue split the expression until encounter the expression only contains 1 single number.

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        
        def getExpression():
            expression = []
            i = 0
            while i < len(input):
                if input[i].isalnum():
                    num = 0

                    while i < len(input) and input[i].isalnum():
                        num = num * 10 + int(input[i])
                        i += 1

                    expression.append(num)
                else:
                    expression.append(input[i])
                    i += 1
                    
            return expression
            
        
         
        def compute(a, opt, b):
            if opt == '+':
                return a + b
            
            if opt == '-':
                return a - b
            
            if opt == '*':
                return a * b
            
            return a // b
            
            
        def helper(expression, start, end):
            if end - start == 1:
                return [expression[start]]
            
            if end - start == 3:
                return [compute(expression[start], expression[start+1], expression[start+2])]
            
            result = []
            
            for i in range(start+1, end):
                opt = expression[i-1]
                
                if type(opt) != str:
                    continue
                    
                for a in helper(expression, start, i-1):
                    for b in helper(expression, i, end):
                        result.append(compute(a, opt, b))
                                
            return result
        
        expression = getExpression()
        return helper(expression, 0, len(expression))

[LeetCode] 240. Search a 2D Matrix II

Problem : https://leetcode.com/problems/search-a-2d-matrix-ii/

Because each row and column is sorted in ascending order.   One number is always larger than the number on its left and smaller than the number underneath. We can iterate from the top-right number. If the number is larger than the target, move the point to left side. If the number is smaller than the target value, move the point to down side.

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        ROW = len(matrix)
        if ROW == 0:
            return False
    
        COL = len(matrix[0])
        if COL == 0:
            return False
        
        if target < matrix[0][0]  or matrix[-1][-1] < target:
            return False
        
        y = 0 
        x = COL - 1
        
        while x >= 0 and y < ROW:
            if matrix[y][x] > target:
                # move pointer to left side
                x -= 1
            elif matrix[y][x] < target:
                # move pointer to down side
                y += 1
            else:
                return True
        
        return False

[LeetCode] 239. Sliding Window Maximum

Problem : https://leetcode.com/problems/sliding-window-maximum/

Maintain a decreasing monotonic queue. The first item of the queue is the maximum value in the range of k numbers.

Time complexity = O ( N )

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = deque()
        result = []
        
        for i in range(k):
            while queue and queue[-1][1] < nums[i]:
                queue.pop()
            
            queue.append((i, nums[i]))
        
        result.append(queue[0][1])
        
        for i in range(k, len(nums)):
            if i - queue[0][0] == k:
                queue.popleft()
            
            while queue and queue[-1][1] < nums[i]:
                queue.pop()
            
            queue.append((i, nums[i]))
            
            result.append(queue[0][1])
        
        return result

Edited on 10/09/2021. Update for the monotonic queue solution.

[LeetCode] 238. Product of Array Except Self

Problem : https://leetcode.com/problems/product-of-array-except-self/

Product of Array can be calculated with the table like:

    
    0   1   2   3
  +---+---+---+---+
0 |   | * | * | * | 
  +---+---+---+---+
1 | * |   | * | * |
  +---+---+---+---+
2 | * | * |   | * |
  +---+---+---+---+
3 | * | * | * |   |
  +---+---+---+---+

As it shows,  result[i]  = product(num[:i])  * product(nums[i:])

Let dp1[i] = product of numbers before nums[i], not include nums[i],

And dp2[i] = product of numbers after nums[i], not include nums[i]

Then result[i] = dp1[i] * dp2[i]

Time Complexity = O ( N )

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        N = len(nums)
        
        # dp1[i] = product of numbers before nums[i], not include nums[i]
        dp1 = [1] * N
        
        # dp2[i] = product of numbers after nums[i], not include nums[i]
        dp2 = [1] * N
        
        for i in range(1, N):
            dp1[i] = nums[i-1] * dp1[i-1]
            
        for i in reversed(range(N-1)):
            dp2[i] = nums[i+1] * dp2[i+1]
        
        return[ dp1[i] * dp2[i] for i in range(N) ]

[LeetCode] 237. Delete Node in a Linked List

Problem : https://leetcode.com/problems/delete-node-in-a-linked-list/submissions/

Replace value and 'next' reference with the ones of next node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        
        node.val = node.next.val
        node.next = node.next.next

[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

Problem: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Search p, q in binary tree.  If both p and q are in the left sub-tree, the lowest common ancestor is in the left sub-tree. If both p and q are in the right sub-tree, the lowest common ancestor is in the right sub-tree. otherwise the current node is the lowest common ancestor.

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def postorder(node):
            if not node:
                return False, None
            
            leftFound, leftAncestor = postorder(node.left)
            if leftAncestor:
                return True, leftAncestor
            
            rightFound, rightAncestor = postorder(node.right)
            if rightAncestor:
                return True, rightAncestor
            
            if (leftFound or rightFound) and node in [p, q] :
                return True, node
            
            if leftFound and rightFound:
                return True, node
            
            return rightFound or leftFound or node in [p, q], None
        
        return postorder(root)[1]

Edited on 06/30/2021. Use postorder traversal to locate node p and q.

Edited on 11/07/2021. Simplify the postorder based solution. Because all node.val is unique, the order to find p or q does not matter.

[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree

Problem : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Let p be smaller than q.

If root > q,  p and q's lowest common ancestor is in the left sub-tree.

If root < p,  p and q's lowest common ancestor is in the right sub-tree.

Otherwise, we find the lowest common ancestor of p and q.

Time complexity = O ( N )

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        if not root:
            return root
        
        # make sure p < q
        if p.val > q.val:
            p, q = q, p
        
        if root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        
        if root.val < p.val:
            return self.lowestCommonAncestor(root.right, p, q)

        return root

[LeetCode] 234. Palindrome Linked List

Problem : https://leetcode.com/problems/palindrome-linked-list/

Use post-order traversal to check the input string recursively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        left = 0
        
        def postorder(node, right):
            nonlocal head
            nonlocal left
            
            if node:
                tmp = postorder(node.next, right + 1)
                if not tmp:
                    return tmp
                
                if left < right:
                    if node.val != head.val:
                        return False
                
                    head = head.next
                    left += 1
                
                return True
                
            return True
        
        return postorder(head, 0)

[LeetCode] 233. Number of Digit One

Problem : https://leetcode.com/problems/number-of-digit-one/

class Solution:
    def countDigitOne(self, n: int) -> int:
        result, a, b = 0, 1, 1
        
        while n > 0:
            result += (n + 8) // 10 * a
            if n % 10 == 1:
                result += b
                
            b += n % 10 * a
            a *= 10
            
            n //= 10
            
        
        return result

[LeetCode] 232. Implement Queue using Stacks

Problem : https://leetcode.com/problems/implement-queue-using-stacks/

Use 2 stacks

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        result = 0
        tmp = []
        while len(self.stack) > 1:
            tmp.append(self.stack.pop())
        
        result = self.stack.pop()
        while tmp:
            self.stack.append(tmp.pop())
        
        return result
        

    def peek(self) -> int:
        """
        Get the front element.
        """
        result = 0
        tmp = []
        while len(self.stack) > 1:
            tmp.append(self.stack.pop())
        
        result = self.stack[0]
        while tmp:
            self.stack.append(tmp.pop())
        
        return result
        

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.stack) == 0
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

[LeetCode] 231. Power of Two

Problem : https://leetcode.com/problems/power-of-two/

Iteration solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        while n > 1:
            if n % 2 != 0:
                return False

            # n = n // 2
            n = n >> 1
           
        return n == 1

Recursion solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 2 == 0 and self.isPowerOfTwo(n >> 1)

Bit manipulate solution:

Time complexity = O ( 1 )

 
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:   
        
        count = 0
        while n > 0 and count <= 1:
            count += n & 1
            n >>= 1
        
        return count == 1

Number may have only one bit equals to 1 if it is power of 2.

With that observation in mind, we have the one liner solution:

n & (n-1) can trim the first '1' bit from right.

n & (n-1) == 0 means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:    
        return n > 0 and (n - 1) & n == 0

n & (-n) can extract the firt '1' bit from right.

n & (-n) == n also means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (-n) == n

Edited on 05/03/2021. Add the one liner solution.

Edited on 11/07/2021. Add the second one liner solution base on bit manipulation.

[LeetCode] 230. Kth Smallest Element in a BST

Problem: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

In-order traverse the BST until collected K elements.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        
        gen = inorder(root)
        return [next(gen) for _ in range(k)][-1]

Edited on 06/06/2021. Update the inorder traversal approach.

[LeetCode] 229. Majority Element II

Problem : https://leetcode.com/problems/majority-element-ii/

The total number of majority elements should less than 3.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        a = b = 0
        cnt1 = cnt2 = 0
        N = len(nums)
        
        for n in nums:
            if n == a:
                cnt1 += 1
            elif n == b:
                cnt2 += 1
            elif cnt1 == 0:
                a = n
                cnt1 += 1
            elif cnt2 == 0:
                b = n
                cnt2 += 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        
        cnt1 = cnt2 = 0
        
        for n in nums:
            if n == a:
                cnt1 += 1
            if n == b:
                cnt2 += 1
        
        # verify the majority elements
        result = []
        if cnt1 > N // 3:
            result.append(a)
        if cnt2 > N // 3 and a != b:
            result.append(b)
        
        return result

[LeetCode] 228. Summary Ranges

Problem : https://leetcode.com/problems/summary-ranges/

For number A,  create the initial range [A, A].  If the next number B = A + 1, then extends the range as [A, B]. Otherwise create new initial range [B, B] and append to the result list.

Time Complexity = O ( N )

Space Complexity = O ( N )

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result = []
        
        for n in nums:
            if result and n == result[-1][1] + 1:
                result[-1][1] = n
            else:
                result.append([n, n])
        
        return ["{}->{}".format(a, b) if a != b else "{}".format(a) for a, b in result]

[LeetCode] 227. Basic Calculator II

Problem : https://leetcode.com/problems/basic-calculator-ii/

Use stack to postpone the operator evaluation.

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        
        int num = 0;
        Character opt = '+'; 
            
        for (int i = 0; i <= s.length(); i++) {
            if (i == s.length() || s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/') {
                if (opt == '+') {
                    stack.push(num);
                } else if (opt == '-') {
                    stack.push(-1 * num);
                } else if (opt == '*') {
                    stack.push(stack.pop() * num);
                } else if (opt == '/') {
                    stack.push(stack.pop() / num);
                }
                
                opt = i < s.length() ? s.charAt(i) : '+';
                num = 0;
                
            } else if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
        }
        
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }
}

Edited on 12/24/2021. Updated for a simpler stack based solution.

[LeetCode] 226. Invert Binary Tree

Problem : https://leetcode.com/problems/invert-binary-tree/

Invert the tree recursively.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        return root != null ? 
                new TreeNode(root.val, invertTree(root.right), invertTree(root.left))
                : null;
    }
}

Updated on 02/17/2023. Replaced with a Java solution.

[LeetCode] 225. Implement Stack using Queues

Problem : https://leetcode.com/problems/implement-stack-using-queues/

Use 2 queues in turn to save items.

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = deque()
        self.q2 = deque()
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        
        # use empty queue to save item
        if self.q1:
            self.q1.append(x)
        else:
            self.q2.append(x)
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        
        # push items to the empty queue, then pop the last item
        if self.q1:
            while len(self.q1) != 1:
                self.q2.append(self.q1.popleft())
            return self.q1.popleft()
        else:
            while len(self.q2) != 1:
                self.q1.append(self.q2.popleft())
            return self.q2.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        # return the last item of the non-empty queue
        if self.q1:
            return self.q1[-1]
        else:
            return self.q2[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        
        # stack is empty if both queue is empty
        return len(self.q1) == 0 and len(self.q2) == 0
        


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

[LeetCode] 224. Basic Calculator

Problem : https://leetcode.com/problems/basic-calculator/

The expression does not include multiplication and division operator. We can calculate the result directly.

When we encounter left-parenthesis, we push current result to stack and restart calculation of the interim expression.

Time complexity = O ( N )

class Solution:
    def calculate(self, s: str) -> int:
        stackSign = [1]
        stackNum = [0]
 
        i = 0
        sign = 1
      
        while i < len(s):
            if s[i] == ' ':
                i += 1
                continue
            
            if s[i] == '-':
                sign = -1
                i += 1
                continue
                
            if s[i] == '+':
                sign = 1
                i += 1
                continue
                
            if s[i] == '(':
                stackSign.append(sign)
                stackNum.append(0)
                sign = 1 # reset the sign for expression in bracket
                i += 1
                continue
                
            if s[i] == ')':
                tmp = stackSign.pop() * stackNum.pop() 
                stackNum[-1] += tmp
        
                i += 1
                continue
            
            num = 0
            
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            
            stackNum[-1] += sign * num
        
        return stackSign[-1] * stackNum[-1]

Edited on 09/11/2021. Simplify the stack based solution.

[LeetCode] 223. Rectangle Area

Problem : https://leetcode.com/problems/rectangle-area/

             (C, D)
+------------+
|            |
|            | (L, M )
|     +------+------+  (G, H)
|     |      |      |
+-----+------+      |
(A,B) |(I, J)       |
      |             |
      +-------------+
      (E,F)

class Solution:
    def computeArea(self, A: int, B: int, C: int, D: int, E: int, F: int, G: int, H: int) -> int:
        
        def overlapping():
            I = max(A, E)
            J = max(B, F)
        
            L = min(C, G)
            M = min(D, H)
            
            if L > I and M > J:
                return (L - I) * (M - J)
                
            return 0
            
        
        area1 = (C - A) * (D - B)
        area2 = (G - E) * (H - F)
        
        return area1 + area2 - overlapping()

[LeetCode] 222. Count Complete Tree Nodes

 Problem : https://leetcode.com/problems/count-complete-tree-nodes/

DFS Solution:

Time Complexity = O ( N )

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
        

BFS Solution:

Time Complexity = O ( N )

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        
        level = 0
        result = 0
        
        while queue:
            tmp = deque()
            result += len(queue)
            while queue:
                node = queue.popleft()
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            
            # stop traversal when reach the last level  
            if len(tmp) < 2 ** level:
                return result + len(tmp)
            
            queue = tmp
        return result

[LeetCode] 221 Maximal Square

 Problem : https://leetcode.com/problems/maximal-square/

This problem is similar to 84. Largest Rectangle in Histogram .

Base on the same idea, we can find the largest square ends on each row.

Time complexity = O ( M * ( N + N ) ),  M = row of the matrix, N = column of the matrix.

class Solution {
    public int maximalSquare(char[][] matrix) {
        int ROW = matrix.length;
        int COLUMN = matrix[0].length;
        
        // rows[i] = the accumulated height of each column base on ith row
        int[][] rows = new int[ROW][COLUMN];
        int result = 0;
        
        for (int y = 0; y < ROW; y++) {
            for (int x = 0; x < COLUMN; x++) {
                if (matrix[y][x] == '1') {
                    rows[y][x] = 1;
                } else {
                    continue;
                }
                
                // increase the height of column x on row y
                if (y > 0 && matrix[y-1][x] == '1') {
                    rows[y][x] += rows[y-1][x];
                }
            }
            
            // find the largest square base on y row.
            result = Math.max(result, squareBaseOnRow(rows[y]));
        }
        
        return result;
    }
    
    /**
    * find the largest square which bottom line is on current row
    */
    int squareBaseOnRow(int[] row) {
        int N = row.length;
        int result = 0;
        
        Stack<Integer> stack = new Stack();
        
        for (int i = 0; i <= N; i++) {
            // add '0' height column in the end to clean the stack
            int currentHeight = i < N ? row[i] : 0;
            
            while (!stack.isEmpty() && row[stack.peek()] > currentHeight) {
                // the highest column so far
                int height = row[stack.pop()];

                // important!  
                // if stack is empty, there is no shorter column in front of it,
                // then the left boundry = 0.
                // otherwise, the left boundry = stack.peek() + 1

                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                int right = i;

                // because it needs a square ...
                int width = Math.min(height, right - left);
                result = Math.max(result, width * width);
            }
            
            stack.push(i);    
        }
        
        return result;
    }
}

Edited on 12/16/2021. Replaced with the monotonic stack based solution.

[LeetCode] 220. Contains Duplicate III

Problem : https://leetcode.com/problems/contains-duplicate-iii/

Maintain a section which length is K. 

For every newly inserted number nums[i], we look for is there any number >= abs(nums[i] - t).

Because the larger the 'target', the smaller 't' is.

import bisect

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        j = 0
        section = []
        for i in range(len(nums)):
            
            if i - j > k:
                # shift the section window to right
                a = bisect.bisect_left(section, nums[j])
                section.pop(a)
                j += 1
                
            target = abs(nums[i] - t)
            
            # find is there any number larger or equal to 'target'
            # a larger 'target' leads a smaller 't'
            a = bisect.bisect_left(section, target)
            if a != len(section) and abs(section[a] - nums[i]) <= t:
                return True
            
            a = bisect.bisect_left(section, -target)
            if a != len(section) and abs(section[a] - nums[i]) <= t:
                return True
            
            bisect.insort(section, nums[i])
        
        return False

Treeset solution

class TreeSet:
    def __init__(self):
        self.sortedNums = []
        
    def add(self, n):
        bisect.insort(self.sortedNums, n)
        
    def remove(self, n):
        idx = bisect.bisect_left(self.sortedNums, n)
        if idx < len(self.sortedNums) and self.sortedNums[idx] == n:
            self.sortedNums.pop(idx)
    
    def ceiling(self, n):
        idx = bisect.bisect_right(self.sortedNums, n)
        
        if idx == len(self.sortedNums) or self.sortedNums[idx] < n: return None
                       
        return self.sortedNums[idx]     
     
    def floor(self, n):
        idx = bisect.bisect_left(self.sortedNums, n)
        
        if idx == len(self.sortedNums):
            if idx - 1 >= 0:
                return self.sortedNums[idx-1]
            else:
                return None
        
        if self.sortedNums[idx] == n: return n
        
        return self.sortedNums[idx-1] if idx -1 >= 0 else None

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        treeset = TreeSet()
        
        for i in range(len(nums)):
            if i - 1 - k >= 0:
                treeset.remove(nums[i - 1 -k])
                
            s = treeset.ceiling(nums[i])
            if s != None and s <= nums[i] + t: 
                return True
            
            g = treeset.floor(nums[i])
            if g != None and g + t >= nums[i]:
                return True
                      
            treeset.add(nums[i])
            if i - k >= 0:
                treeset.remove(nums[i - k])
            
        return False

Updated 05/02/2021. Add treeset solution.

[LeetCode] 219. Contains Duplicate II

Problem : https://leetcode.com/problems/contains-duplicate-ii/

Remember the last position of each number. If find any number distinct indices difference <= k, that the answer.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        seen = {}
        for i, n in enumerate(nums):
            if n in seen and i - seen[n] <= k:
                return True
            
            # update last position of 'n'
            # assume next 'n' position is j,
            # j -  the 'previous' seen[n] must larger than k
            # e.g.   previous seen[n] .... seen[n] .... j
            seen[n] = i
               
        return False

[LeetCode] 218. The Skyline Problem

Problem : https://leetcode.com/problems/the-skyline-problem/

Use divide-and-conquer approach. 

Merging process:

- Pick the item with smaller X in left or right group.

- Update left-height or right-height.

- current-height = max( left-height, right-height )

- Update skyline if current-height is changed

Time Complexity = O ( N * Log N )

from operator import itemgetter
class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        def update(result, x, h):
            if not result or result[-1][0] != x:
                # add new key point
                result.append([x, h])
            else:
                # update the last key point height
                result[-1][1] = h
                
        def append(result, lst, p, n, h, ch):
            while p < n:
                x, h = lst[p]
                p += 1
                
                if ch != h:
                    update(result, x, h)
                    ch = h
        
        def merge(left, right):
            nl, nr = len(left), len(right)
            pl = pr = 0
            
            # current hight, left hight, right hight
            ch = lh = rh = 0
            
            result = []
            
            while pl < nl and pr < nr:
                lpx, lph = left[pl]
                rpx, rph = right[pr]
                
                x = 0
                if lpx < rpx:
                    x, lh = lpx, lph
                    pl += 1
                else:
                    x, rh = rpx, rph
                    pr +=1 
                
                # use the maximum height 
                max_h = max(lh, rh)
                
                # update / add point if maximum height changes
                if ch != max_h:
                    update(result, x, max_h)
                    ch = max_h
       
            append(result, left, pl, nl, lh, ch)
            append(result, right, pr, nr, rh, ch)

            return result
                    
                    
        def divideAndConqure(start, end):
            if end == start:
                # skyline for zero building
                return []
            
            if end - start == 1:
                # skyline for one building
                l, r, h = buildings[start]
                return [[l, h], [r, 0]]
            
            # divide buildings into two groups and calculate skyline respectively
            mid = start + (end - start) // 2
            left_skyline = divideAndConqure(start, mid)
            right_skyline = divideAndConqure(mid, end)
            
            # merge left and right skyline
            return merge(left_skyline, right_skyline)
        
        return divideAndConqure(0, len(buildings))

[LeetCode] 217. Contains Duplicate

Problem : https://leetcode.com/problems/contains-duplicate

Use hash table to find the duplicate. Time complexity = O ( N )

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        counter = Counter(nums)
        return any( counter[n] >= 2 for n in nums )

Sort the input array first, then find the duplicate. Time complexity = O ( N * Log N )

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        return any(nums[i-1] == nums[i] for i in range(1, len(nums)))

Edited on 05/02/2021. Update hash table approach.

Edited on 05/02/2021. Update locating if sorted array approach.

[LeetCode] 216. Combination Sum III

Problem : https://leetcode.com/problems/combination-sum-iii/

Use backtracking approach. Pick up one number at a time until find a valid combination, then it into the result bucket.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        result = []
        
        def backtracking(start, sums, partial):
            if len(partial) == k and sums == n:
                result.append(partial)
                return
            
            for i in range(start, 10):
                if sums + i <= n:
                    backtracking(i+1, sums+i, partial + [i])
        
        backtracking(1, 0, [])
        return result

[LeetCode] 215. Kth Largest Element in an Array

Problem : https://leetcode.com/problems/kth-largest-element-in-an-array/

A naive solution : 

Time complexity = O ( N Log N )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

Use heap:

Time complexity = O ( N Log K )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        
        while len(nums) > k:
            heapq.heappop(nums)
        
        return nums[0]

In real interview, I assume it expects to be resolved by Quick Sort.

Time complexity = O ( N Log N )

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:  
        def swap(left, right):
            nums[left], nums[right] = nums[right], nums[left]
            
        def partition(left, right):
            pivot = left
            
            while left <= right:
                if nums[pivot] <= nums[left]:
                    left += 1
                elif nums[pivot] >= nums[right]:
                    right -= 1
                else:
                    swap(left, right)
                
            swap(left-1, pivot)
            return left-1
                
        def qsort(left, right):
            while left <= right:
                pivot = partition(left, right)
            
                if pivot == k - 1: 
                    return nums[pivot]
                elif pivot > k - 1:
                    right = pivot - 1
                else:
                    left = pivot + 1
        
            return nums[right]
        
        return qsort(0, len(nums)-1)