Posts tagged as “O(nlogn)”

花花酱 LeetCode 2208. Minimum Operations to Halve Array Sum

By zxi on March 21, 2022

You are given an array nums of positive integers. In one operation, you can choose any number from nums and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of nums by at least half.

Example 1:

Input: nums = [5,19,8,1]
Output: 3
Explanation: The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33.
The following is one of the ways to reduce the sum by at least half:
Pick the number 19 and reduce it to 9.5.
Pick the number 9.5 and reduce it to 4.75.
Pick the number 8 and reduce it to 4.
The final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75. 
The sum of nums has been reduced by 33 - 14.75 = 18.25, which is at least half of the initial sum, 18.25 >= 33/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Example 2:

Input: nums = [3,8,20]
Output: 3
Explanation: The initial sum of nums is equal to 3 + 8 + 20 = 31.
The following is one of the ways to reduce the sum by at least half:
Pick the number 20 and reduce it to 10.
Pick the number 10 and reduce it to 5.
Pick the number 3 and reduce it to 1.5.
The final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5. 
The sum of nums has been reduced by 31 - 14.5 = 16.5, which is at least half of the initial sum, 16.5 >= 31/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Constraints:

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

Solution: Greedy + PriorityQueue/Max Heap

Always half the largest number, put all the numbers onto a max heap (priority queue), extract the largest one, and put reduced number back.

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

C++

// Author: Huahua

class Solution {

public:

int halveArray(vector<int>& nums) {

double sum = accumulate(begin(nums), end(nums), 0.0);

priority_queue<double> q;

for (int num : nums) q.push(num);

int ans = 0;

for (double cur = sum; cur > sum / 2; ++ans) {

double num = q.top(); q.pop();

cur -= num / 2;

q.push(num / 2);

}

return ans;

}

};

花花酱 LeetCode 912. Sort an Array

By zxi on February 1, 2020

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

Since n <= 50000, any O(n^2) won’t pass, we need O(nlogn) or better

Solution 1: QuickSort

Time complexity: O(nlogn) ~ O(n^2)
Space complexity: O(logn) ~ O(n)

C++

// Author: Huahua, 60 ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

function<void(int, int)> quickSort = [&](int l, int r) {

if (l >= r) return;

int i = l;

int j = r;

int p = nums[l + rand() % (r - l + 1)];

while (i <= j) {

while (nums[i] < p) ++i;

while (nums[j] > p) --j;

if (i <= j)

swap(nums[i++], nums[j--]);

}

quickSort(l, j);

quickSort(i, r);

};

quickSort(0, nums.size() - 1);

return nums;

}

};

Solution 2: Counting Sort

Time complexity: O(n)
Space complexity: O(max(nums) – min(nums))

C++

// Author: Huahua, 54 ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

auto [min_it, max_it] = minmax_element(begin(nums), end(nums));

int l = *min_it, r = *max_it;

vector<int> count(r - l + 1);

for (int n : nums) ++count[n - l];

int index = 0;

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

while (count[i]--) nums[index++] = i + l;

return nums;

}

};

Solution 2: HeapSort

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

C++

// Author: Huahua, 72ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

priority_queue<int> q(begin(nums), end(nums));

int i = nums.size();

while (!q.empty()) {

nums[--i] = q.top();

q.pop();

}

return nums;

}

};

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

auto heapify = [&](int i, int e) {

while (i <= e) {

int l = 2 * i + 1;

int r = 2 * i + 2;

int j = i;

if (l <= e && nums[l] > nums[j]) j = l;

if (r <= e && nums[r] > nums[j]) j = r;

if (j == i) break;

swap(nums[i], nums[j]);

swap(i, j);

}

};

const int n = nums.size();

// Init heap

for (int i = n / 2; i >= 0; i--)

heapify(i, n - 1);

// Get min.

for (int i = n - 1; i >= 1; i--) {

swap(nums[0], nums[i]);

heapify(0, i - 1);

}

return nums;

}

};

Solution 3: MergeSort

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

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

vector<int> t(nums.size());

function<void(int, int)> mergeSort = [&](int l, int r) {

if (l + 1 >= r) return;

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

mergeSort(l, m);

mergeSort(m, r);

int i1 = l;

int i2 = m;

int index = 0;

while (i1 < m || i2 < r)

if (i2 == r || (i1 < m && nums[i1] < nums[i2]))

t[index++] = nums[i1++];

else

t[index++] = nums[i2++];

std::copy(begin(t), begin(t) + index, begin(nums) + l);

};

mergeSort(0, nums.size());

return nums;

}

};

Solution 4: BST

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

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

multiset<int> s(begin(nums), end(nums));

return {begin(s), end(s)};

}

};

花花酱 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

By zxi on January 26, 2020

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i set to true) or false (meaning you can include any restaurant). In addition, you have the filters maxPrice and maxDistance which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity veganFriendly_i and veganFriendly take value 1 when it is true, and 0 when it is false.

Example 1:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
Output: [3,1,5] 
Explanation: 
The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).

Example 2:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
Output: [4,3,2,1,5]
Explanation: The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

Example 3:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
Output: [4,5]

Constraints:

1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Solution

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

C++

// Author: Huahua

class Solution {

public:

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {

vector<pair<int, int>> rs; // <rating, id>

for (auto& r : restaurants)

if ((!veganFriendly || veganFriendly && r[2]) && r[3] <= maxPrice && r[4] <= maxDistance)

rs.emplace_back(r[1], r[0]);

sort(rbegin(rs), rend(rs));

vector<int> ans;

for (const auto& r : rs) ans.push_back(r.second);

return ans;

}

};

花花酱 LeetCode 1326. Minimum Number of Taps to Open to Water a Garden

By zxi on January 19, 2020

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3

Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2

Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

Solution 1: Greedy

Reduce to 1024. Video Stitching

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

C++

// Author: Huahua

class Solution {

public:

int minTaps(int n, vector<int>& ranges) {

vector<pair<int, int>> t;

// O(n) reduction

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

t.emplace_back(max(0, i - ranges[i]),

min(i + ranges[i], n));

// 1024. Video Stiching

sort(begin(t), end(t));

int ans = 0;

int i = 0;

int l = 0;

int e = 0;

while (e < n) {

// Extend to the right most w.r.t t[i].first <= l

while (i <= n && t[i].first <= l)

e = max(e, t[i++].second);

if (l == e) return -1; // Can not extend

l = e;

++ans;

}

return ans;

}

};

Solution 2: Greedy

Reduce to 45. Jump Game II

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

C++

// Author: Huahua

class Solution {

public:

int minTaps(int n, vector<int>& ranges) {

vector<int> nums(ranges.size());

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

int s = max(0, i - ranges[i]);

nums[s] = max(nums[s], i + ranges[i]);

}

// 45. Jump Game II

int steps = 0;

int l = 0;

int e = 0;

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

if (i > e) return -1;

if (i > l) { ++steps; l = e; }

e = max(e, nums[i]);

}

return steps;

}

};

花花酱 LeetCode 1317. Convert Integer to the Sum of Two No-Zero Integers

By zxi on January 13, 2020

Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

A and B are No-Zero integers.
A + B = n

It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

Example 1:

Input: n = 2

Output: [1,1]

Explanation: A = 1, B = 1. A + B = n and both A and B don't contain any 0 in their decimal representation.

Example 2:

1 2	<strong>Input:</strong> n = 11 <strong>Output:</strong> [2,9]

Example 3:

1 2	<strong>Input:</strong> n = 10000 <strong>Output:</strong> [1,9999]

Example 4:

1 2	<strong>Input:</strong> n = 69 <strong>Output:</strong> [1,68]

Example 5:

1 2	<strong>Input:</strong> n = 1010 <strong>Output:</strong> [11,999]

Constraints:

2 <= n <= 10^4

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getNoZeroIntegers(int n) {

auto valid = [](int x) {

if (!x) return false;

while (x) {

if (x % 10 == 0) return false;

x /= 10;

}

return true;

};

for (int i = 1; i <= n / 2; ++i)

if (valid(i) && valid(n - i))

return {i, n - i};

return {};

}

};