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