Huahua’s Tech Road

花花酱 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 2769. Find the Maximum Achievable Number

By zxi on July 11, 2023

You are given two integers, num and t.

An integer x is called achievable if it can become equal to num after applying the following operation no more than t times:

Increase or decrease x by 1, and simultaneously increase or decrease num by 1.

Return the maximum possible achievable number. It can be proven that there exists at least one achievable number.

Example 1:

Input: num = 4, t = 1
Output: 6
Explanation: The maximum achievable number is x = 6; it can become equal to num after performing this operation:
1- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5. 
It can be proven that there is no achievable number larger than 6.

Example 2:

Input: num = 3, t = 2
Output: 7
Explanation: The maximum achievable number is x = 7; after performing these operations, x will equal num: 
1- Decrease x by 1, and increase num by 1. Now, x = 6 and num = 4.
2- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
It can be proven that there is no achievable number larger than 7.

Constraints:

1 <= num, t <= 50

Solution: Greedy

Always decrease x and always increase num, the max achievable number x = num + t * 2

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

C++

// Author: Huahua

class Solution {

public:

int theMaximumAchievableX(int num, int t) {

return num + t * 2;

}

};

花花酱 LeetCode 2666. Allow One Function Call

By zxi on May 7, 2023

Given a function fn, return a new function that is identical to the original function except that it ensures fn is called at most once.

The first time the returned function is called, it should return the same result as fn.
Every subsequent time it is called, it should return undefined.

Example 1:

Input: fn = (a,b,c) => (a + b + c), calls = [[1,2,3],[2,3,6]]
Output: [{"calls":1,"value":6}]
Explanation:
const onceFn = once(fn);
onceFn(1, 2, 3); // 6
onceFn(2, 3, 6); // undefined, fn was not called

Example 2:

Input: fn = (a,b,c) => (a * b * c), calls = [[5,7,4],[2,3,6],[4,6,8]]
Output: [{"calls":1,"value":140}]
Explanation:
const onceFn = once(fn);
onceFn(5, 7, 4); // 140
onceFn(2, 3, 6); // undefined, fn was not called
onceFn(4, 6, 8); // undefined, fn was not called

Constraints:

1 <= calls.length <= 10
1 <= calls[i].length <= 100
2 <= JSON.stringify(calls).length <= 1000

Solution:

JavaScript

// Author: Huahua

/**

* @param {Function} fn

* @return {Function}

var once = function(fn) {

this.called = false;

return function(...args){

if (this.called === false) {

this.called = true;

return fn(...args);

} else {

return undefined;

}

};

花花酱 LeetCode 2667. Create Hello World Function

By zxi on May 7, 2023

Write a function createHelloWorld. It should return a new function that always returns "Hello World".

Example 1:

Input: args = []
Output: "Hello World"
Explanation:
const f = createHelloWorld();
f(); // "Hello World"
The function returned by createHelloWorld should always return "Hello World".

Example 2:

Input: args = [{},null,42]
Output: "Hello World"
Explanation:
const f = createHelloWorld();
f({}, null, 42); // "Hello World"
Any arguments could be passed to the function but it should still always return "Hello World".

Constraints:

0 <= args.length <= 10

Solution:

JavaScript

// Author: Huahua

/**

* @return {Function}

var createHelloWorld = function() {

return function(...args) {

return "Hello World";

}

};

Huahua's Tech Road

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

Solution: DP

Python3

C++

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

Solution: DP

Python3

花花酱 LeetCode 2769. Find the Maximum Achievable Number

Solution: Greedy

C++

花花酱 LeetCode 2666. Allow One Function Call

JavaScript

花花酱 LeetCode 2667. Create Hello World Function

JavaScript