Posts published in “Array”

花花酱 LeetCode 1822. Sign of the Product of an Array

By zxi on April 12, 2021

There is a function signFunc(x) that returns:

1 if x is positive.
-1 if x is negative.
0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

Example 1:

Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1

Example 2:

Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 3:

Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1

Constraints:

1 <= nums.length <= 1000
-100 <= nums[i] <= 100

Solution: Sign Only

No need to compute the product, only track the sign changes. Flip the sign when encounter a negative number, return 0 if there is any 0 in the array.

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

C++

// Author: Huahua

class Solution {

public:

int arraySign(vector<int>& nums) {

int sign = 1;

for (int x : nums) {

if (x == 0) return 0;

else if (x < 0) sign = -sign;

}

return sign;

}

};

花花酱 LeetCode 1800. Maximum Ascending Subarray Sum

By zxi on March 21, 2021

Given an array of positive integers nums, return the maximum possible sum of an ascending subarray in nums.

A subarray is defined as a contiguous sequence of numbers in an array.

A subarray [nums_l, nums_l+1, ..., nums_r-1, nums_r] is ascending if for all i where l <= i < r, nums_i< nums_i+1. Note that a subarray of size 1 is ascending.

Example 1:

Input: nums = [10,20,30,5,10,50]
Output: 65
Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.

Example 2:

Input: nums = [10,20,30,40,50]
Output: 150
Explanation: [10,20,30,40,50] is the ascending subarray with the maximum sum of 150.

Example 3:

Input: nums = [12,17,15,13,10,11,12]
Output: 33
Explanation: [10,11,12] is the ascending subarray with the maximum sum of 33.

Example 4:

Input: nums = [100,10,1]
Output: 100

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution: Running sum with resetting

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

Track the running sum and reset it to zero if nums[i] <= nums[i – 1]

C++

// Author: Huahua

class Solution {

public:

int maxAscendingSum(vector<int>& nums) {

int ans = 0;

for (int i = 0, s = 0; i < nums.size(); ++i) {

if (i && nums[i] <= nums[i - 1])

s = 0;

ans = max(ans, s += nums[i]);

}

return ans;

}

};

花花酱 LeetCode 1773. Count Items Matching a Rule

By zxi on February 27, 2021

You are given an array items, where each items[i] = [type_i, color_i, name_i] describes the type, color, and name of the i^th item. You are also given a rule represented by two strings, ruleKey and ruleValue.

The i^th item is said to match the rule if one of the following is true:

ruleKey == "type" and ruleValue == type_i.
ruleKey == "color" and ruleValue == color_i.
ruleKey == "name" and ruleValue == name_i.

Return the number of items that match the given rule.

Example 1:

Input: items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]], ruleKey = "color", ruleValue = "silver"
Output: 1
Explanation: There is only one item matching the given rule, which is ["computer","silver","lenovo"].

Example 2:

Input: items = [["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]], ruleKey = "type", ruleValue = "phone"
Output: 2
Explanation: There are only two items matching the given rule, which are ["phone","blue","pixel"] and ["phone","gold","iphone"]. Note that the item ["computer","silver","phone"] does not match.

Constraints:

1 <= items.length <= 10⁴
1 <= type_i.length, color_i.length, name_i.length, ruleValue.length <= 10
ruleKey is equal to either "type", "color", or "name".
All strings consist only of lowercase letters.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {

return count_if(begin(items), end(items), [&](const auto& item) {

return (ruleKey == "type" && item[0] == ruleValue

|| ruleKey == "color" && item[1] == ruleValue

|| ruleKey == "name" && item[2] == ruleValue);

});

}

};

花花酱 LeetCode 1764. Form Array by Concatenating Subarrays of Another Array

By zxi on February 20, 2021

You are given a 2D integer array groups of length n. You are also given an integer array nums.

You are asked if you can choose n disjoint subarrays from the array nums such that the i^th subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)^th subarray appears before the i^th subarray in nums (i.e. the subarrays must be in the same order as groups).

Return true if you can do this task, and false otherwise.

Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0^th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1^st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.

Example 2:

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].

Example 3:

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).

Constraints:

groups.length == n
1 <= n <= 10³
1 <= groups[i].length, sum(groups[i].length) <= 10³
1 <= nums.length <= 10³
-10⁷ <= groups[i][j], nums[k] <= 10⁷

Solution: Brute Force

Time complexity: O(n^2?)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {

const int n = nums.size();

int s = 0;

for (const auto& g : groups) {

bool found = false;

for (int i = s; i <= n - g.size(); ++i)

if (equal(begin(g), end(g), begin(nums) + i)) {

s = i + g.size();

found = true;

break;

}

if (!found) return false;

}

return true;

}

};

花花酱 LeetCode 1752. Check if Array Is Sorted and Rotated

By zxi on February 7, 2021

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

Example 1:

Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

Example 2:

Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.

Example 3:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Example 4:

Input: nums = [1,1,1]
Output: true
Explanation: [1,1,1] is the original sorted array.
You can rotate any number of positions to make nums.

Example 5:

Input: nums = [2,1]
Output: true
Explanation: [1,2] is the original sorted array.
You can rotate the array by x = 5 positions to begin on the element of value 2: [2,1].

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution: Counting and checking

Count how many turning points (nums[i] < nums[i – 1]) in the array. Return false if there are more than 1.
For the turning point r, (nums[r] < nums[r – 1), return true if both of the following conditions are satisfied:
1. nums[r – 1] is the largest number, e.g. nums[r – 1] >= nums[n – 1]
2. nums[r] is the smallest number, e.g. nums[r] <= nums[0]

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

C++

// Author: Huahua

class Solution {

public:

bool check(vector<int>& nums) {

int count = 0;

int r = -1;

for (size_t i = 1; i < nums.size(); ++i)

if (nums[i] < nums[i - 1]) {

++count;

r = i;

}

if (count == 0) return true;

if (count > 1) return false;

return nums[r] <= nums[0] && nums[r - 1] >= nums.back();

}

};