2024 May 4 Problems

48 views
Skip to first unread message

daryl...@gmail.com

unread,
May 4, 2024, 12:42:42 PMMay 4
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.




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
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

Reminder that we have the monthly meet up for coffee afterwards for anyone attending live.

Flocela Maldonado

unread,
May 4, 2024, 1:21:57 PMMay 4
to leetcode-meetup
653Two Sum IV - Input is a BST61.2%Easy
Time O(n), Memory O(lg(n))
class Solution {
public:

void dfsHasCouple(TreeNode* node, bool& hasCouple, unordered_set<int>& values, int k)
{

if(node == nullptr)
{
return;
}
else
{
dfsHasCouple(node->left, hasCouple, values, k);
dfsHasCouple(node->right, hasCouple, values, k);
int wantedDifference = k - node->val;
if(values.find(wantedDifference) != values.end())
{
hasCouple = true;
}
else
{
values.insert(node->val);
}
}
}

bool findTarget(TreeNode* root, int k) {

unordered_set<int> values{};
bool hasCouple = false;
dfsHasCouple(root, hasCouple, values, k);

return hasCouple;
}
};

Ankit Malhotra

unread,
May 5, 2024, 3:48:47 AMMay 5
to leetcod...@googlegroups.com
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
return findTargetRecur(root, k, new HashSet<Integer>());
}

public boolean findTargetRecur(TreeNode root, int k, Set<Integer> numSet) {
if(root == null) return false;

if(numSet.contains(k - root.val)) return true;
numSet.add(root.val);
return findTargetRecur(root.left, k, numSet) || findTargetRecur(root.right, k, numSet);
}
}

--
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/ad8f32c8-1f19-4b40-bd92-0d81b6b1bc2an%40googlegroups.com.


--
-Ankit M.

vinay

unread,
May 5, 2024, 6:34:28 PMMay 5
to leetcod...@googlegroups.com

So the idea here is if I know the total sum of the next level, then I could remove the combined sum of the child nodes that have the same parent, thereby obtaining the sum of cousins.

Time: o(n)
Space: o(L) L = number of nodes for a given level

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        //root always be 0
        root.val = 0;

        Deque<TreeNode> queue  = new ArrayDeque<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            //calculate the total sum of each level
            // final values of nodes with parent A will then be > sum - (sum of all nodes that have parent A)
            int sum = 0;
            // this will keep track of each parent with which we are able to
            // update this child's cousin's value
            List<TreeNode> list = new ArrayList<>();

            for(int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                if(cur.left != null){
                    sum += cur.left.val;
                }
                if(cur.right != null){
                    sum += cur.right.val;
                }

                list.add(cur);
            }

           
// for all the tracked parents in the order, update their child's value with sum of cousins
for(TreeNode parent : list){
                int levelSum = sum;

                if(parent.left != null){
                    levelSum -= parent.left.val;
                    queue.offer(parent.left);
                }

                if(parent.right != null){
                    levelSum -= parent.right.val;
                    queue.offer(parent.right);
                }


                //update the values

                if(parent.left != null){
                   parent.left.val = levelSum;
                }

                if(parent.right != null){
                    parent.right.val = levelSum;
                }


            }
        }

        return root;
    }
}


--
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.
Reply all
Reply to author
Forward
0 new messages