LeetCode 442 – Python 3 (Week 4 – 03)

Solution 1

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for num in nums:
            index = abs(num) - 1
            if nums[index] > 0:
                nums[index] = - nums[index]
            else:
                res.append(index+1)
        
        return res
        

Time complexity is O(n). Space complexity is O(1).

LeetCode 448 – Python 3 (Week 4 – 02)

Solution 1

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(0, len(nums)):
            index = abs(nums[i]) - 1
            nums[index] = -abs(nums[index])
            
            
        return [i + 1 for i in range(len(nums)) if nums[i] > 0]

Time complexity is O(n). Space complexity is O(1).

*LeetCode 437 – Python 3 (Week 4 – 01)

Solution 1

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

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        #go through reach node. count the paths when the start node is that node.
        
        self.numOfPaths = 0
        
        self.dfs(root, sum)

        return self.numOfPaths
    
    def dfs(self, node, sum):
        if node is None:
            return 
        self.count(node, sum) 
        self.dfs(node.left, sum)
        self.dfs(node.right, sum)
        
    def count(self, node, sum):
        if node is None:
            return
        if node.val == sum:
            self.numOfPaths += 1       
        self.count(node.left, sum-node.val)
        self.count(node.right, sum-node.val)

Both time complexity and space complexity are O(n*n) to O(nlogn).

Solution 2

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

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.result = 0
        presum = {0:1}
        currentsum = 0
        
        self.dfs(root, sum, 0, presum)
        
        return self.result
    
    def dfs(self, root, sum, currentsum, presum):

        if root is None:
            return  
        
        currentsum += root.val
        needpresum = currentsum - sum
        
        self.result += presum.get(needpresum, 0)
        presum[currentsum] = presum.get(currentsum, 0) + 1
        
        self.dfs(root.left, sum, currentsum, presum)
        self.dfs(root.right, sum, currentsum, presum)
        # *********
        presum[currentsum] -= 1

Both time complexity and space complexity are O(n).

LeetCode 283 – Python 3 (Week 3 – 08)

Solution 1

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero = 0 #position of 0
        for i in range(len(nums)):
            #if the num is not 0, move the num to the position of last zero
            if nums[i] != 0:
                nums[zero] = nums[i]
                zero += 1
                
        for i in range(zero, len(nums)):
            nums[i] = 0

Time complexity is O(n). Space complexity is O(1).

Solution 2

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort(key=bool, reverse=True)

Time complexity is O(n log n). Space complexity is O(n).

Solution 3

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero = 0
        
        #swap current first 0 and next non-zero elements
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[i], nums[zero] = 0, nums[i]
                zero += 1

Time complexity is O(n). Space complexity is O(1).

LeetCode 234 – Python 3 (Week 3 – 07)

Solution 1

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        
        #if head == None: return False 
        #if[], output should be true
        
        #fist-find the middle node, second-reverse half of the list, third-compare
        fast = slow = head
        pre = None      
        while fast and fast.next: #make sure fast is the last one or None.
            fast = fast.next.next
            slow = slow.next          
            head.next = pre
            pre = head
            head = slow
            
        
        #1-2-3-4, now slow is 3, fast is null, pre is 2
        #1-2-3-4-5, slow is 3, fast is 5, pre is 2      
        if fast: slow = slow.next #slow is 4
            
                        
        #compare
        while pre and slow:
            if pre.val != slow.val:
                return False
            else:
                pre = pre.next
                slow = slow.next
        
        return True

Time complexity is O(n). Space complexity is O(1).

LeetCode 226 – Python 3 (Week 3 – 06)

Solution 1

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

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        
        #Recusive
        if not root: return None
        right = self.invertTree(root.left)
        left = self.invertTree(root.right)
        root.right = right
        root.left = left
        return root

Time complexity is O(n). Space complexity is O(n).

Solution 2

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

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        
        #Iterative
        if not root: return None
        current = root
        stack = []
        while stack or current:
            if current:
                stack.append(current)
                current = current.left
            else:
                current = stack.pop()
                current.right, current.left = current.left, current.right
                current = current.left
                
        return root

Time complexity is O(n). Space complexity is O(n).

LeetCode 206 – Python 3 (Week 3 – 05)

Solution 1: Iterative

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        #Iterative
        dummy = ListNode(float('-inf'))

        while head:
            dummy.next, head.next, head = head, dummy.next, head.next
        return dummy.next
            

Time complexity is O(n). Space complexity is O(1).

Solution 2: Recursive

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        #Recursive
        if not head or not head.next: return head
        
        left = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return left

Time complexity is O(n). Space complexity is O(n).

LeetCode 155 – Python 3 (Week 3 – 04)

Solution 1

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.array = []

    def push(self, x: int) -> None:
        cur_min = self.getMin()
        if cur_min == None or x < cur_min: cur_min = x #here we can not use if not cur_min. Because if cur_min is 0, it will be considered as not cur_min is true! 
        self.array.append((x, cur_min))
        

    def pop(self) -> None:
        self.array.pop()
        

    def top(self) -> int:
        if not self.array: return None
        return self.array[-1][0]
        

    def getMin(self) -> int:
        if not self.array: return None
        return self.array[-1][1]


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

Time complexity and space complexity are O(1).

Warning: Do not use ” if not x”, if “x” is a number!

LeetCode 198 – Python 3 (Week 3 – 03)

Solution 1

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        # for house 0, we have to choose: rob or not. If we rob, the max total amount we can get is the max amount at point house -2 + amount in house 0. If not, the max total amount we can get is the max amount at point house -1.Thus, the largest amount is max( amount at house -2 + house 0, amount at house -1)
        
        dp_last, dp_now = 0, 0
        for num in nums:
            dp_last, dp_now = dp_now, max(dp_last + num, dp_now)
            
        return dp_now

Time complexity is O(n). Space complexity is O(1).

LeetCode 169 – Python 3 (Week 3 – 02)

Solution 1:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = {}
        
        for num in nums:
            if num in dic:
                dic[num] += 1
            else:
                dic[num] = 1
        
        for v,k in dic.items():
            if k > len(nums)/2:
                return v

Time complexity is O(n). Space complexity is O(n).

Solution 2

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
  
        #The number of majority element is more than n/2. Set the first number as the majority number. Count this number and not this number. When equal, delete this part. Go on...
        index, cnt = 0, 1
        
        for i in range(1,len(nums)):
            if nums[i] == nums[index]:
                cnt += 1
            else:
                cnt -= 1
                if cnt == -1:
                    index = i
                    cnt = 1

                    
        return nums[index]
        

Time complexity is O(n). Space complexity is O(1).

Solution 3

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]

Time complexity is O(nlgn). It is the time to sort array in Python. Space complexity is O(n). Timsort is used.

Create your website at WordPress.com
Get started