2025 December 13 Problems

daryl...@gmail.com

unread,

Dec 13, 2025, 12:38:11 PM (2 days ago) Dec 13

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 carried over.

146. LRU Cache Medium 46.4%

460. LFU Cache Hard 48.0%

3559. Number of Ways to Assign Edge Weights II Hard 59.9%

We're going to try to use the same Google meet link as the last few times: https://meet.google.com/xnn-kifj-jnx?pli=1

Kevin Burleigh

unread,

Dec 13, 2025, 1:08:08 PM (2 days ago) Dec 13

to leetcode-meetup

3559. Number of Ways to Assign Edge Weights II Hard 59.9%

Posting my solution from last week (spiffed up a bit). It passes the tests, but is pretty slow. Gonna try to improve it this week using a new technique...

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        ## convert the given edges into a more useful structure
        neighbors_by_node = defaultdict(list)
        for edge in edges:
            neighbors_by_node[edge[0]].append(edge[1])
            neighbors_by_node[edge[1]].append(edge[0])

        ## perform a DFS starting at node 1, recording each node's
        ## parent and distance from the root
        distance_to_node_1_by_node = {1: 0}
        parent_by_node             = {1: None}
        def calc_distances_and_parents (node, node_parent):
            for neighbor in neighbors_by_node[node]:
                if neighbor != node_parent:
                    distance_to_node_1_by_node[neighbor] = 1 + distance_to_node_1_by_node[node]
                    parent_by_node[neighbor]             = node
                    calc_distances_and_parents(neighbor, node)
        calc_distances_and_parents(1, None)

        ## a memoized function for finding the distance between two nodes
        distance_memo = {}
        def find_distance_between(node_a, node_b):
            ## put the nodes into a canonical ordering to avoid
            ## wasted space / missed lookups
            key = (node_a,node_b) if node_a<node_b else (node_b,node_a)            
            if key not in distance_memo:
                if node_a == node_b:
                    result = 0
                elif node_a == 1:
                    result = distance_to_node_1_by_node[node_b]
                elif node_b == 1:
                    result = distance_to_node_1_by_node[node_a]
                else:
                    if distance_to_node_1_by_node[node_a] > distance_to_node_1_by_node[node_b]:
                        result = 1 + find_distance_between(parent_by_node[node_a], node_b)
                    else:
                        result = 1 + find_distance_between(parent_by_node[node_b], node_a)
                distance_memo[key] = result
            return distance_memo[key]

        ## a memoized calculation for the number of solutions
        ## given the path length
        @cache
        def find_num_ways(N_edges):
            if N_edges == 0:
                return 0
            else:
                return pow(2, N_edges-1, mod=10**9 + 7)

        ## process each query and update the result
        result = []
        for q in queries:
            N_edges = find_distance_between(q[0],q[1])
            N_ways = find_num_ways(N_edges)
            result.append(N_ways)
        
        return result

FloM

unread,

Dec 13, 2025, 1:10:13 PM (2 days ago) Dec 13

to leetcode-meetup

146. LRU Cache Medium 46.4%

class LRUCache {

struct Node
{
    Node(int k, int v): key{k}, val{v}{};
    Node(int k, Node* p, Node* n):key{k}, prev{p}, next{n}{}

    int key = -1;
    int val = -1;
    Node* prev = nullptr;
    Node* next = nullptr;
};

public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        if(_nodePerKey.find(key) == _nodePerKey.end())
        {
            return -1;
        }

        Node* node = _nodePerKey[key];
        int value = node->val;
        if(node != _head)
        {
            removeNode(node);
            addNodeToFront(new Node({key, value}));
        }
        return _nodePerKey[key]->val;
    }
    
    void put(int key, int value) {
        if(_nodePerKey.find(key) != _nodePerKey.end())
        {
            removeNode(_nodePerKey[key]);
        }
        addNodeToFront(new Node(key, value));
        
        if(_nodePerKey.size() > _capacity)
        {
            removeNode(_tail);
        }
    }

private:

    void addNodeToFront(Node* node)
    {
        if(_head == nullptr)
        {
            _head = node;
            _tail = node;
        }
        else
        {
            Node* oldHead = _head;
            node->next = oldHead;
            oldHead->prev = node;
            _head = node;
        }
        _nodePerKey.insert({node->key, node});
    }

    void removeNode(Node* node)
    {
        Node* oldPrev = node->prev;
        Node* oldNext = node->next;
        if (oldPrev != nullptr)
        {
            oldPrev->next = oldNext;
        }
        if(oldNext != nullptr)
        {
            oldNext->prev = oldPrev;
        }
        if(node == _head)
        {
            _head = oldNext;
        }
        if(node == _tail)
        {
            _tail = oldPrev;
        }
        _nodePerKey.erase(node->key);
        delete node;
    }

    Node* _head = nullptr;
    Node* _tail = nullptr;
    unordered_map<int, Node*> _nodePerKey{};
    int _capacity = -1;
};

FloM

unread,

Dec 13, 2025, 1:19:27 PM (2 days ago) Dec 13

to leetcode-meetup

3559. Number of Ways to Assign Edge Weights II Hard 59.9%

Time: O(n) Mem: O(n)

class Solution {
public:
    vector<int> assignEdgeWeights(vector<vector<int>>& edges, vector<vector<int>>& queries) {

        // Adjacency list
        unordered_map<int, vector<int>> adjList{};

        for(const vector<int>& edge : edges)
        {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        // Map of depth of each node. Map of parent of each node.
        unordered_map<int, int> depthPerNode{};
        unordered_map<int, int> parPerNode{};

        // Use bfs to populate depthPerNode and parPerNode.
        int depth = 0;
        deque<int> dq{};
        dq.push_back(1);
        dq.push_back(-1);
        while(!dq.empty())
        {
            if (dq.front() == -1)
            {
                ++depth;
                dq.pop_front();
                if (!(dq.empty()))
                {
                    dq.push_back(-1);
                }
                continue;
            }

            int top = dq.front();
            dq.pop_front();
            depthPerNode.insert({top, depth});

            for(int adj : adjList[top])
            {
                if (!parPerNode.contains(adj))
                {
                    dq.push_back(adj);
                    parPerNode.insert({adj, top});
                }
            }
        }

        // Answer
        vector<int> ans{};

        // Memoization
        unordered_map<double, int> ansPerQuery{};

        // For each query find the num of edges from u to v.
        // Num of edges is the sum of 1) difference in depths
        // between u and v. 2) Number of nodes from the common parent
        // to the shortest depth between u and v.
        for(const vector<int>& query : queries)
        {
            int* lowerNum = nullptr;
            int* higherNum = nullptr;

            int numA = query[0];
            int numB = query[1];

            if (numA == numB)
            {
                ans.push_back(0);
                continue;
            }

            lowerNum  = (depthPerNode[numA] < depthPerNode[numB])? (&numB) : (&numA);
            higherNum = (depthPerNode[numA] < depthPerNode[numB])? (&numA) : (&numB);

            double key = ( (static_cast<double>(*lowerNum)) * 100000 ) +(*higherNum);

            if (ansPerQuery.contains(key))
            {
                ans.push_back(ansPerQuery[key]);
                continue;
            }

            int diffBelow = 0;
            while(depthPerNode[*lowerNum] > depthPerNode[*higherNum])
            {
                ++diffBelow;
                lowerNum = &(parPerNode[(*lowerNum)]);
            }

            // numC and numD are at the same depth.
            int numC = *lowerNum;
            int numD = *higherNum;

            int diffAbove = 0;
            while(numC != numD)
            {
                numC = parPerNode[numC];
                numD = parPerNode[numD];
                ++diffAbove;
            }

            int diff = diffBelow + (2*diffAbove);

            int val = 1;
            for(int ii=0; ii<diff-1; ++ii)
            {
                val *=2;
                val = (val % (1000000007));
            }

            ansPerQuery.insert({key, val});
            ans.push_back(val);
            
        }

        return ans;
        
    }
};

Gowrima Jayaramu

unread,

Dec 13, 2025, 2:02:21 PM (2 days ago) Dec 13

to leetcode-meetup

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        res = -1

        if key in self.cache:
            res = self.cache[key]
            self.cache.move_to_end(key, last=True)
        
        return res

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key, last=True)
            return

        if len(self.cache) >= self.capacity:
            # evict least recently used
            self.cache.popitem(last=False)

        self.cache[key] = value
        self.cache.move_to_end(key, last=True)

# Time: O(n)
# Space: O(n)

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Allen S.

unread,

Dec 13, 2025, 2:05:59 PM (2 days ago) Dec 13

to leetcode-meetup

type item struct {
    le *list.Element
    v int
}

type LRUCache struct {
    c int
    q *list.List // DLL, que of keys
    m map[int]*item // map of pointers to items
}


func Constructor(capacity int) LRUCache {
    return LRUCache{
        c: capacity,
        q: list.New(),
        m: make(map[int]*item),
    }
}


func (this *LRUCache) Get(key int) int {
    if item, ok := this.m[key]; ok { // if key in que move to back
        this.q.MoveToBack(item.le)
        return item.v
    }
    return -1
}


func (this *LRUCache) Put(key int, value int)  {
    if obj, ok := this.m[key]; ok { // if element esixts
        this.q.MoveToBack(obj.le) // if key in m, move to back
        obj.v = value // update value
    } else { // else push to back
        le := this.q.PushBack(key)
        obj := &item {
            le: le,
            v: value,
        }
        this.m[key] = obj
    }

    // if over cap, evict, 
    if this.q.Len() > this.c {
        le := this.q.Front()
        this.q.Remove(le)
        delete(this.m, le.Value.(int))
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

On Saturday, December 13, 2025 at 9:38:11 AM UTC-8 daryl...@gmail.com wrote:

Anuj Patnaik

unread,

Dec 13, 2025, 2:09:20 PM (2 days ago) Dec 13

to leetcode-meetup

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):

        self.capacity = capacity
        self.dict_of_nums = dict() 
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def add_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:

        if key in self.dict_of_nums:
            node = self.dict_of_nums[key]
            self.remove(node)
            self.add_front(node)
            return node.value
        else:
            return -1

            
    def put(self, key: int, value: int) -> None:

        if key in self.dict_of_nums:
            node = self.dict_of_nums[key]
            node.value = value
            self.remove(node)
            self.add_front(node)
        else:
            new_node = Node(key, value)
            self.dict_of_nums[key] = new_node
            self.add_front(new_node)
            if len(self.dict_of_nums) > self.capacity:
                node_to_remove = self.tail.prev
                self.remove(node_to_remove)
                del self.dict_of_nums[node_to_remove.key]

                

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Reply all

Reply to author

Forward