Posts published in “Algorithms”

花花酱 LeetCode 2148. Count Elements With Strictly Smaller and Greater Elements

By zxi on February 4, 2022

Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element appear in nums.

Example 1:

Input: nums = [11,7,2,15]
Output: 2
Explanation: The element 7 has the element 2 strictly smaller than it and the element 11 strictly greater than it.
Element 11 has element 7 strictly smaller than it and element 15 strictly greater than it.
In total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.

Example 2:

Input: nums = [-3,3,3,90]
Output: 2
Explanation: The element 3 has the element -3 strictly smaller than it and the element 90 strictly greater than it.
Since there are two elements with the value 3, in total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.

Constraints:

1 <= nums.length <= 100
-10⁵ <= nums[i] <= 10⁵

Solution: Min / Max elements

Find min and max of the array, count elements other than those two.

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

C++

// Author: Huahua

class Solution {

public:

int countElements(vector<int>& nums) {

auto [it1, it2] = minmax_element(begin(nums), end(nums));

return count_if(begin(nums), end(nums), [lo=*it1, hi=*it2](int x) {

return x != lo && x != hi;

});

}

};

花花酱 LeetCode 2141. Maximum Running Time of N Computers

By zxi on January 30, 2022

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the i^th battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the maximum number of minutes you can run all the n computers simultaneously.

Example 1:

Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation: 
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.

Example 2:

Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation: 
Initially, insert battery 0 into the first computer and battery 2 into the second computer. 
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. 
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.

Constraints:

1 <= n <= batteries.length <= 10⁵
1 <= batteries[i] <= 10⁹

Solution: Binary Search

Find the smallest L that we can not run, ans = L – 1.

For a guessing m, we check the total battery powers T = sum(min(m, batteries[i])), if T >= m * n, it means there is a way (doesn’t need to figure out how) to run n computers for m minutes by fully unitize those batteries.

Proof: If T >= m*n holds, there are two cases:

There are only n batteries, can not swap, but each of them has power >= m.
At least one of the batteries have power less than m, but there are more than n batteries and total power is sufficient, we can swap them with others.

Time complexity: O(Slogn) where S = sum(batteries)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long maxRunTime(int n, vector<int>& batteries) {

long long l = 0;

long long r = accumulate(begin(batteries), end(batteries), 0LL) + 1;

while (l < r) {

long long m = l + (r - l) / 2;

long long t = 0;

for (long long b : batteries)

t += min(m, b);

if (m * n > t) // smallest m that does not fit.

r = m;

else

l = m + 1;

}

return l - 1; // greatest m that fits.

}

};

花花酱 LeetCode 1995. Count Special Quadruplets

By zxi on December 31, 2021

Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:

nums[a] + nums[b] + nums[c] == nums[d], and
a < b < c < d

Example 1:

Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.

Example 2:

Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].

Example 3:

Input: nums = [1,1,1,3,5]
Output: 4
Explanation: The 4 quadruplets that satisfy the requirement are:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

Constraints:

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

Solution 1: Brute force (224ms)

Enumerate a, b, c, d.

Time complexity: O(C(n, 4)) = O(n⁴/24)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

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

for (int b = a + 1; b < n; ++b)

for (int c = b + 1; c < n; ++c)

for (int d = c + 1; d < n; ++d)

ans += nums[a] + nums[b] + nums[c] == nums[d];

return ans;

}

};

Solution 2: Static frequency table + binary search (39ms)

For each element, we store its indices (sorted).

Given a, b, c, target t = nums[a] + nums[b] + nums[c], we check the hashtable and use binary search to find how many times it occurred after index c.

Time complexity: O(n³/6*logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

constexpr int kMax = 100;

const int n = nums.size();

int ans = 0;

vector<vector<int>> m(kMax + 1);

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

m[nums[i]].push_back(i);

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

for (int b = a + 1; b < n; ++b)

for (int c = b + 1; c < n; ++c) {

const int t = nums[a] + nums[b] + nums[c];

if (t > kMax) continue;

ans += end(m[t]) - lower_bound(begin(m[t]), end(m[t]), c + 1);

}

return ans;

}

};

Solution 3: Dynamic frequency table (29ms)

Similar to 花花酱 LeetCode 1. Two Sum, we dynamically add elements (from right to left) into the hashtable.

Time complexity: O(n³/6)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

constexpr int kMax = 100;

const int n = nums.size();

int ans = 0;

vector<int> m(kMax + 1);

// for every c we had seen, we can use it as target (nums[d]).

for (int c = n - 1; c >= 0; ++m[nums[c--]])

for (int a = 0; a < c; ++a)

for (int b = a + 1; b < c; ++b) {

const int t = nums[a] + nums[b] + nums[c];

if (t > kMax) continue;

ans += m[t];

}

return ans;

}

};

花花酱 LeetCode 1991. Find the Middle Index in Array

By zxi on December 31, 2021

Given a 0-indexed integer array nums, find the leftmost middleIndex (i.e., the smallest amongst all the possible ones).

A middleIndex is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].

If middleIndex == 0, the left side sum is considered to be 0. Similarly, if middleIndex == nums.length - 1, the right side sum is considered to be 0.

Return the leftmost middleIndex that satisfies the condition, or -1 if there is no such index.

Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4

Example 2:

Input: nums = [1,-1,4]
Output: 2
Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0

Example 3:

Input: nums = [2,5]
Output: -1
Explanation: There is no valid middleIndex.

Constraints:

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

Solution: Pre-compute + prefix sum

Pre-compute the sum of entire array. We scan the array and accumulate prefix sum and we can compute the sum of the rest of array.

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

C++

// Author: Huahua

class Solution {

public:

int findMiddleIndex(vector<int>& nums) {

int sum = accumulate(begin(nums), end(nums), 0);

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

if (cur == sum - cur - nums[i]) return i;

cur += nums[i];

}

return -1;

}

};

花花酱 LeetCode 1985. Find the Kth Largest Integer in the Array

By zxi on December 31, 2021

You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.

Return the string that represents the k^th largest integer in nums.

Note: Duplicate numbers should be counted distinctly. For example, if nums is ["1","2","2"], "2" is the first largest integer, "2" is the second-largest integer, and "1" is the third-largest integer.

Example 1:

Input: nums = ["3","6","7","10"], k = 4
Output: "3"
Explanation:
The numbers in nums sorted in non-decreasing order are ["3","6","7","10"].
The 4^th largest integer in nums is "3".

Example 2:

Input: nums = ["2","21","12","1"], k = 3
Output: "2"
Explanation:
The numbers in nums sorted in non-decreasing order are ["1","2","12","21"].
The 3^rd largest integer in nums is "2".

Example 3:

Input: nums = ["0","0"], k = 2
Output: "0"
Explanation:
The numbers in nums sorted in non-decreasing order are ["0","0"].
The 2^nd largest integer in nums is "0".

Constraints:

1 <= k <= nums.length <= 10⁴
1 <= nums[i].length <= 100
nums[i] consists of only digits.
nums[i] will not have any leading zeros.

Solution: nth_element / quick selection

Use std::nth_element to find the k-th largest element. When comparing two strings, compare their lengths first and compare their content if they have the same length.

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

C++

// Author: Huahua

class Solution {

public:

string kthLargestNumber(vector<string>& nums, int k) {

nth_element(begin(nums), begin(nums) + k - 1, end(nums), [](const auto& a, const auto& b) {

return a.length() == b.length() ? a > b : a.length() > b.length();

});

return nums[k - 1];

}

};