Posts tagged as “medium”

花花酱 LeetCode 2090. K Radius Subarray Averages

By zxi on November 28, 2021

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.

Example 1:

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
- avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
  Using integer division, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index.

Example 2:

Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
  avg[0] = 100000 / 1 = 100000.

Example 3:

Input: nums = [8], k = 100000
Output: [-1]
Explanation: 
- avg[0] is -1 because there are less than k elements before and after index 0.

Constraints:

n == nums.length
1 <= n <= 10⁵
0 <= nums[i], k <= 10⁵

Solution: Sliding Window

We compute i – k’s average at position i.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getAverages(vector<int>& nums, int k) {

const int n = nums.size();

long long sum = 0;

vector<int> ans(n, -1);

for (int i = 0; i < n; ++i) {

sum += nums[i];

if (i >= 2 * k) {

ans[i - k] = sum / (2 * k + 1);

sum -= nums[i - 2 * k];

}

return ans;

}

};

花花酱 LeetCode 137. Single Number II

By zxi on November 27, 2021

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Solution: Bit by bit

Since every number appears three times, the i-th bit must be a factor of 3, if not, that bit belongs to the single number.

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

C++

// Author: Huahua

class Solution {

public:

int singleNumber(vector<int>& nums) {

int ans = 0;

for (int s = 0; s < 32; ++s) {

int mask = 1 << s;

int sum = 0;

for (int x : nums)

if (x & mask) ++sum;

if (sum % 3) ans |= mask;

}

return ans;

}

};

花花酱 LeetCode 114. Flatten Binary Tree to Linked List

By zxi on November 27, 2021

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

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

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Solution 1: Recursion

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

Python3

# Author: Huahua

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

"""

Do not return anything, modify root in-place instead.

"""

def solve(root: Optional[TreeNode]):

if not root: return None, None

if not root.left and not root.right: return root, root

l_head = l_tail = r_head = r_tail = None

if root.left:

l_head, l_tail = solve(root.left)

if root.right:

r_head, r_tail = solve(root.right)

root.left = None

root.right = l_head or r_head

if l_tail:

l_tail.right = r_head

return root, r_tail or l_tail

return solve(root)[0]

Solution 2: Unfolding

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

Python3

# Author: Huahua

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

while root:

if root.left:

prev = root.left

while prev.right: prev = prev.right

prev.right = root.right

root.right = root.left

root.left = None

root = root.right

花花酱 LeetCode 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses

By zxi on November 27, 2021

You are given a 0-indexed string street. Each character in street is either 'H' representing a house or '.' representing an empty space.

You can place buckets on the empty spaces to collect rainwater that falls from the adjacent houses. The rainwater from a house at index i is collected if a bucket is placed at index i - 1 and/or index i + 1. A single bucket, if placed adjacent to two houses, can collect the rainwater from both houses.

Return the minimum number of buckets needed so that for every house, there is at least one bucket collecting rainwater from it, or -1 if it is impossible.

Example 1:

Input: street = "H..H"
Output: 2
Explanation:
We can put buckets at index 1 and index 2.
"H..H" -> "HBBH" ('B' denotes where a bucket is placed).
The house at index 0 has a bucket to its right, and the house at index 3 has a bucket to its left.
Thus, for every house, there is at least one bucket collecting rainwater from it.

Example 2:

Input: street = ".H.H."
Output: 1
Explanation:
We can put a bucket at index 2.
".H.H." -> ".HBH." ('B' denotes where a bucket is placed).
The house at index 1 has a bucket to its right, and the house at index 3 has a bucket to its left.
Thus, for every house, there is at least one bucket collecting rainwater from it.

Example 3:

Input: street = ".HHH."
Output: -1
Explanation:
There is no empty space to place a bucket to collect the rainwater from the house at index 2.
Thus, it is impossible to collect the rainwater from all the houses.

Example 4:

Input: street = "H"
Output: -1
Explanation:
There is no empty space to place a bucket.
Thus, it is impossible to collect the rainwater from the house.

Example 5:

Input: street = "."

Output: 0

Explanation:

There is no house to collect water from.

Thus, 0 buckets are needed.

Constraints:

1 <= street.length <= 10⁵
street[i] is either'H' or '.'.

Solution: Greedy

Try to put a bucket after a house if possible, otherwise put it before the house, or impossible.

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

C++

// Author: Huahua

class Solution {

public:

int minimumBuckets(string street) {

const int n = street.size();

int ans = 0;

for (int i = 0; i < n; ++i)

if (street[i] == 'H')

if (i - 1 >= 0 and street[i - 1] == 'B')

continue;

else if (i + 1 < n and street[i + 1] == '.')

street[i + 1] = 'B', ++ans;

else if (i - 1 >= 0 and street[i - 1] == '.')

street[i - 1] = 'B', ++ans;

else

return -1;

return ans;

}

};

Posts tagged as “medium”

花花酱 LeetCode 2090. K Radius Subarray Averages

Solution: Sliding Window

C++

花花酱 LeetCode 137. Single Number II

Solution: Bit by bit

C++

Related Problems

花花酱 LeetCode 114. Flatten Binary Tree to Linked List

Solution 1: Recursion

Python3

Python3

花花酱 LeetCode 109. Convert Sorted List to Binary Search Tree

Solution 1: Recursion w/ Fast + Slow Pointers

C++

花花酱 LeetCode 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses

Solution: Greedy

C++