Posts tagged as “medium”

花花酱 LeetCode 2829. Determine the Minimum Sum of a k-avoiding Array

By zxi on August 26, 2023

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.

Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.

Constraints:

1 <= n, k <= 50

Solution 1: Greedy + HashTable

Always choose the smallest possible number starting from 1.

Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSum(int n, int k) {

int sum = 0;

unordered_set<int> s;

for (int i = 1; s.size() != n; ++i) {

if (s.count(k - i)) continue;

sum += i;

s.insert(i);

}

return sum;

}

};

花花酱 LeetCode 2825. Make String a Subsequence Using Cyclic Increments

By zxi on August 23, 2023

You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.

Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input: str1 = "abc", str2 = "ad"
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become 'd'. 
Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.

Example 2:

Input: str1 = "zc", str2 = "ad"
Output: true
Explanation: Select indices 0 and 1 in str1. 
Increment str1[0] to become 'a'. 
Increment str1[1] to become 'd'. 
Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.

Example 3:

Input: str1 = "ab", str2 = "d"
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. 
Therefore, false is returned.

Constraints:

1 <= str1.length <= 10⁵
1 <= str2.length <= 10⁵
str1 and str2 consist of only lowercase English letters.

Solution: Two pointers

s1[i] and s2[j] can match if
s1[i] == s2[j] or inc(s1[i]) == s2[j]

If matched: ++i; ++j else ++i.

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

C++

class Solution {

public:

bool canMakeSubsequence(string_view s1, string_view s2) {

for (int i = 0, j = 0, n = s1.size(), m = s2.size(); i < n; ++i)

if (s1[i] == s2[j] || (s1[i] - 'a' + 1) % 26 == s2[j] - 'a')

if (++j == m) return true;

return false;

}

};

Iterator version

C++

class Solution {

public:

bool canMakeSubsequence(string_view s1, string_view s2) {

for (auto i = begin(s1), j = begin(s2); i != end(s1); ++i)

if (*i == *j || (*i - 'a' + 1) % 26 == *j - 'a')

if (++j == end(s2)) return true;

return false;

}

};

花花酱 LeetCode 2771. Longest Non-decreasing Subarray From Two Arrays

By zxi on July 15, 2023

You are given two 0-indexed integer arrays nums1 and nums2 of length n.

Let’s define another 0-indexed integer array, nums3, of length n. For each index i in the range [0, n - 1], you can assign either nums1[i] or nums2[i] to nums3[i].

Your task is to maximize the length of the longest non-decreasing subarray in nums3 by choosing its values optimally.

Return an integer representing the length of the longest non-decreasing subarray in nums3.

Note: A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums1 = [2,3,1], nums2 = [1,2,1]
Output: 2
Explanation: One way to construct nums3 is: 
nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]. 
The subarray starting from index 0 and ending at index 1, [2,2], forms a non-decreasing subarray of length 2. 
We can show that 2 is the maximum achievable length.

Example 2:

Input: nums1 = [1,3,2,1], nums2 = [2,2,3,4]
Output: 4
Explanation: One way to construct nums3 is: 
nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]. 
The entire array forms a non-decreasing subarray of length 4, making it the maximum achievable length.

Example 3:

Input: nums1 = [1,1], nums2 = [2,2]
Output: 2
Explanation: One way to construct nums3 is: 
nums3 = [nums1[0], nums1[1]] => [1,1]. 
The entire array forms a non-decreasing subarray of length 2, making it the maximum achievable length.

Constraints:

1 <= nums1.length == nums2.length == n <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁹

Solution: DP

Let dp1(i), dp2(i) denote the length of the Longest Non-decreasing Subarray ends with nums1[i] and nums2[i] respectively.

init: dp1(0) = dp2(0) = 1

dp1(i) = max(dp1(i – 1) + 1 if nums1[i] >= nums1[i – 1] else 1, dp2(i – 1) + 1 if nums1[i] >= nums2[i – 1] else 1)
dp2(i) = max(dp1(i – 1) + 1 if nums2[i] >= nums1[i – 1] else 1, dp2(i – 1) + 1 if nums2[i] >= nums2[i – 1] else 1)

ans = max(dp1, dp2)

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

Python3

# Author: Huahua

class Solution:

def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:

n = len(nums1)

nums = [nums1, nums2]

@cache

def dp(i: int, j: int):

if i == 0: return 1

ans = 1

for k in range(2):

if nums[j][i] >= nums[k][i - 1]:

ans = max(ans, dp(i - 1, k) + 1)

return ans

return max(max(dp(i, 0), dp(i, 1)) for i in range(n))

C++

// Author: Huahua

class Solution {

public:

int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {

int ans = 1;

for (int i = 1, dp1 = 1, dp2 = 1; i < nums1.size(); ++i) {

int t1 = max(nums1[i] >= nums1[i - 1] ? dp1 + 1 : 1,

nums1[i] >= nums2[i - 1] ? dp2 + 1 : 1);

int t2 = max(nums2[i] >= nums1[i - 1] ? dp1 + 1 : 1,

nums2[i] >= nums2[i - 1] ? dp2 + 1 : 1);

dp1 = t1;

dp2 = t2;

ans = max({ans, dp1, dp2});

}

return ans;

}

};

花花酱 LeetCode 2770. Maximum Number of Jumps to Reach the Last Index

By zxi on July 11, 2023

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

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target

Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

Example 1:

Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3.

Example 2:

Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5.

Example 3:

Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.

Constraints:

2 <= nums.length == n <= 1000
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Solution: DP

Let dp(i) denotes the maximum jumps from index i to index n-1.

For each index i, try jumping to all possible index j.

dp(i) = max(1 + dp(j)) if j > i and abs(nums[j] – nums[i) <= target else -1

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

Python3

# Author: Huahua

class Solution:

def maximumJumps(self, nums: List[int], target: int) -> int:

n = len(nums)

@cache

def dp(i):

if i == n - 1: return 0

ans = -1

for j in range(i + 1, n):

if abs(nums[j] - nums[i]) <= target and dp(j) != -1:

ans = max(ans, 1 + dp(j))

return ans

return dp(0)

花花酱 LeetCode 2662. Minimum Cost of a Path With Special Roads

By zxi on April 30, 2023

You are given an array start where start = [startX, startY] represents your initial position (startX, startY) in a 2D space. You are also given the array target where target = [targetX, targetY] represents your target position (targetX, targetY).

The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|.

There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1_i, y1_i, x2_i, y2_i, cost_i] indicates that the i^th special road can take you from (x1_i, y1_i) to (x2_i, y2_i) with a cost equal to cost_i. You can use each special road any number of times.

Return the minimum cost required to go from (startX, startY) to (targetX, targetY).

Example 1:

Input: start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
Output: 5
Explanation: The optimal path from (1,1) to (4,5) is the following:
- (1,1) -> (1,2). This move has a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) -> (3,3). This move uses the first special edge, the cost is 2.
- (3,3) -> (3,4). This move has a cost of |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5). This move uses the second special edge, the cost is 1.
So the total cost is 1 + 2 + 1 + 1 = 5.
It can be shown that we cannot achieve a smaller total cost than 5.

Example 2:

Input: start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
Output: 7
Explanation: It is optimal to not use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.

Constraints:

start.length == target.length == 2
1 <= startX <= targetX <= 10⁵
1 <= startY <= targetY <= 10⁵
1 <= specialRoads.length <= 200
specialRoads[i].length == 5
startX <= x1_i, x2_i <= targetX
startY <= y1_i, y2_i <= targetY
1 <= cost_i <= 10⁵

Solution: Dijkstra

Create a node for each point in special edges as well as start and target.
Add edges for special roads (note it’s directional)
Add edges for each pair of node with default cost, i.e. |x1-x2| + |y1-y2|
Run Dijkstra’s algorithm

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

C++

// Author: Huahua

class Solution {

public:

int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {

unordered_map<long, int> ids;

vector<pair<int, int>> pos;

auto getId = [&](int x, int y) {

const auto key = ((unsigned long)x << 32) | y;

if (ids.count(key)) return ids[key];

const int id = ids.size();

ids[key] = id;

pos.emplace_back(x, y);

return id;

};

const int s = getId(start[0], start[1]);

const int t = getId(target[0], target[1]);

vector<vector<pair<int, int>>> g;

auto addEdge = [&](int x1, int y1, int x2, int y2, int c = INT_MAX) {

int n1 = getId(x1, y1);

int n2 = getId(x2, y2);

if (n1 == n2) return;

while (g.size() <= max(n1, n2)) g.push_back({});

int cost = min(c, abs(x1 - x2) + abs(y1 - y2));

g[n1].emplace_back(cost, n2);

// directional for special edge

if (c == INT_MAX) g[n2].emplace_back(cost, n1);

};

for (const auto& r : specialRoads)

addEdge(r[0], r[1], r[2], r[3], r[4]);

for (int i = 0; i < pos.size(); ++i)

for (int j = i + 1; j < pos.size(); ++j)

addEdge(pos[i].first, pos[i].second,

pos[j].first, pos[j].second);

vector<int> dist(ids.size(), INT_MAX);

dist[s] = 0;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

q.emplace(0, s);

while (!q.empty()) {

auto [d, u] = q.top(); q.pop();

if (d > dist[u]) continue;

if (u == t) return d;

for (auto [c, v] : g[u])

if (d + c < dist[v])

q.emplace(dist[v] = d + c, v);

}

return -1;

}

};