Leetcode Solutions Week 1.1

110. Balanced Binary Tree

#DFS #Python

Time Complexity : O(n)

Space Complexity: O(k) where k is constant

Code :

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    
    def helper(self, root):
        if not root:
            return (True, 0)
        else:
            left_result = self.helper(root.left)
            right_result = self.helper(root.right)
            # print(left_result[0], right_result[0], left_result[1], right_result[1])
            return (left_result[0] and right_result[0] and abs(left_result[1] - right_result[1]) <= 1, 1+max(left_result[1], right_result[1]))
def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return_value = self.helper(root)
        return return_value[0]

746. Min Cost Climbing Stairs

#DP #Python #Rod Cutting Problem # Single Array DP

Time Complexity: O(n)

Code :

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        Very similar to the rod cutting problem but with a twist
        """
        net_cost = [0 for i in range(len(cost)+1)]
        
        for i in range(2, len(cost)+1):
            net_cost[i] = min(net_cost[i-1]+cost[i-1], net_cost[i-2]+cost[i-2])
            
        return net_cost[-1]

1014. Capacity To Ship Packages Within D Days **(Unique binary search paradigm)

# Binary Search # Medium # Python

Similar problems : 875. Koko Eating Bananas
774. Minimize Max Distance to Gas Station

Articles related to problem : https://www.topcoder.com/community/competitive-programming/tutorials/binary-search

User top solution : https://leetcode.com/lee215/

Time complexity : O(nlog(n)) where n is number of shipments (n => for each for-loop within the while and logn for the binary search)

Code :

class Solution(object):
    def shipWithinDays(self, weights, D):
        """
        :type weights: List[int]
        :type D: int
        :rtype: int
        """
        left = max(weights)
        right = sum(weights)
        while(left < right):
            mid = (left + right) // 2
            current = 0
            days_needed = 1
            for w in weights:
                if current + w > mid:
                    current = w
                    days_needed += 1
                else:
                    current += w
                    
            if days_needed > D:
                left = mid + 1
            else:
                right = mid
                
        return left

189. Rotate Array

# Array

Complexity : O(n²), can be done inplace with O(1) extra space

Code :

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
            popped_element = nums.pop()
            nums.insert(0, popped_element)

165. Compare Version Numbers

# String Manipulation # Time consuming # Corner-case-king

Code :

class Solution(object):
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        version1 = version1.split(".")
        version2 = version2.split(".")
        
        min_len = min(len(version1), len(version2))
        
        for i in range(min_len):
            # print(version1[i], version2[i])
            v1 = version1[i]
            while v1.find('0') == 0: v1 = v1[1:]
            v1 = int(v1 or '0')
            v2 = version2[i]
            while v2.find('0') == 0: v2 = v2[1:]
            v2 = int(v2 or '0')
            if  v1 > v2:
                return 1
            elif v2 > v1:
                return -1
            
        if len(version1) > len(version2):
            for i in range(len(version2), len(version1)):
                v1 = version1[i]
                while v1.find('0') == 0: v1 = v1[1:]
                v1 = int(v1 or '0')
                if v1 != 0:
                    return 1
            return 0
        elif len(version2) > len(version1):
            for i in range(len(version1), len(version2)):
                v2 = version2[i]
                while v2.find('0') == 0: v2 = v2[1:]
                v2 = int(v2 or '0')
                if v2 != 0:
                    return -1
            return 0
        else:
            return 0