[LeetCode] 327. Count of Range Sum

 Problem : https://leetcode.com/problems/count-of-range-sum/

Time Complexity = O ( N ** 2 ). Time Limit Exceeded.

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        N = len(nums)
        
        sums = [0] * (N+1)
        
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
        result = 0
        for i in range(N+1):
            for j in range(i+1, N+1):
                if lower <= sums[j] - sums[i] <= upper:
                    result += 1
        
        return result

Count and merge sort solution:

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        
        def countAndMergeSort(sums, start, end):
            if end - start <= 1: return 0
            mid = start + (end - start) // 2
            
            count = countAndMergeSort(sums, start, mid) + countAndMergeSort(sums, mid, end)
            
            j = k = t = mid
            cache = [0] * (end - start)
            r = 0
            
            for i in range(start, mid):
                while k < end and sums[k] - sums[i] < lower: 
                    k += 1
                while j < end and sums[j] - sums[i] <= upper: 
                    j += 1
                while t < end and sums[t] < sums[i]:
                    cache[r] = sums[t]
                    r += 1
                    t += 1
    
                cache[r] = sums[i]
                r += 1
            
                count += j - k
            
            r = 0
            for i in range(start, t):
                sums[i] = cache[r]
                r += 1
            
            return count
            
        
        
        
        N = len(nums)
        
        sums = [0] * (N+1)    
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
    
        return countAndMergeSort(sums, 0, len(sums))
                
       

[LeetCode] 321. Create Maximum Number

 Problem : https://leetcode.com/problems/create-maximum-number/

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        
        def monotoneDecreasingSequence(nums, size):
            if size <= 0: return []
            
            dropCount = len(nums) - size
            
            result = []
            
            for n in nums:
                while result and result[-1] < n and dropCount > 0:
                    result.pop()
                    dropCount -= 1
                    
                result.append(n)
            
            return result[:size]
    
    
        def merge(n1, n2):
            i = j = 0
            result = []
            while i < len(n1) or j < len(n2):
                if i < len(n1) and j < len(n2):
                    # important! compare the rest numbers in lexical 
                    if n1[i:] > n2[j:]:
                        result.append(n1[i])
                        i += 1
                    else:
                        result.append(n2[j])
                        j += 1
                elif i < len(n1):
                    result.append(n1[i])
                    i += 1
                else:
                    result.append(n2[j])
                    j += 1
            
            return result
        
        result = []
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) +1):
            mds1 = monotoneDecreasingSequence(nums1, i)
            mds2 = monotoneDecreasingSequence(nums2, k - i)
            merged = merge(mds1, mds2)
            
            result = max(result, merged)
        
        return result

[LeetCode] 315. Count of Smaller Numbers After Self

 Problem : https://leetcode.com/problems/count-of-smaller-numbers-after-self/

The original array is unsorted. Iterate the input array from the rear and use insert sort to create a sorted sequence.  The insert position indicates the number of smaller elements.

Time Complexity = O ( N * Log N  + N * N ).   Inserting number to array is O(N) time complexity operation.

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]: 
        def lowerBound(n, dp):
            """
            the first poistion on the left where dp[i] <= n
            """
            left, right = 0, len(dp)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if dp[mid] == n:
                    right = mid
                elif dp[mid] < n:
                    left = mid + 1
                elif dp[mid] > n:
                    right = mid
            
            return right
        
        result = [0] * len(nums)
        dp = []
        
        for i in reversed(range(len(nums))):
            n = nums[i]
            # insert sort
            j = lowerBound(n, dp)
            dp.insert(j, n)
            
            result[i] = j
            
        return result

Use Python build-in lib:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        dp = []
        result = [0] * len(nums)
        
        for i in reversed(range(len(nums))):
            
            lowerBound = bisect.bisect_left(dp, nums[i])
            
            result[i] = lowerBound
            
            bisect.insort_left(dp, nums[i])
        
        return result

Use segment tree:

class SegmentTree:
    def __init__(self, m):
        # M = number of leafs of the segement tree
        self.M = m
        
        # Because segement tree is a completed binary tree.
        # If number of leafs = M, then number of internal nodes = M - 1.
        # Because tree[0] will not be used, the total number of nodes = 2 * M
        self.tree = [0] * (2 * self.M)
        
    def update(self, n, delta):
        """
        update counter of number on index n
        """
        
        # number n leaf node index = n + M
        n += self.M
        self.tree[n] += delta
        
        n //= 2
        while n > 0:
            # left child node index = 2 * n
            # right child node index = 2 * n
            self.tree[n] = self.tree[2*n] + self.tree[2*n+1]
            n //= 2
    
    def query(self, left, right):
        """
        query accumulative count between range [left, right).
        the 'right' is excluded.
        """
        
        result = 0
        
        left += self.M
        right += self.M
        
        while left < right:
            if left & 1 == 1:
                # on left side, the left child node is not in the needed range.
                result += self.tree[left]
                left += 1
            
            left //= 2
            
            if right & 1 == 1:
                # on right side, the right child node is not in the needed range
                right -= 1
                result += self.tree[right]
            
            right //= 2
        
        return result

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        mi = min(nums)
        mx = max(nums) + 1
        m = mx - mi + 1
        segmentTree = SegmentTree(m)
        
        # query in segement tree for number of smaller elements to the right of nums[i]
        result = [0] * len(nums)
        for i in reversed(range(len(nums))):
            n = nums[i] - mi
            
            result[i] = segmentTree.query(0, n)
            segmentTree.update(n, 1)
        
        return result

Use fenwick tree:

class FenwickTree:
    def __init__(self, m):
        self.tree = [0] * m
    
    def update(self, n, delta):
        while n < len(self.tree):
            self.tree[n] += delta
            n += self.lowbit(n)
    
    def query(self, n):
        result = 0
        
        while n > 0 :
            result += self.tree[n]
            n -= self.lowbit(n)
        
        return result
            
    
    def lowbit(self, n):
        return n & (~(n-1))
        
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        mi = min(nums)
        mx = max(nums) + 1
        m = mx - mi + 1
        
        fenwickTree = FenwickTree(m)
        
        result = [0] * len(nums)
        
        for i in reversed(range(len(nums))):
            # fenwick tree node index starts with 1
            n = nums[i] - mi + 1
            
            result[i] = fenwickTree.query(n-1)
            fenwickTree.update(n, 1)
        
        return result

Use merge sort approach.

Split the nums array into left and right parts.

Sort the right part first, then for each number on the left part, use binary-search to find count of number less than it. (lower-bound)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        result = [0] * len(nums)
        
        def mergeSort(left, right):
            if left + 1 == right: 
                return 

            mid = left + (right - left) // 2

            # sort right side
            mergeSort(mid, right)

            # for each number on left side, find
            # how many number is smaller than it on right side.
            for i in range(left, mid):
                lowerBound = bisect.bisect_left(nums, nums[i], mid, right)
                # count of smaller numbers = lowerBound - mid
                result[i] += lowerBound - mid
            
            # sort left side
            mergeSort(left, mid)
            
            # merge the sorted left and right side
            tmp = []
            i = left
            j = mid

            while i < mid and j < right:
                if nums[i] < nums[j]:
                    tmp.append(nums[i])
                    i += 1
                else:
                    tmp.append(nums[j])
                    j += 1

            while i < mid:
                tmp.append(nums[i])
                i += 1

            while j < right:
                tmp.append(nums[j])
                j += 1

            for i in range(right - left):
                nums[left+i] = tmp[i]
        
        # merge sort starts
        mergeSort(0, len(nums))
        
        return result

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

[LeetCode] 191. Number of 1 Bits

Problem : https://leetcode.com/problems/number-of-1-bits/

An one liner solution:

Time Complexity = O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        return sum([n >> offset & 1 for offset in range(32)])

Use bit manipulate trick to only count '1'

class Solution:
    def hammingWeight(self, n: int) -> int:
        result = 0
        while n:
            result += 1
            n = n & (n-1)
        
        return result

A divide and conquer approach. And use memorization to accelerate. ( The fastest solution. )

class Solution:
    def hammingWeight(self, n: int) -> int:
        
        #000 001 010 011 100 101 110 111
    
        @cache
        def helper(x):
            return helper(x >> 3) + helper(x & 7) if x > 7 else [0, 1, 1, 2, 1, 2, 2, 3][x]
                
        return helper(n)

Edited on 05/04/2021. Add the only count '1' solution.

Edited on 05/04/2021. Add the divide and conquer solution.

[LeetCode] 153. Find Minimum in Rotated Sorted Array

Problem : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Binary search solution:

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

Divide and conquer solution:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        
        def helper(left, right):
            if nums[left] <= nums[right]:
                return nums[left]
            
            mid = left + (right - left) // 2
            
            return min(helper(left, mid), helper(mid+1, right))
        
        return helper(0, len(nums) - 1)

[LeetCode] 148. Sort List

Problem : https://leetcode.com/problems/sort-list/

Use merge sort to get O( n log n ) time complexity.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
              
        # divide into 2 parts
        fast, slow = head, head
        
        while fast and fast.next:
            fast = fast.next.next
            if fast:
                slow = slow.next
            
        tmp = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(tmp)

        return self.merge(left, right)
    
    def merge(self, left, right):
        dummy = ListNode(0)
        p = dummy
        
        while left and right:
            if left.val <= right.val:
                p.next = left
                p = p.next
                left = left.next
            else:
                p.next = right
                p = p.next
                right = right.next
        
        while left:
            p.next = left
            p = p.next
            left = left.next
        
        while right:
            p.next = right
            p = p.next
            right = right.next
        
        p.next = None
        
        return dummy.next

[LeetCode] 53. Maximum Subarray

Problem : https://leetcode.com/problems/maximum-subarray/

O( N ) time complexity solution is based on DP.

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    
        result = -2 ** 31
        tmp = 0
        
        for i in range(len(nums)):
            # restart sub-array from i if its sum less than nums[i]
            tmp = max(tmp + nums[i], nums[i])            
            result = max(result, tmp)

        return result

Divide and conquer solution:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        def helper(start, end):
            if end - start == 1:
                return nums[start]
            
            mid = start + (end - start) // 2
            
            # max of left sub-array
            left_max = helper(start, mid)
            
            # max of right sub-array
            right_max = helper(mid, end)
        
            # max of middle
            mid_max = nums[mid]
            t = mid_max
            
            for i in range(mid-1, start-1, -1):
                t += nums[i]
                mid_max = max(mid_max, t)
                
            t = mid_max
            for i in range(mid+1, end): 
                t += nums[i]
                mid_max = max(mid_max, t)
            
            return max(left_max, mid_max, right_max)
            
         
        return helper(0, len(nums))
    

[LeetCode] 23. Merge k Sorted Lists

Problem : https://leetcode.com/problems/merge-k-sorted-lists/

Must divide and conquer approach to avoid exceeding time limit. 

Time Complexity = O( N log(len(lists) )

Space Complexity: O(1)

 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
    
        def merge(l1, l2):
            if l1 and l2:
                if l1.val < l2.val:
                    l1.next = merge(l1.next, l2)
                    return l1
                else:
                    l2.next = merge(l1, l2.next)
                    return l2
                
            return l1 if l1 else l2
        
        
        def helper(left, right):
            if left == right:
                return None
            
            if right - left == 1:
                return lists[left]
            
            if right - left == 2:
                return merge(lists[left], lists[left+1])
            
            
            mid = left + (right - left) // 2
            return merge(helper(left, mid), helper(mid, right))
    
            
        return helper(0, len(lists))

Use priority queue to merge K sorted list. N = max length of lists

Time Compleixty = O(N * Log K)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) pq.offer(head);
        }
        
        while (!pq.isEmpty()) {
            p.next = pq.poll();
            p = p.next;
            if (p.next != null) pq.offer(p.next);
        }

        return dummy.next;
    }
}