Posts tagged as “hard”

花花酱 LeetCode 2088. Count Fertile Pyramids in a Land

By zxi on November 27, 2021

A farmer has a rectangular grid of land with m rows and n columns that can be divided into unit cells. Each cell is either fertile (represented by a 1) or barren (represented by a 0). All cells outside the grid are considered barren.

A pyramidal plot of land can be defined as a set of cells with the following criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of a pyramid is the topmost cell of the pyramid. The height of a pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r <= i <= r + h - 1 and c - (i - r) <= j <= c + (i - r).

An inverse pyramidal plot of land can be defined as a set of cells with similar criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of an inverse pyramid is the bottommost cell of the inverse pyramid. The height of an inverse pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r - h + 1 <= i <= r and c - (r - i) <= j <= c + (r - i).

Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.

Given a 0-indexed m x n binary matrix grid representing the farmland, return the total number of pyramidal and inverse pyramidal plots that can be found in grid.

Example 1:

Input: grid = [[0,1,1,0],[1,1,1,1]]
Output: 2
Explanation:
The 2 possible pyramidal plots are shown in blue and red respectively.
There are no inverse pyramidal plots in this grid. 
Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.

Example 2:

Input: grid = [[1,1,1],[1,1,1]]
Output: 2
Explanation:
The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red. 
Hence the total number of plots is 1 + 1 = 2.

Example 3:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 0
Explanation:
There are no pyramidal or inverse pyramidal plots in the grid.

Example 4:

Input: grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
Output: 13
Explanation:
There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.
There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.
The total number of plots is 7 + 6 = 13.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
grid[i][j] is either 0 or 1.

Solution: DP

Let dp[i][j] be the height+1 of a Pyramid tops at i, j
dp[i][j] = min(dp[i+d][j – 1], dp[i + d][j + 1]) + 1 if dp[i-1][j] else grid[i][j]

Time complexity: O(mn)
Space complexity: O(mn)

Python

# Author: Huahua

class Solution:

def countPyramids(self, grid: List[List[int]]) -> int:

m = len(grid)

n = len(grid[0])

ans = 0

@cache

def dp(i: int, j: int, d: int) -> int:

if grid[i][j] and 0 <= i + d < m and 0 < j < n - 1 and grid[i + d][j]:

return min(dp(i + d, j - 1, d), dp(i + d, j + 1, d)) + 1

return grid[i][j]

for i, j in product(range(m), range(n)):

ans += max(0, dp(i, j, 1) - 1)

ans += max(0, dp(i, j, -1) - 1)

return ans

花花酱 LeetCode 65. Valid Number

By zxi on November 26, 2021

A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One of the following formats:
1. One or more digits, followed by a dot '.'.
2. One or more digits, followed by a dot '.', followed by one or more digits.
3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = "0"
Output: true

Example 2:

Input: s = "e"
Output: false

Example 3:

Input: s = "."
Output: false

Example 4:

Input: s = ".1"
Output: true

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Solution: Rule checking

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

C++

// Author: Huahua

class Solution {

public:

bool isNumber(string s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != ' ') {

s = s.substr(i);

break;

}

while (!s.empty() && s.back() == ' ') s.pop_back();

bool dot = false;

bool e = false;

bool digit = false;

for (int i = 0; i < s.length(); ++i) {

s[i] = tolower(s[i]);

if (isdigit(s[i])) {

digit = true;

} else if (s[i] == '.') {

if (e || dot) return false;

dot = true;

} else if (s[i] == 'e') {

if (e || !digit) return false;

e = true;

digit = false;

} else if (s[i] == '-' || s[i] == '+') {

if (i != 0 && s[i - 1] != 'e')

return false;

} else {

return false;

}

return digit;

}

};

花花酱 LeetCode 41. First Missing Positive

By zxi on November 26, 2021

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

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

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

Constraints:

1 <= nums.length <= 5 * 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Solution: Marking

First pass, marking nums[i] to INT_MAX if nums[i] <= 0
Second pass, use a negative number to mark the presence of a number x at nums[x – 1]
Third pass, the first positive number is the missing index i, return i +1
If not found return n + 1.

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

C++

// Author: Huahua

class Solution {

public:

int firstMissingPositive(vector<int>& nums) {

const int n = nums.size();

for (int& x : nums)

if (x <= 0) x = INT_MAX;

for (int x : nums) {

x = abs(x);

if (x >= 1 && x <= n && nums[x - 1] > 0)

nums[x - 1] *= -1;

}

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

if (nums[i] > 0)

return i + 1;

return n + 1;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on November 26, 2021

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

1 <= s.length <= 10⁴
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

Solution: Hashtable + Brute Force

Try every index and use a hashtable to check coverage.

Time complexity: O(n*m*l)
Space complexity: O(m*l)

C++

// Author: Huahua

class Solution {

public:

vector<int> findSubstring(string_view s, vector<string>& words) {

const int n = s.length();

const int m = words.size();

const int l = words[0].size();

if (m * l > n) return {};

unordered_map<string_view, int> freq;

for (const string& word : words) ++freq[word];

vector<int> ans;

for (int i = 0; i <= n - m * l; ++i) {

unordered_map<string_view, int> seen;

int count = 0;

for (int k = 0; k < m; ++k) {

string_view t = s.substr(i + k * l, l);

auto it = freq.find(t);

if (it == end(freq)) break;

if (++seen[t] > it->second) break;

++count;

}

if (count == m) ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode 2009. Minimum Number of Operations to Make Array Continuous

By zxi on November 26, 2021

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

All elements in nums are unique.
The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make numscontinuous.

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Solution: Sliding Window

Remove duplicates and sort the numbers.
Try using nums[i] as the min number of the final array.
window [i, j), max – min < n, then change the rest of array to fit into or append after the window, which takes n – (j – i) steps.
e.g. input = [10, 3, 1, 4, 5, 6, 6, 6, 11, 15] => sorted + unique => [1, 3, 4, 5, 6, 10, 11, 15]
n = 10, window = [3, 4, 5, 6, 10, 11], max = 11, min = 3, max – min = 8 < 10
Final array = [3, 4, 5, 6, 1->7, 6₂->8, 6₃->9, 10, 11, 15->12]
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& A) {

const int n = A.size();

sort(begin(A), end(A));

A.erase(unique(begin(A), end(A)), end(A));

int ans = INT_MAX;

for (int i = 0, j = 0, m = A.size(); i < m; ++i) {

while (j < m && A[j] < A[i] + n) ++j;

ans = min(ans, n - (j - i));

}

return ans;

}

};