Posts tagged as “array”

花花酱 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 1748. Sum of Unique Elements

By zxi on February 6, 2021

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.

Return the sum of all the unique elements of nums.

Example 1:

Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Example 3:

Input: nums = [1,2,3,4,5]
Output: 15
Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints:

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

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int sumOfUnique(vector<int>& nums) {

vector<int> seen(101);

int ans = 0;

for (int x : nums)

++seen[x];

for (int x : nums)

if (seen[x] == 1) ans += x;

return ans;

}

};

花花酱 LeetCode 1743. Restore the Array From Adjacent Pairs

By zxi on January 30, 2021

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [u_i, v_i] indicates that the elements u_i and v_i are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]

Constraints:

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 10⁵
-10⁵ <= nums[i], u_i, v_i <= 10⁵
There exists some nums that has adjacentPairs as its pairs.

Solution: Hashtable

Reverse thinking! For a given input array, e.g.
[1, 2, 3, 4, 5]
it’s adjacent pairs are [1,2] , [2,3], [3,4], [4,5]
all numbers appeared exactly twice except 1 and 5, since they are on the boundary.
We just need to find the head or tail of the input array, and construct the rest of the array in order.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {

const int n = adjacentPairs.size() + 1;

unordered_map<int, vector<int>> g;

for (const auto& p : adjacentPairs) {

g[p[0]].push_back(p[1]);

g[p[1]].push_back(p[0]);

}

vector<int> ans(n);

for (const auto& [u, vs] : g)

if (vs.size() == 1) {

ans[0] = u;

ans[1] = vs[0];

break;

}

for (int i = 2; i < n; ++i) {

const auto& vs = g[ans[i - 1]];

ans[i] = vs[0] == ans[i - 2] ? vs[1] : vs[0];

}

return ans;

}

};

花花酱 LeetCode1732. Find the Highest Altitude

By zxi on January 23, 2021

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

Solution: Running Max

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

C++

// Author: Huahua

class Solution {

public:

int largestAltitude(vector<int>& gain) {

int ans = 0;

int cur = 0;

for (int diff : gain)

ans = max(ans, cur += diff);

return ans;

}

};