23.02.22 Today’s Leetcode

1011. Capacity To Ship Packages Within D Days (medium)

Brute Force Approach

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        count = 10**9
        ans = max(sum(weights) // days, max(weights))
        while count > days:
            total = 0
            count = 0
            for weight in weights:
                total += weight
                if total > ans:
                    total = weight
                    # print(total)
                    count += 1
            if total > 0:
                count += 1
            print(ans, count)
            if count > days:
                ans += 1
        return ans

Binary Search Approach

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def ship_packages(capacity):
            day = 1
            total = 0
            for weight in weights:
                total += weight
                if total > capacity:
                    total = weight
                    day += 1
                    if day > days:
                        return False
            return True
        
        left, right = max(weights), sum(weights)
        while left < right:
            middle = left + (right-left) // 2
            if ship_packages(middle):
                right = middle
            else:
                left = middle + 1
        return left
    
#Binary Search
#Time complexity: O(NlogN)
#Space complexity: O(1)

977. Squares of a Sorted Array (easy)

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        zero, zero_index = 10**9, 0
        for i in range(n):
            num = abs(nums[i])
            if num < zero:
                zero = num
                zero_index = i
        res = [zero**2]
        i = zero_index - 1
        j = zero_index + 1
        while (i >= 0 and j < n):
            a, b = abs(nums[i]), abs(nums[j])
            if a < b:
                res.append(a ** 2)
                i -= 1
            else:
                res.append(b ** 2)
                j += 1
        while (i >= 0):
            res.append(nums[i] ** 2)
            i -= 1
        while (j < n):
            res.append(nums[j] ** 2)
            j += 1
        return res

189. Rotate Array (medium)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        temp = nums[-k:]
        # print(temp)
        for i in range(len(nums) - k - 1, -1, -1):
            nums[i + k] = nums[i]
        for i in range(k):
            nums[i] = temp[i]

109. Convert Sorted List to Binary Search Tree (medium)

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next


        def dfs(start, end):
            if start >= end:
                return None
            nonlocal arr
            mid = (start + end) // 2
            node = TreeNode(arr[mid])
            node.left = dfs(start, mid)
            node.right = dfs(mid + 1, end)
            return node
        
        return dfs(0, len(arr))

129. Sum Root to Leaf Numbers (medium)

# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        ans = 0 

        def dfs(node, value):
            if not node:
                return
            if not node.left and not node.right:
                nonlocal ans
                ans += value * 10 + node.val
                return
            value = value * 10
            value += node.val
            dfs(node.left, value)
            dfs(node.right, value)
        
        dfs(root, 0)
        return ans