2025 September 27 Problems

73 views
Skip to first unread message

daryl...@gmail.com

unread,
Sep 27, 2025, 12:28:54 PM (11 days ago) Sep 27
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.

Hard problem is rolled over.




Please download and import the following iCalendar (.ics) files to your calendar system.

Anuj Patnaik

unread,
Sep 27, 2025, 12:47:01 PM (11 days ago) Sep 27
to leetcode-meetup
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def evaluateTree(self, root: Optional[TreeNode]) -> bool:
if(root.left == None and root.right == None):
return root.val != 0
left_of_root = self.evaluateTree(root.left)
right_of_root = self.evaluateTree(root.right)
if(root.val == 2):
return left_of_root or right_of_root
if(root.val == 3):
return left_of_root and right_of_root

FloM

unread,
Sep 27, 2025, 12:47:38 PM (11 days ago) Sep 27
to leetcode-meetup
2331. Evaluate Boolean Binary Tree Easy 82.4%
Time: O(n) n is number of nodes. Mem: O(1)
class Solution {
public:
bool evaluateTree(TreeNode* node) {
if (node->left == nullptr)
{
return node->val;
}

if (node->val == 2)
{
return (evaluateTree(node->left) || evaluateTree(node->right));
}
else
{
return (evaluateTree(node->left) && evaluateTree(node->right));
}
}
};

On Saturday, September 27, 2025 at 9:28:54 AM UTC-7 daryl...@gmail.com wrote:

Leonardo Pinero-Perez

unread,
Sep 27, 2025, 1:33:39 PM (11 days ago) Sep 27
to leetcode-meetup
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        return dfs(root);
    }

    bool dfs(TreeNode* n) {
        if (n->val == 0) return false;
        if (n->val == 1) return true;
        // by the problem statement, we know that n is NOT a leaf node
        // therefore we can safely assume that left and right child exists
        if (n->val == 2) return dfs(n->left) || dfs(n->right);
        if (n->val == 3) return dfs(n->left) && dfs(n->right);
        // raise error for unexpected value
        else return false;
    }
};

Eli Manzo

unread,
Sep 27, 2025, 1:35:27 PM (11 days ago) Sep 27
to leetcode-meetup
Time: o(n)
Space: o(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def evaluateTree(self, root: Optional[TreeNode]) -> bool:
    if root.val == 1:
      return True
    if root.val == 0:
      return False
   
    left = self.evaluateTree(root.left)
    right = self.evaluateTree(root.right)
   
    return left or right if root.val == 2 else left and right


On Saturday, September 27, 2025 at 9:47:38 AM UTC-7 FloM wrote:

Allen S.

unread,
Sep 27, 2025, 1:48:59 PM (11 days ago) Sep 27
to leetcode-meetup
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func evaluateTree(root *TreeNode) bool {
if root.Val < 2 {
return root.Val == 1
}
left := evaluateTree(root.Left)
right := evaluateTree(root.Right)
if root.Val == 2 {
return left || right
}
return left && right
}

Anuj Patnaik

unread,
Sep 27, 2025, 2:25:50 PM (11 days ago) Sep 27
to leetcode-meetup
class Solution:
def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
graph = defaultdict(list)
for i in range(len(edges)):
graph[edges[i][0]].append(edges[i][1])
graph[edges[i][1]].append(edges[i][0])
bob_time_to_visit_each_node = [-1] * len(amount)
def bob_dfs(curr, time, visited):
if curr == 0:
bob_time_to_visit_each_node[curr] = time
return True
visited.add(curr)
for i in graph[curr]:
if i in visited:
continue
if bob_dfs(i, time + 1, visited):
bob_time_to_visit_each_node[curr] = time
return True
visited.remove(curr)
return False
bob_dfs(bob, 0, set())
def alice_dfs(curr, time, income, visited):
visited.add(curr)
if bob_time_to_visit_each_node[curr] == -1 or time < bob_time_to_visit_each_node[curr]:
income += amount[curr]
elif time == bob_time_to_visit_each_node[curr]:
income += amount[curr] // 2
is_leaf = True
max_profit = float('-inf')
for j in graph[curr]:
if j in visited:
continue
is_leaf = False
profit = alice_dfs(j, time + 1, income, visited)
max_profit = max(max_profit, profit)
visited.remove(curr)
if is_leaf:
return income
return max_profit

return alice_dfs(0, 0, 0, set())

Leonardo Pinero-Perez

unread,
Sep 27, 2025, 2:27:50 PM (11 days ago) Sep 27
to leetcode-meetup
Ran out of time to implement one helper function, but pretty sure this was the right approach:

class Solution {
public:
    int amount_ref;

    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        // Prereq: convert the inputs into a useful data structure (tree with amounts).
        amount_ref = amount;
        unordered_map<int, vector<int>, int> g;  // node : {neighbors}, amount[node]
        for (vector<int> adj : edges) {
            // This graph will actually be directed from 0 to leaf nodes (tree-like for dfs).
            // We enforce this with only appending once, assuming nodes are ordered in
            // edges list, and that parent nodes are lower values than child nodes.
            g[adj[0]].push_back(adj[1]);
        }
       
        // We can determine the path "bob->0" that Bob will take on the tree.
        // We can use Bob to clear out the nodes where he visits prior to meeting Alice.
        vector<int> nodes_bob_travelled = get_bobs_path(g, bob);
        bool is_split_at_middle = nodes_bob_travelled.size() % 2;

        // If he ever does meet Alice, this will be midway through his path. Everything
        // after this will not affect Alice's profit. This is the extent that Bob will factor
        // into the result. Let's update the tree with Bob's effect.
        update_tree_with_bobs_traversal(g, nodes_bob_travelled, is_split_at_middle);

        // The next portion of the result is up to Alice to choose the max path on the
        // modified tree.
        return get_max_profit_path_from_modified_tree(g);
    }

    vector<int> get_bobs_path(unordered_map<int, pair<vector<int>, int>> g, int bob) {
        void dfs(int node, int target, vector<int> curr_path) {
            // if reached end of a path, do not use
            if (g[node].size() == 0) return;
            // if bob is found, return built up path
            if (node == target) {
                path_to_bob = curr_path;
                return;
            }
            // look through all potential adjacencies, add self
            curr_path.push_back(node);
            for (int adj_node : g[node]) {
                dfs(adj_node, target, curr_path);
                // perf optimization: short circuit if we found bob
                if (path_to_bob.size()) return;
            }
        }
        // because this is a tree, let's start at 0 and find bob
        path_to_bob = {};
        dfs(0, bob);
        return path_to_bob;
    }

    int get_max_profit_path_from_modified_tree(unordered_map<int, pair<vector<int>, int>> g) {
        void dfs(int n, int running_total) {
            // if reached end of a path, update res (if bigger)
            if (g[node].first.size() == 0) {
                res = max(res, running_total);
                return;
            }
            // otherwise, add node amount and keep exploring
            running_total += amount_ref[n];
            for (int adj_node : g[n]) {
                dfs(adj_node, running_total);
            }
        }
        int res = -10001;
        dfs(0, 0);
        return res;
    }
};
Message has been deleted

FloM

unread,
Sep 27, 2025, 3:28:50 PM (10 days ago) Sep 27
to leetcode-meetup
Time: O(n + q) Mem: O(n+q)

class Solution {
public:

// Make vector of cities, where cities[idx] = destination city. So cities
// starts as cities = {1, 2, 3, 4, ...};
// For each query, we'll be removing edges between startQ and endQ and replacing these
// edges with one edge. (I think of the first edge as being removed and then replaced with
// the new long edge.)

// So we start with n-1 edges from city 0 to city n-1.
// For each query, do not take away the edge from city startQ, replace it with an edge to city qEnd.
// In other words, don't increase @takeAway for the first city.
// For all other cities, do delete an edge, (increate @takeAway).
// As we travel from qStart to qEnd update that city's next city. So city[idx] = qEnd.

// In future queries, we travel along the new edges, deleting edges as we go. Where do we go?
// Where ever cities[idx] tells us to.

// The "no query rule": "There are no two queries such that queries[i][0] < queries[j][0] <
// queries[i][1] < queries[j][1]."

// So, for every query, cities between qStart and qEnd are essentially removed. But what if
// qStart is on one of these removed cities? That can never happen according to the description.
// Well, it could happen, but then the current query will be a nested query (nested inside a
// previous query). In that case, simply continue to the next query. Doesn't change the number
// of edges from city zero to end.

// What if qStart starts before any previous qStarts, but ends at a previously removed city?
// Again, not possible according to the description.

// Essentially, if there is a query, we should remove all EXISTING edges between the qStart and qEnd.
// So, update all edges as we travel, and count the removed edges.

vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {

// vector of cities and their destinations.
vector<int> cities(n, 0);
iota(cities.begin(), cities.end(), 1);

// Answer.
vector<int> ans(queries.size(), -1);

// Edges removed so far.
int subtrahend = 0;

// For each query.
for(int ii=0; ii<queries.size(); ++ii)
{
int qStart = queries[ii][0];
int qEnd = queries[ii][1];

// Edges removed in this query.
int takeAway = 0;

// idx is from range [qStart, qEnd)
int idx = qStart;
while(idx < qEnd)
{
// Do not takeAway an edge for the qStart city (it's replaced). But do mark it with qEnd.
if (idx == qStart)
{
// Don't update with this city with a shorter edge. A longer edge already exists.
if (qEnd < cities[qStart]) // if (cities[qStart] != qStart + 1)
{
break;
}
else
{
// temp is the next city, which will have the next edge that needs to be taken away.
int temp = cities[idx];
// update cities[idx].
cities[idx] = qEnd;
// go to next city to remove that edge.
idx = temp;
}
}
// Else not the startCity, so do increase @takeAway.
else
{
int temp = cities[idx];
cities[idx] = qEnd;
idx = temp;
++takeAway;
}
}
subtrahend += takeAway;

// Original number of edges was n-1.
ans[ii] = n - 1 - subtrahend;
}

return ans;

}
};

Carrie Lastname

unread,
Sep 27, 2025, 3:40:46 PM (10 days ago) Sep 27
to leetcode-meetup
class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        e = {}
        for u,v in edges:
            if u not in e:
                e[u] = []
            if v not in e:
                e[v] = []
            e[u].append(v)
            e[v].append(u)
        parents = [-1 for _ in range(len(e))]
        children = {}
        s = [0]
        while s:
            curr = s.pop()
            if curr in children:
                continue
            children[curr] = []
            for neighbor in e[curr]:
                if neighbor not in children:
                    s.append(neighbor)
                    parents[neighbor] = curr
                    children[curr].append(neighbor)

        def path(a,b,v):
            t = 0
            if a == b:
                t = amount[a]//2
            elif a not in v:
                t = amount[a]
            max_path = float("-inf")
            v.add(b)
            for child in children[a]:
                new_bob = max(0, parents[b])
                max_path = max(max_path, path(child, new_bob, v))
            if b in v:
                v.remove(b)
            if max_path == float("-inf"):
                return t
            return t + max_path

        return path(0,bob,set())

On Saturday, September 27, 2025 at 9:28:54 AM UTC-7 daryl...@gmail.com wrote:
Reply all
Reply to author
Forward
0 new messages