I'm a big fan of all three problems and solutions today. I must say that these Easys are getting harder than their counterparts though. But I do often sort by acceptance rate high->low.
There's also a 'perfect' solution included for the Move Zeroes problem!
- Move Zeroes
Problem: Move all the zeroes to the end of the array, in-place.
The problem statement also wants a minimum of total operations.
In production, this would be a perfect use-case of Python's timsort
.sort() -- although, this sometimes creates additional space which excludes the algorithm for this problem. It also uses more operations than we need to!
The trick is realizing that the zero characters are essentially empty space. I'll show you what I mean.
class Solution(object):def moveZeroes(self, nums):""":type nums: List[int]:rtype: void Do not return anything, modify nums in-place instead."""place_nums = 0for i in range(len(nums)):if nums[i] != 0:if i > place_nums:nums[place_nums] = nums[i]place_nums += 1for i in range(place_nums, len(nums)):nums[i] = 0# return is excluded as per problem statement
We place all the numbers at the start of the array and then overwrite the part of the array that should now be zeros.
Runtime: 32 ms, faster than 100.00% of Python online submissions for Move Zeroes.
- Merge Two Sorted Lists
Problem: Merge two sorted linked list, return as a linked list
I chose to solve this recursively as it really cuts down on the if/else blocks. The code is a little easier to read as well.
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""if not l1 and not l2:return Noneelif not l1:return l2elif not l2:return l1node = ListNode(0)if l1.val < l2.val:node.val = l1.valnode.next = self.mergeTwoLists(l1.next, l2)else:node.val = l2.valnode.next = self.mergeTwoLists(l1, l2.next)return node
However, cute as this solution is, there will be stack issues with long lists.
- Merge Two Binary Trees
Problem: Merge two binary trees, that is to say, fold them onto one and other, summing overlapping nodes.
This uses a similar recursive strategy to the linked list problem earlier.
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object):def mergeTrees(self, t1, t2):""":type t1: TreeNode:type t2: TreeNode:rtype: TreeNode"""if not t1:return t2if not t2:return t1result = TreeNode(t1.val + t2.val)result.left = self.mergeTrees(t1.left, t2.left)result.right = self.mergeTrees(t1.right, t2.right)return result