Leetcode 30 Day Challenge - Week 1 Solutions

April 10, 2020 | 10 min read

With the wide spread of COVID-19, many people are encouraged to work from home. Leetcode initiate a 30-day challenge from April 1st to April 30th, one problem for each day. URL

P1. Single Number

Problem Statement

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Idea

The first idea coming into mind is counting! Just count each number’s occurrences and return the number with a count of 1. The time complexity is $O(N)$ , but the space complexity is also $O(N)$ . Can we save the extra memory space? The answer is yes! We can use bit manipulation! Note that for the operator xor, 1 xor 0 = 1, 1 xor 1 = 0 and 0 xor 0 = 0 . For any number A, A xor A = 0 and A xor 0 = A (try to prove it yourself!). If we xor all the numbers in a list, what will happen? If a number appears twice, the xor operation between them will cancel them out! Given this property, we just xor all the numbers, and the number with a count of 1 will be left!

Solution

from functools import reduce
from operator import xor

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums)

P2. Happy Number

Problem Statement

Write an algorithm to determine if a number n is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example:

Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Idea

Apparently the problem statement tells us what to do. Here comes the first version of the code:

class Solution:
    def isHappy(self, n: int) -> bool:
        if n <= 0:
            return False
        s = sum(i*i for i in map(int, str(n)))
        while s != 1:
            s = sum(i*i for i in map(int, str(s)))

        return True

Unfortunately, Time Limit Exceeded error happens! The online judge cannot do its job if you just loop endlessly. So, we have to break the loop, if there is a loop. How do we know there is a loop? When a number appears twice, there must be loop! Here comes the second version:

Solution

class Solution:
    def isHappy(self, n: int) -> bool:
        if n <= 0:
            return False
        s = n
        seen = set()
        while s != 1:
            if s in seen:
                return False
            seen.add(s)
            s = sum(i*i for i in map(int, str(s)))

        return True

P3. Maximum Subarray

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Idea

This is the most difficult problem of the week. Unfortunately, I did not manage to solve this problem in an interview with Bytedance last year, which makes me fail the first round.

The first idea coming to mind is use brute force. Just enumerate every span and calculate the sum, and return the biggest sum. If you precompute the prefix sum of the array, i.e. For $a_i$ , you precompute $s_i = \sum_{i \in (1, i)}{a_i}$ , which take $O(N)$ , it would takes $O(N^2)$ to calculate the sum of a subspan $a_i \cdots a_j, i, j \in [1, N]$ .

Can we do better? It looks that we can use dynamic programming to solve this problem. The idea of dynamic programming is to divide the original problem into smaller sub-problems, which is the prefix or the suffix of the original problem. How can we use DP here?

Suppose we have a array $A = [a_1, a_2, a_3, a_4, a_5]$ and we know solution of $A$ is $S$ . The solution must be the sum of some subspan of this array. If we append an addition element $a_6$ , what is the solution to this new array?

1 3 4 -100 5 | 10

When trying to calculate the solution to the new array, let’s define two variable: $S$ is the solution of the array, and $S'$ is the largest sum which ends at the end of the array. If an additional element $a_6$ comes, we first update $S'$ : $S' = max(S'+a_6, a_6)$ , then compare the old $S$ with $S'$ : $S = max(S, S')$ .

Complexity Analysis: Since the additional element only takes constant time, we can say our time complexity is $O(N)$ .

Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum = 0
        max_sum = -float("inf")
        for num in nums:
            current_sum = max(current_sum + num, num)
            max_sum = max(max_sum, current_sum)
        return max_sum

P4. Move Zeroes

Problem Statement

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array. Minimize the total number of operations.

Idea

Without making a copy of the array, we have to move the numbers around. At first thought, it seems complex to try to swap the position of the numbers. But think again! At the end of the story, all the positive numbers are moved to the begining of the array. Index 0 is the first positive number, index 1 is the second positive number… The solution just pops up: we just assign index 0 with the first positive number, assign index 1 with the second positive number, and so on. We just use a variable to keep track of the order of the positive numbers, and copy it to the correct place. After that, we fill the remaining positions with 0s.

Solution

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        pos = 0
        for i, num in enumerate(nums):
            if num != 0:
                nums[pos] = num
                pos += 1
        for i in range(pos, len(nums)):
            nums[i] = 0
        return nums

P5. Best Time to Buy and Sell Stock II

Problem Solution

Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$ .

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

Idea

Buy at the valley and sell at the peak. Just mind the corner cases, i.e. the beginning and end of the array.

Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        buy, sell = None, None
        for i in range(len(prices)):
            if i == 0 and i+1 < len(prices) and prices[i+1] > prices[i]:
                buy = prices[i]
            elif i > 0 and prices[i] <= prices[i-1] and i < len(prices) - 1 and prices[i] < prices[i+1]:
                buy = prices[i]
            elif i > 0 and prices[i] > prices[i-1] and ( i < len(prices) - 1 and prices[i] >= prices[i+1] or i == len(prices) - 1):
                sell = prices[i]
                profit += sell - buy
        return profit

P6. Group Anagrams

Problem Statement

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

All inputs will be in lowercase. The order of your output does not matter.

Idea

Let’s hash the anagrams to the same key: first count the frequency of the chars, then use the frequency of the chars to generate a unique key. Let’s use the most simple serialization: $char1count1char2count2...$

Solution

from collections import defaultdict, Counter

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def hash(s):
            c = Counter(s)
            return ''.join((f'{char}{count}' for (char, count) in sorted(c.items())))
        groups = defaultdict(list)
        for token in strs:
            groups[hash(token)].append(token)
        return groups.values() 

P7. Counting Elements

Problem Statement

Given an integer array arr, count element x such that x + 1 is also in arr.

If there’re duplicates in arr, count them seperately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:

1 <= arr.length <= 1000
0 <= arr[i] <= 1000

Idea

The in operator for membership test takes $O(N)$ for list and $O(1)$ for set. Therefore we transform the list to the set first to improve efficiency.

Solution

class Solution:
    def countElements(self, arr: List[int]) -> int:
        arr_set = set(arr)
        return sum((1 if a + 1 in arr_set else 0 for a in arr))