Posts tagged as “easy”

花花酱 LeetCode 119. Pascal’s Triangle II

By zxi on November 27, 2021

Given an integer rowIndex, return the rowIndex^th (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints:

0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Solution: Remember last row

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

C++

# Author: huahua

class Solution {

public:

vector<int> getRow(int rowIndex) {

vector<int> ans(1, 1);

for (int i = 2; i <= rowIndex + 1; ++i) {

vector<int> tmp(i, 1);

for (int j = 1; j < i - 1; ++j)

tmp[j] = ans[j] + ans[j - 1];

swap(ans, tmp);

}

return ans;

}

};

花花酱 LeetCode 118. Pascal’s Triangle

By zxi on November 27, 2021

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> ans(numRows);

for (int i = 0; i < numRows;++i) {

ans[i].resize(i + 1);

ans[i][0] = ans[i][i] = 1;

for (int j = 1; j < i; ++j)

ans[i][j] = ans[i-1][j] + ans[i-1][j-1];

}

return ans;

}

花花酱 LeetCode 2085. Count Common Words With One Occurrence

By zxi on November 27, 2021

Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

Example 1:

Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
Output: 2
Explanation:
- "leetcode" appears exactly once in each of the two arrays. We count this string.
- "amazing" appears exactly once in each of the two arrays. We count this string.
- "is" appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
- "as" appears once in words1, but does not appear in words2. We do not count this string.
Thus, there are 2 strings that appear exactly once in each of the two arrays.

Example 2:

Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
Output: 0
Explanation: There are no strings that appear in each of the two arrays.

Example 3:

Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Explanation: The only string that appears exactly once in each of the two arrays is "ab".

Constraints:

1 <= words1.length, words2.length <= 1000
1 <= words1[i].length, words2[j].length <= 30
words1[i] and words2[j] consists only of lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int countWords(vector<string>& words1, vector<string>& words2) {

unordered_map<string, int> c1;

unordered_map<string, int> c2;

for (const string& w : words1) ++c1[w];

for (const string& w : words2) ++c2[w];

int ans = 0;

for (const auto& [w, c] : c1)

if (c == 1 && c2[w] == 1) ++ans;

return ans;

}

};

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

By zxi on November 25, 2021

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

Example 2:

Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k

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

C++

// Author: Huahua

class Solution {

public:

int countKDifference(vector<int>& nums, int k) {

unordered_map<int, int> m;

int ans = 0;

for (int x : nums) {

ans += m[x - k];

ans += m[x + k];

++m[x];

}

return ans;

}

};

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

By zxi on November 20, 2021

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the i^th house.

Return the maximum distance between two houses with different colors.

The distance between the i^th and j^th houses is abs(i - j), where abs(x) is the absolute value of x.

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation: The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

Constraints:

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100
Test data are generated such that at least two houses have different colors.

Solution 1: Brute Force

Try all pairs.
Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

const int n = colors.size();

for (int d = n - 1; d > 0; --d)

for (int i = 0; i + d < n; ++i)

if (colors[i] != colors[i + d])

return d;

return 0;

}

};

Solution 2: Greedy / One pass

First house or last house must be involved in the ans.

Scan the house and check with first and last house.

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

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

int ans = 0;

const int n = colors.size();

for (int i = 0; i < n; ++i)

ans = max({ans,

i * (colors[i] != colors[0]),

(n - i - 1) * (colors[i] != colors[n - 1])});

return ans;

}

};

Posts tagged as “easy”

花花酱 LeetCode 119. Pascal’s Triangle II

Solution: Remember last row

C++

Related Problems

花花酱 LeetCode 118. Pascal’s Triangle

Solution: Simulation

C++

Related Problems

花花酱 LeetCode 2085. Count Common Words With One Occurrence

Solution: Hashtable

C++

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k

C++

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

Solution 1: Brute Force

C++

Solution 2: Greedy / One pass

C++

Posts tagged as “easy”

花花酱 LeetCode 119. Pascal’s Triangle II

Solution: Remember last row

C++

Related Problems

花花酱 LeetCode 118. Pascal’s Triangle

Solution: Simulation

C++

Related Problems

花花酱 LeetCode 2085. Count Common Words With One Occurrence

Solution: Hashtable

C++

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

Solution: Hashtable|y – x| = ky = x + k or y = x – k

C++

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

Solution 1: Brute Force

C++

Solution 2: Greedy / One pass

C++

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k