2024 June 29 Problems

[daryl...@gmail.com]

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.

2848Points That Intersect With Cars75.1%Easy

3015Count the Number of Houses at a Certain Distance I55.6%Medium

3017Count the Number of Houses at a Certain Distance II21.4%Hard

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-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609

[Flocela Maldonado]

2848Points That Intersect With Cars75.1%Easy

Time: O(n), Memory: O(1)

class Solution {

public:

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

sort(nums.begin(), nums.end(), [](const vector<int>& a, const vector<int>& b){ return a[0] < b[0]; });

int count = 0;

int prevEnd = 0;

for(int ii=0; ii<nums.size(); ++ii)

{

int start = nums[ii][0];

int end = nums[ii][1];

if(prevEnd >= end)

{

continue;

}

if (prevEnd < start)

{

count += (end - start + 1);

}

else

{

count += (end - prevEnd);

}

prevEnd = end;

}

return count;

}

};

[Carlos Green]

/**

* @param {number[][]} nums

* @return {number} Time & Space O(n)

*/

var numberOfPoints = function(nums) {

const points = new Set()

for (let [start, end] of nums) {

for (let i = start; i <= end; i++) {

points.add(i)

}

}

return points.size

};

[Lan Ying]

Think for Points That Intersect With Cars, if we sort, the runtime is O(nlogn).

Here's my solution in Python:

class Solution:

def numberOfPoints(self, nums: List[List[int]]) -> int:

nums.sort(key=lambda x:x[0])

res = 0

max = 0

for start, end in nums:

# overlap

if start <= max and end > max:

res += (end - max)

max = end

# no overlap

elif start > max:

res += (end - start + 1)

max = end

return res

On Saturday, June 29, 2024 at 10:14:51 AM UTC-7 flo...@gmail.com wrote:

[Anne-Elise Chung]

2848 Points That Intersect With Cars75.1%

/**

* @param {number[][]} nums

* @return {number}

*/

var numberOfPoints = function(nums) {

let points = new Array();

let result = 0;

for(let n of nums){

let start = n[0];

let end = n[1];

while(start <= end){

if(points[start] != 1){

++result;

points[start] = 1;

}

++start;

}

}

return result;

};

Time: O(n*r) where n is the amount of nums, and r is the width of the range for each num.

Space: O(m) where m is the largest singular value in our nums, max of num[1]

This probably could have been much more efficient but I woke up late and found the solution in about 5 minutes, so pretty happy with that haha.

 

On Saturday, June 29, 2024 at 9:26:23 AM UTC-7 daryl...@gmail.com wrote:

[Flocela Maldonado]

First Saturday of the Month: July 6th, 2024, Meet after the zoom call for coffee. 

After the zoom meeting, we go from the library to one of the restaurants/coffee houses next to the library.

Which library?? Northside Branch Library at 695 Moreland Way, Santa Clara, CA 95054.

Please join!!

[Priyank Gupta]

# Time : O(n*k) => n = len(nums), k = avg len of each element

# Space: O(m) => range of nums.

class Solution:

def numberOfPoints(self, nums: List[List[int]]) -> int:

s = set()

for start, end in nums:

for i in range(start, end+1):

s.add(i)

return len(s)

[Priyank Gupta]

'''

Start a BFS from each node and find the shortest distance from that node to each other node and maintain the res array of distances between 2 nodes and update that whenever we encounter that distance.

Time : O(n+e) => n = no of nodes, e = no of edges

Space: O(n)

'''

from collections import defaultdict

from collections import deque

class Solution:

def countOfPairs(self, n: int, x: int, y: int) -> List[int]:

graph = self.buildGraph(n, x, y)

res = [0]*n

for i in range(1, n+1):

self.bfs(i, graph, res)

return res

def bfs(self, node, graph, res):

q, seen, dist = deque(), {node}, -1

q.append(node)

while(q):

noOfNodes = len(q)

dist += 1

if dist > 0:

res[dist-1] += noOfNodes

for _ in range(noOfNodes):

node = q.popleft()

for neighbor in graph[node]:

if neighbor not in seen:

q.append(neighbor)

seen.add(neighbor)

return

def buildGraph(self, n, x, y):

d = defaultdict(list)

for i in range(1,n):

d[i].append(i+1)

d[i+1].append(i)

d[x].append(y)

d[y].append(x)

return d

[Vivek H]

*****************************************************************************************************

3015Count the Number of Houses at a Certain Distance I55.6%Medium

****************************************************************************************************

class Solution {

public:

    map<int, vector<pair<int, int>>> M;

    void print(map<int, vector<int>>& G) {

        for(auto &a : G) {

            cout << a.first << ": ";

            for(auto &b : a.second)

                cout << b  << " ";

            cout << endl;

        }

    }

    void printM(map<int, vector<pair<int, int>>>& M) {

        for(auto &a : M) {

            cout << a.first << ": ";

            for(auto &b : a.second) {

                cout << "(" << b.first << "," << b.second << ")";

            }

            cout << endl;

        }

    }

    void bfs( map<int, vector<int>>& graph, int start) {

            map<int, bool> visited;

            //create a Q of pair of node and dist from start node

            queue<pair<int, int>> Q;

            Q.push(make_pair(start, 0));

            visited[start] = true;

            while(!Q.empty()) {

                int node = Q.front().first;

                int prevDist = Q.front().second;

                Q.pop();

               

                for(int i=0; i<graph[node].size(); i++) {

                    if(!visited[graph[node][i]]) {

                        visited[graph[node][i]] = true;

                        Q.push(make_pair(graph[node][i], prevDist+1));

                        /* In the map, keep storing the pairs and the distance from start node */

                        M[prevDist+1].push_back(make_pair(start, graph[node][i]));

                    }

                }

            }

    }

   

    vector<int> countOfPairs(int n, int x, int y) {

        map<int, vector<int>> graph;

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

            graph[i].push_back(i+1);

            graph[i+1].push_back(i);

        }

        graph[x].push_back(y);

        graph[y].push_back(x);

        vector<int> result;

        /* run bfs for all nodes */

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

            bfs(graph, i);

           

        }

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

            result.push_back(M[i].size());

        }

       

        //printM(M);

        //print(graph);

        return result;

       

    }

};

--
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/7a9aaba4-6f78-42d1-b8e8-eef9e68db713n%40googlegroups.com.

[Vivek H]

*********************************************************************

2848Points That Intersect With Cars75.1%Easy

*********************************************************************

O(n) - time 

O(101) - space 

class Solution {

public:

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

        vector<int> V(101, 0);

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

            for (int j = nums[i][0]; j <= nums[i][1]; j++) {

                V[j] += 1;

            }

        }

        int pointsCovered = 0;

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

            if (V[i] > 0)

                pointsCovered++;

        }

        return pointsCovered;

    }

};

On Sat, Jun 29, 2024 at 9:26 AM daryl...@gmail.com <daryl...@gmail.com> wrote:

--