Huahua’s Tech Road

花花酱 LeetCode 2476. Closest Nodes Queries in a Binary Search Tree

By zxi on November 21, 2022

You are given the root of a binary search tree and an array queries of size n consisting of positive integers.

Find a 2D array answer of size n where answer[i] = [min_i, max_i]:

min_i is the largest value in the tree that is smaller than or equal to queries[i]. If a such value does not exist, add -1 instead.
max_i is the smallest value in the tree that is greater than or equal to queries[i]. If a such value does not exist, add -1 instead.

Return the array answer.

Example 1:

Input: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
Output: [[2,2],[4,6],[15,-1]]
Explanation: We answer the queries in the following way:
- The largest number that is smaller or equal than 2 in the tree is 2, and the smallest number that is greater or equal than 2 is still 2. So the answer for the first query is [2,2].
- The largest number that is smaller or equal than 5 in the tree is 4, and the smallest number that is greater or equal than 5 is 6. So the answer for the second query is [4,6].
- The largest number that is smaller or equal than 16 in the tree is 15, and the smallest number that is greater or equal than 16 does not exist. So the answer for the third query is [15,-1].

Example 2:

Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]
Explanation: The largest number that is smaller or equal to 3 in the tree does not exist, and the smallest number that is greater or equal to 3 is 4. So the answer for the query is [-1,4].

Constraints:

The number of nodes in the tree is in the range [2, 10⁵].
1 <= Node.val <= 10⁶
n == queries.length
1 <= n <= 10⁵
1 <= queries[i] <= 10⁶

Solution: Convert to sorted array

Since we don’t know whether the tree is balanced or not, the safest and easiest way is to convert the tree into a sorted array using inorder traversal. Or just any traversal and sort the array later on.

Once we have a sorted array, we can use lower_bound / upper_bound to query.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {

vector<int> vals;

function<void(TreeNode*)> inorder = [&](TreeNode* root) {

if (!root) return;

inorder(root->left);

vals.push_back(root->val);

inorder(root->right);

};

inorder(root);

vector<vector<int>> ans;

for (const int q : queries) {

vector<int> cur{-1, -1};

auto lit = upper_bound(begin(vals), end(vals), q);

if (lit != begin(vals))

cur[0] = *(prev(lit));

auto rit = lower_bound(begin(vals), end(vals), q);

if (rit != end(vals))

cur[1] = *rit;

ans.push_back(std::move(cur));

}

return ans;

}

};

One binary search per query.

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {

vector<int> vals;

function<void(TreeNode*)> inorder = [&](TreeNode* root) {

if (!root) return;

inorder(root->left);

if (vals.empty() || root->val > vals.back()) vals.push_back(root->val);

inorder(root->right);

};

inorder(root);

vector<vector<int>> ans;

for (const int q : queries) {

vector<int> cur{-1, -1};

auto it = lower_bound(begin(vals), end(vals), q);

if (it != end(vals) && *it == q)

cur[0] = cur[1] = q;

else {

if (it != begin(vals)) cur[0] = *prev(it);

if (it != end(vals)) cur[1] = *it;

}

ans.push_back(std::move(cur));

}

return ans;

}

};

花花酱 LeetCode 2475. Number of Unequal Triplets in Array

By zxi on November 21, 2022

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) that meet the following conditions:

0 <= i < j < k < nums.length
nums[i], nums[j], and nums[k] are pairwise distinct.
- In other words, nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].

Return the number of triplets that meet the conditions.

Example 1:

Input: nums = [4,4,2,4,3]
Output: 3
Explanation: The following triplets meet the conditions:
- (0, 2, 4) because 4 != 2 != 3
- (1, 2, 4) because 4 != 2 != 3
- (2, 3, 4) because 2 != 4 != 3
Since there are 3 triplets, we return 3.
Note that (2, 0, 4) is not a valid triplet because 2 > 0.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: No triplets meet the conditions so we return 0.

Constraints:

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

Solution 1: Brute Force

Enumerate i, j, k.

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

C++

// Author: Huahua

class Solution {

public:

int unequalTriplets(vector<int>& nums) {

int ans = 0;

const int n = nums.size();

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

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

for (int k = j + 1; k < n; ++k)

if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k])

++ans;

return ans;

}

};

花花酱 LeetCode 2452. Words Within Two Edits of Dictionary

By zxi on October 31, 2022

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words from queries, that match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].

Example 2:

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

Constraints:

1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
All queries[i] and dictionary[j] are composed of lowercase English letters.

Solution: Hamming distance + Brute Force

For each query word q, check the hamming distance between it and all words in the dictionary.

Time complexity: O(|q|*|d|*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {

const int n = queries[0].size();

auto check = [&](string_view q) {

for (const string& w : dictionary) {

int dist = 0;

for (int i = 0; i < n && dist <= 3; ++i)

dist += q[i] != w[i];

if (dist <= 2) return true;

}

return false;

};

vector<string> ans;

for (const string& q : queries)

if (check(q)) ans.push_back(q);

return ans;

}

};

花花酱 LeetCode 2451. Odd String Difference

By zxi on October 31, 2022

You are given an array of equal-length strings words. Assume that the length of each string is n.

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] - words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0, 'b' is 1, and 'z' is 25.

For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string in words that has different difference integer array.

Example 1:

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation: 
- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
- The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
- The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. 
The odd array out is [1, 1], so we return the corresponding string, "abc".

Example 2:

Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].

Constraints:

3 <= words.length <= 100
n == words[i].length
2 <= n <= 20
words[i] consists of lowercase English letters.

Solution: Comparing with first string.

Let us pick words[0] as a reference for comparison, assuming it’s valid. If we only found one instance say words[i], that is different than words[0], we know that words[i] is bad, otherwise we should see m – 1 different words which means words[0] itself is bad.

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

C++

// Author: Huahua

class Solution {

public:

string oddString(vector<string>& words) {

const int m = words.size();

const int n = words[0].size();

int count = 0;

int bad = 0;

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

for (int j = 1; j < n; ++j) {

if (words[i][j] - words[i][j - 1]

!= words[0][j] - words[0][j - 1]) {

++count;

bad = i;

break;

}

return words[count == 1 ? bad : 0];

}

};

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

By zxi on October 15, 2022

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints:

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
nums[i] != 0

Solution 1: Hashtable

We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

unordered_set<int> s;

int ans = -1;

for (int x : nums) {

if (abs(x) > ans && s.count(-x))

ans = abs(x);

s.insert(x);

}

return ans;

}

};

Solution 2: Sorting

Sort the array by abs(x) in descending order.

[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]

Check whether arr[i] = -arr[i-1].

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

sort(begin(nums), end(nums), [](int a, int b){

return abs(a) == abs(b) ? a < b : abs(a) > abs(b);

});

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

if (nums[i] == -nums[i - 1]) return nums[i];

return -1;

}

};

Solution 3: Two Pointers

Sort the array.

Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum < 0, ++i else –j.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

sort(begin(nums), end(nums));

int ans = -1;

for (int i = 0, j = nums.size() - 1; i < j; ) {

const int s = nums[i] + nums[j];

if (s == 0) {

ans = max(ans, nums[j]);

++i, --j;

} else if (s < 0) {

++i;

} else {

--j;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2476. Closest Nodes Queries in a Binary Search Tree

Solution: Convert to sorted array

C++

C++

花花酱 LeetCode 2475. Number of Unequal Triplets in Array

Solution 1: Brute Force

C++

花花酱 LeetCode 2452. Words Within Two Edits of Dictionary

Solution: Hamming distance + Brute Force

C++

花花酱 LeetCode 2451. Odd String Difference

Solution: Comparing with first string.

C++

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

Solution 1: Hashtable

C++

Solution 2: Sorting

C++

Solution 3: Two Pointers

C++