2024 June 15 Problems
71 views
Skip to first unread message
daryl...@gmail.com
Jun 15, 2024, 12:49:18 PMJun 15
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.
Please post your solutions to this thread so others can use this as a reference.
561Array Partition79.0%Easy
3170Lexicographically Minimum String After Removing Stars35.6%Medium
Please download and import the following iCalendar (.ics) files to your calendar system.
Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZJoin Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Flocela Maldonado
Jun 15, 2024, 1:01:34 PMJun 15
to leetcode-meetup
561Array Partition79.0%Easy
Time : O(n* lg(n) + n) Memory: O(1)
Time : O(n* lg(n) + n) Memory: O(1)
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int sum = 0;
for(int ii=0; ii<nums.size(); ii+=2)
{
sum += std::min(nums[ii], nums[ii+1]);
}
return sum;
}
};
Vivek H
Jun 15, 2024, 1:26:17 PMJun 15
to leetcod...@googlegroups.com
**********************************************************************************
3111Minimum Rectangles to Cover Points64.5%Medium
**********************************************************************************
Time Complexity = nlogn
Space complexity = O(1)
class Solution {
public:
static bool comp(vector<int>& v1, vector<int>& v2) {
return v1[0] < v2[0];
}
int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
sort(points.begin(), points.end(), comp);
int minRec = 0;
int i=0; int j=1;
while( j < points.size()) {
if(points[j][0] - points[i][0] <= w) {
j++;
} else {
minRec++;
i=j; j++;
}
}
minRec++;
return minRec;
}
};
--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/f8449ff0-9aa3-4452-b2c2-65d592eef8c3n%40googlegroups.com.
Anne-Elise Chung
Jun 15, 2024, 1:51:08 PMJun 15
to leetcode-meetup
Array Partition (easy)
/**
* @param {number[]} nums
* @return {number}
*/
var arrayPairSum = function(nums) {
function compareNumbers(a, b) {
return a - b;
}
//sort
nums.sort(compareNumbers); //min time O(nlogn)
let max = 0;
for( let i = 0; i < nums.length - 1; i+=2)
{
max += Math.min(nums[i], nums[i+1]); //min time O(n)
}
return max;
};
Time: O(nlogn + n)
Space: O(1)
Approach:
In order to assure that we get the highest min values, the biggest items in the array need to paired off together, thus it made sense to sort the array first. Implementing a max heap might have been more time-efficient than calling Array.sort() but for the sake of time, I decided to just use the library sort function.
Message has been deleted
Message has been deleted
Anne-Elise Chung
Jun 16, 2024, 1:52:46 AMJun 16
to leetcode-meetup
min rectangles: https://leetcode.com/problems/minimum-rectangles-to-cover-points
Thanks to Flo and Vivek's explanation this morning, I was able to simplify my approach and get a solution that I'm happy with.
The only part I wish I could improve is the awkward conversion from array to set and back to array to filter unique numbers.
I probably could have used a filter method for this, but I was too lazy...
/**
* @param {number[][]} points
* @param {number} w
* @return {number}
*/
var minRectanglesToCoverPoints = function(points, w) {
function comparefn(a,b){
return a[0] - b[0];
}
points.sort(comparefn); // O(nlogn)
let x_values = points.map((element)=> element[0]); // O(n)
let set = new Set(x_values); // O(n)
let numRectangles = 0;
let j = 0;
const arr = Array.from(set); // O(n)
// O(n)
for(let i = 0; i < arr.length; i++){
let x = arr[i];
let max_dist = x + w;
while(arr[j] <= max_dist){
j++;
}
++numRectangles;
i = j - 1;
}
return numRectangles;
};
Time Complexity: O(nlogn + n)
Space Complexity: because I am making a new set and new array my space complexity is O(n). I could probably have avoided this, but it made the logic easier to follow.
Approach: For the approach, I borrowed some of Flo's logic of processing only the unique x values, and Vivek's two-pointer approach. I found that a combination of both made the resulting greedy search a bit easier to wrap my head around.
On Saturday, June 15, 2024 at 9:49:18 AM UTC-7 daryl...@gmail.com wrote:
vinay
Jun 16, 2024, 1:31:14 PMJun 16
to leetcod...@googlegroups.com
Started by sorting the points based on their x-coordinates. This approach helps in grouping as many points as possible into one rectangle.
Then create a new rectangle once a point falls outside the current rectangle's boundary, which is defined by the condition .
time complexity: o(n log n)
class Solution {
public int minRectanglesToCoverPoints(int[][] points, int w) {
int i = 0, j = 0;
int count = 0;
Arrays.sort(points, (x,y) -> Integer.compare(x[0], y[0]));
while(i < points.length){
int curX = points[i][0];
while(j < points.length && points[j][0] - curX <= w){
j++;
}
count++;
i = j;
}
return count;
}
}
Flocela Maldonado
Jun 16, 2024, 3:16:29 PMJun 16
to leetcode-meetup
Time O(n*lg(n) + n) Mem: O(n)
class Solution {
public:
string clearStars(string s) {
// Priority queue of pair<char, int>.
// Primary sorted by char. Smaller chars are first. Secondary sorted by ints. Larger ints are first.
priority_queue<
pair<char, int>,
vector<pair<char, int>>,
decltype([](const pair<char, int>& a, const pair<char, int>& b)
{
if(b.first == a.first)
{
return a.second < b.second;
}
else
{
return a.first > b.first;
}
})
> pq{};
// Iterate s from left to right. If char in s is '*' put the character from pq into
// removedIndexes. These indexes will not be included in returned string. See stringstream ss below.
unordered_set<int> removedIndexes{};
for(int ii=0; ii<s.size(); ++ii)
{
char c = s[ii];
if(c == '*')
{
pair<char, int> top = pq.top();
pq.pop();
removedIndexes.insert(top.second);
}
else
{
pq.push({c, ii});
}
}
// Put in all characters from s into ss except for '*' chars and
// chars that were removed from s (that's removedIndexes).
stringstream ss{};
for(int ii=0; ii<s.size(); ++ii)
{
if (s[ii] == '*')
{
continue;
}
if (removedIndexes.find(ii) == removedIndexes.end())
{
ss << s[ii];
}
}
return ss.str();
}
};
Vivek H
Jul 3, 2024, 4:23:00 PM (2 days ago) Jul 3
to leetcod...@googlegroups.com
***********************************************************************************************************************
***********************************************************************************************************************
class Solution {
public:
struct comp {
bool operator()(const vector<int>& v1, const vector<int>& v2) {
if (v1[1] == v2[1]) {
return v1[0] < v2[0];
} else {
return v1[1] > v2[1];
}
}
};
string clearStars(string s) {
/* create a priority_queue of [index, char] where the elements are first heapified based on
smallest char, and if the char is same, it heapified based on larger index
*/
priority_queue<vector<int>, vector<vector<int>>, comp> heap;
/* map to store all the indices that we have to ignore in the final string */
map<int, int> ignoredIdx;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '*') {
/* current char is *, so we need to ignore its index */
ignoredIdx[i]++;
/* pop the heap and store the index retrieved from it, in the map */
ignoredIdx[heap.top()[0]]++;
heap.pop();
} else {
heap.push({i, s[i]});
}
}
string result;
for(int i=0; i<s.length(); i++) {
if(ignoredIdx.count(i) == 0) {
/*form the result string using leftover indices */
result += s[i];
}
}
return result;
}
};
Reply all
Reply to author
Forward
0 new messages