Posts published in “Algorithms”

花花酱 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 2419. Longest Subarray With Maximum Bitwise AND

By zxi on September 26, 2022

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Solution: Find the largest number

a & b <= a
a & b <= b
if b > a, a & b < b, we choose to start a new sequence of “b” instead of continuing with “ab”

Basically, we find the largest number in the array and count the longest sequence of it. Note, there will be some tricky cases like.
b b b b a b
b a b b b b
We need to return 4 instead of 1.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

int ans = 0;

int best = 0;

for (int i = 0, l = 0; i < nums.size(); ++i) {

if (nums[i] > best) {

best = nums[i];

ans = l = 1;

} else if (nums[i] == best) {

ans = max(ans, ++l);

} else {

l = 0;

}

return ans;

}

};

花花酱 LeetCode 2418. Sort the People

By zxi on September 26, 2022

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the i^th person.

Return names sorted in descending order by the people’s heights.

Example 1:

Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.

Example 2:

Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]
Explanation: The first Bob is the tallest, followed by Alice and the second Bob.

Constraints:

n == names.length == heights.length
1 <= n <= 10³
1 <= names[i].length <= 20
1 <= heights[i] <= 10⁵
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Solution: Zip and sort

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

C++

// Author: Huahua

class Solution {

public:

vector<string> sortPeople(vector<string>& names, vector<int>& heights) {

vector<pair<int, string*>> data;

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

data.emplace_back(heights[i], &names[i]);

sort(rbegin(data), rend(data));

vector<string> ans(names.size());

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

ans[i].swap(*data[i].second);

return ans;

}

};

花花酱 LeetCode 2395. Find Subarrays With Equal Sum

By zxi on September 7, 2022

Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.

Return true if these subarrays exist, and false otherwise.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.

Example 2:

Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of size 2 have the same sum.

Example 3:

Input: nums = [0,0,0]
Output: true
Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. 
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.

Constraints:

2 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

Solution: Hashset

Use a hashset to track all the sums seen so far.

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

C++

// Author: Huahua

class Solution {

public:

bool findSubarrays(vector<int>& nums) {

unordered_set<int> s;

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

if (!s.emplace(nums[i] + nums[i - 1]).second) return true;

return false;

}

};