2020 October 17 Questions

Daryl Wang

unread,

Oct 17, 2020, 1:00:17 PM10/17/20

to leetcode-meetup

Please work on the questions at home and post your replies to the thread. We'll be going over them next week on Zoom.

183

Customers Who Never Order

54.7%

Easy

739

Daily Temperatures

63.9%

Medium

1617

Count Subtrees With Max Distance Between Cities

61.4%

Hard

Carlos Green

unread,

Oct 17, 2020, 2:03:38 PM10/17/20

to leetcode-meetup

https://leetcode.com/problems/customers-who-never-order/submissions/

Runtime: 425 ms, faster than 90.08% of MySQL online submissions for Customers Who Never Order.

Memory Usage: 0B, less than 100.00% of MySQL online submissions for Customers Who Never Order.

select customers.name as 'Customers'

from customers

where customers.id not in

(select customerid from orders);

Carlos Green

unread,

Oct 17, 2020, 2:13:18 PM10/17/20

to leetcode-meetup

https://leetcode.com/problems/daily-temperatures/submissions/

Runtime: 940 ms, faster than 30.75% of JavaScript online submissions for Daily Temperatures.

Memory Usage: 47.9 MB, less than 5.08% of JavaScript online submissions for Daily Temperatures.

var dailyTemperatures = function(temps) {

return temps.map((temp, idx) => {

let nextDay = 0

for (let i = idx + 1; i < temps.length; i++) {

if (temp < temps[i]) {

nextDay = i - idx

return nextDay

}

return nextDay

})

};

Daryl Wang

unread,

Oct 24, 2020, 11:04:04 AM10/24/20

to leetcode-meetup

739

Daily Temperatures

63.9%Medium

There are two basic ideas here: work backwards and use a stack. We keep a stack of temperatures and their index, in increasing order. Every time we see a new temperature we pop items off the stack until we see a bigger temperature. The answer for the current temperature is then the index of the top of the stack minus the current index. If the stack is empty, then the answer is -1. We then add the current temperature and its index to the stack, and move onto the next temperature.

(This can be simplified by just storing the index in the stack and looking up the temperature.)

The stack starts off empty and we start from the last temperature and work backwards.

O(n) time

O(n) space

class Solution:

def dailyTemperatures(self, T: List[int]) -> List[int]:

results = [0] * len(T)

seenTemps = []

for i in reversed(range(len(T))):

if seenTemps:

while (seenTemps and T[i] >= T[seenTemps[-1]]):

seenTemps.pop()

if seenTemps:

results[i] = seenTemps[-1] - i

seenTemps.append(i)

return results

Daryl Wang

unread,

Oct 24, 2020, 11:44:41 AM10/24/20

to leetcode-meetup

1617

Count Subtrees With Max Distance Between Cities

61.4%Hard

The solution for this problem is pretty close to brute force:

1) Try all the possible subtrees

2) See what the maximum distance is for each subtree.

To do 1), we use a bitmap to represent the graph. The nth bit is 1 if city n is in the graph, and 0 otherwise. This way we iterate through all the possible subtrees by going from 1 to 2^n.

To do 2), we do a bfs from every city in the subtree and use that to find the farthest away node.

Once we do have the maximum distance for a subtree, we can increment the counts for all d less than or equal to that in the answer array.

O(n^2 * 2^n) time

O(n^2) space

class Solution(object):

def countSubgraphsForEachDiameter(self, n, edges):

adj_list = defaultdict(list)

for u, v in edges:

adj_list[u-1].append(v-1)

adj_list[v-1].append(u-1)

def bfs(src, cities):

visited = set([src])

q = deque([(src, 0)]) # Pair of (vertex, distance)

farthestDist = 0 # Farthest distance from src to other nodes

while len(q) > 0:

u, d = q.popleft()

farthestDist = d

for v in adj_list[u]:

if v not in visited and v in cities:

visited.add(v)

q.append((v, d+1))

return farthestDist, visited

def maxDistance(tree_bitmask): # return: maximum distance between any two cities in our subset. O(n^2)

cities = set()

for i in range(n):

# Check if the ith bit is set

if (tree_bitmask >> i) & 1 == 1:

cities.add(i)

ans = 0

for i in cities:

farthestDist, visited = bfs(i, cities)

if len(visited) < len(cities): return 0 # Can't visit all nodes of the tree -> Invalid tree

ans = max(ans, farthestDist)

return ans

ans = [0] * (n - 1)

for subtree_candidate in range(1, 2 ** n):

d = maxDistance(subtree_candidate)

if d > 0: ans[d - 1] += 1

return ans

On Saturday, October 17, 2020 at 10:00:17 AM UTC-7, Daryl Wang wrote:

safique ahemad

unread,

Oct 24, 2020, 5:58:48 PM10/24/20

to leetcod...@googlegroups.com

1617

Count Subtrees With Max Distance Between Cities

61.4%

Hard

type Graph struct {
adj [][]int
}

func makeGraph(n int) Graph {
adj := make([][]int, n+1)
for i := range adj {
adj[i] = make([]int,0)
}
return Graph{adj: adj}
}

func(g Graph) AddEdge(u, v int) {
g.adj[u] = append(g.adj[u], v)
g.adj[v] = append(g.adj[v], u)
}

func (g Graph) neighbourList(u int) []int {
return g.adj[u]
}

func countSubgraphsForEachDiameter(n int, edges [][]int) []int {

totalSubTrees := int(math.Pow(2, float64(n)))

result := make([]int, n)

g := makeGraph(n)

for _, edge := range edges {
g.AddEdge(edge[0], edge[1])
}

for setMask := 1; setMask < totalSubTrees; setMask++ {
if (setMask & (setMask - 1)) != 0 {
nodes, noNodes := makeSubTree(setMask, n)

maxDiam := getMaxDiamSubtree(nodes, noNodes, g)

if maxDiam > 0 {
result[maxDiam] += 1
}
}
}

return result[1:]
}

func makeSubTree(mask, n int) ([]int, int) {

pos := 1
nodes := make([]int, n+1)
noNodes := 0

for mask > 0 {
if mask & 1 == 1 {

nodes[pos] = 1
noNodes++
}
mask >>= 1
pos++
}
return nodes, noNodes
}

func getMaxDiamSubtree(nodes []int, noNodes int, g Graph) int{

getMaxDistBfs := func(src int) (int, int) {
q := []int{src}
dist := 0
visted := make([]bool, len(g.adj))
noVistedNodes := 1
visted[src] = true
for len(q) > 0 {

levelNodes := len(q)

for levelNodes > 0 {
curr := q[0]; q = q[1:]

for _, nei := range g.neighbourList(curr) {

if nodes[nei] != 0 && visted[nei] != true {
q = append(q, nei)
visted[nei] = true
noVistedNodes++
}
}

levelNodes--
}
dist++
}

return dist-1, noVistedNodes
}
maxDiam := 0
for node := range nodes {
if nodes[node] == 0 {
continue
}
d, numVisted := getMaxDistBfs(node)
if numVisted < noNodes {
maxDiam = 0
break
}
if d > maxDiam {
maxDiam = d
}
}
return maxDiam
}

--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS

https://www.techbayarea.us/

FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
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/13a6614c-36f4-456b-a48f-f22ad8caf436o%40googlegroups.com.

--

Regards,

Safique Ahemad

Boyang Zhang

unread,

Apr 5, 2025, 2:09:40 PMApr 5

to leetcode-meetup

Daily temperatures: montonic Stack

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0]*len(temperatures)
        monotonic_decreasing_stack = []

        for day, temp in enumerate(temperatures):
            while monotonic_decreasing_stack and temperatures[monotonic_decreasing_stack[-1]]<temp:
                prev_day = monotonic_decreasing_stack.pop()
                answer[prev_day] = day-prev_day
            
            monotonic_decreasing_stack.append(day)
        return answer

Reply all

Reply to author

Forward