Posts tagged as “easy”

花花酱 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 1796. Second Largest Digit in a String

By zxi on March 20, 2021

Given an alphanumeric string s, return the second largest numerical digit that appears in s, or -1 if it does not exist.

An alphanumericstring is a string consisting of lowercase English letters and digits.

Example 1:

Input: s = "dfa12321afd"
Output: 2
Explanation: The digits that appear in s are [1, 2, 3]. The second largest digit is 2.

Example 2:

Input: s = "abc1111"
Output: -1
Explanation: The digits that appear in s are [1]. There is no second largest digit.

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int secondHighest(string s) {

vector<int> d(10);

for (char c : s)

if (c >= '0' && c <= '9')

d[c - '0'] = 1;

int order = 0;

for (int i = 9; i >= 0; --i)

if (d[i] && ++order == 2)

return i;

return -1;

}

};

花花酱 LeetCode 1790. Check if One String Swap Can Make Strings Equal

By zxi on March 13, 2021

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Example 4:

Input: s1 = "abcd", s2 = "dcba"
Output: false

Constraints:

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 and s2 consist of only lowercase English letters.

Solution: Remember two indices

There needs to be either 0 or 2 indices are different. Otherwise return false.
s1[idx1] == s2[idx2] and s1[idx2] == s2[idx1]

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

C++

// Author: Huahua

class Solution {

public:

bool areAlmostEqual(string s1, string s2) {

vector<int> idx;

for (int i = 0; i < s1.length() && idx.size() <= 2; ++i)

if (s1[i] != s2[i]) idx.push_back(i);

if (idx.size() == 0) return true;

if (idx.size() != 2) return false;

return s1[idx[0]] == s2[idx[1]] && s1[idx[1]] == s2[idx[0]];

}

};

花花酱 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);

});

}

};