Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 117. Populating Next Right Pointers in Each Node II

By zxi on November 29, 2021

Given a binary tree

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 6000].
  • -100 <= Node.val <= 100

Follow-up:

  • You may only use constant extra space.
  • The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Solution -2: Group nodes into levels

Use pre-order traversal to group nodes by levels.
Connects nodes in each level.

Time complexity: O(n)
Space complexity: O(n)

C++

Solution -1: BFS level order traversal

Time complexity: O(n)
Space complexity: O(n)

C++

Solution 1: BFS w/o extra space

Populating the next level while traversing current level.

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

By zxi on November 28, 2021

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

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

Example 1:

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

Example 2:

Input: prices = [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: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Example 4:

Input: prices = [1]
Output: 0

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105

Solution: DP

A special case of 花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV where k = 2.

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 143. Reorder List

By zxi on November 28, 2021

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000

Solution: Three steps

Step 1: Find mid node that splits the list into two halves.
Step 2: Reverse the second half
Step 3: Merge two lists

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 147. Insertion Sort List

By zxi on November 28, 2021

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head.

The steps of the insertion sort algorithm:

  1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
  3. It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Constraints:

  • The number of nodes in the list is in the range [1, 5000].
  • -5000 <= Node.val <= 5000

Solution: Scan from head

For each node, scan from head of the list to find the insertion position in O(n), and adjust pointers.

Time complexity: O(n2)
Space complexity: O(1)

C++

花花酱 LeetCode 152. Maximum Product Subarray

By zxi on November 28, 2021

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution: Track high and low

Compute the low / high of prefix product, reset if nums[i] is higher than high or lower than low.

Swap low and high if nums[i] is a negative number.

e.g. [2, 3, -1, 8, -2]
nums[i] = 2, low = 2, high = 2
nums[i] = 3, low = 3, high = 2 * 3 = 6
nums[i] = -1, low = 6 * -1 = -6, high = -1
nums[i] = 8, low = -6 * 8 = -48, high = 8
nums[i] = -2, low = 8*-2 = -16, high = -48 * -2 = 96

Time complexity: O(n)
Space complexity: O(1)

C++