leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2779.cpp (1056B)

0 // Binary search: O(n * logn) 1 class Solution { 2 public: 3 int maximumBeauty(vector<int> &nums, int k) const { 4 sort(begin(nums), end(nums)); 5 int res = 1; 6 7 for (int i = 0; i < size(nums); i++) { 8 const auto it = upper_bound(begin(nums), end(nums), 2 * k + nums[i]); 9 res = max(res, (int)distance(begin(nums) + i, it)); 10 } 11 12 return res; 13 } 14 }; 15 16 // Line sweep: O(n) 17 class Solution { 18 public: 19 int maximumBeauty(const vector<int> &nums, int k) const { 20 int mini = INT_MAX, maxi = INT_MIN; 21 static int count[200002]; 22 23 memset(count, 0x00, sizeof(count)); 24 for (const int n : nums) { 25 const int a = max(n - k, 0); 26 const int b = n + k + 1; 27 28 count[a]++; 29 count[b]--; 30 31 mini = min(mini, a); 32 maxi = max(maxi, b); 33 } 34 35 int res = 1; 36 for (int i = mini, acc = 0; i <= maxi; i++) { 37 acc += count[i]; 38 res = max(res, acc); 39 } 40 41 return res; 42 } 43 };