Posts tagged as “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 1779. Find Nearest Point That Has the Same X or Y Coordinate

By zxi on March 6, 2021

You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where each points[i] = [a_i, b_i] represents that a point exists at (a_i, b_i). A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.

Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.

The Manhattan distance between two points (x₁, y₁) and (x₂, y₂) is abs(x₁ - x₂) + abs(y₁ - y₂).

Example 1:

Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output: 2
Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.

Example 2:

Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The answer is allowed to be on the same location as your current location.

Example 3:

Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.

Constraints:

1 <= points.length <= 10⁴
points[i].length == 2
1 <= x, y, a_i, b_i <= 10⁴

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int nearestValidPoint(int x, int y, vector<vector<int>>& points) {

int min_dist = INT_MAX;

int ans = -1;

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

const int dx = abs(points[i][0] - x);

const int dy = abs(points[i][1] - y);

if (dx * dy == 0 && dx + dy < min_dist) {

min_dist = dx + dy;

ans = 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;

}

};