2020 May 16 Questions

75 views
Skip to first unread message

Daryl Wang

unread,
May 16, 2020, 12:05:18 PM5/16/20
to leetcode-meetup
Please work on the problems at home and post your responses to the thread. I'll be hosting a Zoom session next Saturday to answer questions about these problems.



57244.0%Easy

126862.0%Medium


9938.5%Hard

suburban House

unread,
May 16, 2020, 1:05:48 PM5/16/20
to leetcode-meetup
is there a zoom link?
Message has been deleted

Jigar Shah

unread,
May 16, 2020, 3:23:37 PM5/16/20
to leetcode-meetup
```
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(s *TreeNode, t *TreeNode) bool {
    if t == nil {
        return true
    }
    
    if s == nil {
        return false
    }
    
    // PreOrder traversal
    // At C) Check if the head match for both trees, then check if they are identical
    // At L & R) Check with s Left subtree with t, r Right subtree with t
    if s.Val == t.Val && areIdentical(s, t) {
        return true
    }
    // Keep checkig Tree on L or R subtree
    return (isSubtree(s.Left, t) || isSubtree(s.Right, t))
    
}

func areIdentical(s *TreeNode, t *TreeNode) bool {
    if s == nil && t == nil {
        return true
    }
    
    if s == nil || t == nil {
        return false
    }
    
    // PreOrder Traversal
    // Constrant for C) values of s and t should be same
    // Same constraint for L & R) L & R subtree should be same
    if s.Val != t.Val {
        return false
    }
    
    return areIdentical(s.Left, t.Left) && areIdentical(s.Right, t.Right)
    
}
```

rakesh katkam

unread,
May 16, 2020, 3:38:36 PM5/16/20
to leetcode-meetup
Subtree of Another Tree
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        stack = []
        stack.append(s)
        while stack:
            currNode = stack.pop()
            if currNode.val == t.val and self.isSameTree(currNode,t):
                return True
            if currNode.left:
                stack.append(currNode.left)
            if currNode.right:
                stack.append(currNode.right)
            
        return False
    
    def isSameTree(self, s, t):
        q1 = deque([s])
        q2 = deque([t])
        while q1 and q2:
            n1 = q1.popleft()
            n2 = q2.popleft()
            if n1.val != n2.val:
                return False
            if n1.left:
                q1.append(n1.left)
            if n1.right:
                q1.append(n1.right)
            if n2.left:
                q2.append(n2.left)
            if n2.right:
                q2.append(n2.right)
                
        return not q1 and not q2


On Saturday, 16 May 2020 09:05:18 UTC-7, Daryl Wang wrote:

Jigar Shah

unread,
May 16, 2020, 3:56:07 PM5/16/20
to leetcode-meetup
126862.0%Medium

``` 
class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        root = Trie()
        for product in sorted(products):
            root.insert(product)
        
        
        ans = root.search(searchWord)
        return ans        

class TrieNode:
    def __init__(self):
        self.children = {}  # {char -> TrieNode (Subtree)}
        self.isEndOfWord = False
        self.sug = []
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, product):
        crawl = self.root
        for c in product:
            if c not in crawl.children:
                crawl.children[c] = TrieNode()
            
            # Crawl down for next char
            crawl = crawl.children[c]
            # Suggestion at each level
            if len(crawl.sug) < 3:
                crawl.sug.append(product) 
        
        crawl.isEndOfWord = True
        
    def search(self, searchWord):
        ans = []
        crawl = self.root
        for c in searchWord:
            if crawl:
                crawl = crawl.children.get(c, None)
            ans.append(crawl.sug if crawl else [])
            
        return ans 
```

Punit Salian

unread,
May 16, 2020, 4:16:24 PM5/16/20
to leetcod...@googlegroups.com
1268.          Search Suggestions System      62.0%Medium

class Trie {
 public:
  bool endofword;
  Trie** dictmap;
  Trie() {
    endofword = false;
    dictmap = new Trie*[26]();
  }
  ~Trie() { delete[] dictmap; }
};

class Solution {
  Trie* root;

 public:
  Solution() {
    root = new Trie();  // new root trie node
  }

  // create trie
  void createtrie(vector<string>& products) {
    Trie* currroot;
    // loop through each word
    for (auto& w : products) {
      // loop through each char
      currroot = root;  // reset afer each word

      for (auto& c : w) {
        // if NULL its the value new path
        // creata new trie node
        if (currroot->dictmap[c - 'a'] == NULL) {
          Trie* temp = new Trie();
          currroot-> dictmap[c - 'a'] = temp;
          currroot = temp;
        } else {
          currroot = currroot->dictmap[c - 'a'];
        }
        // if last char mark endof word true
      }
      currroot-> endofword = true;
    }
  }

  // simulated typing

  // find the next trie node of the word typed till now if any letter not dfound
  // return false

  Trie* nextxtrieNode(string typed) {
    Trie* currroot = root;

    for (int i = 0; i < typed.length(); i++) {
      Trie* temp = currroot->dictmap[typed[i] - 'a'];
      if (temp != NULL) {
        currroot = temp;
      } else {
        return temp;
      }
    }

    return currroot;
  }

  // use the above node to form the word
  bool autocomplete(Trie* curroot, string words, vector<string>& v) {
    // resurse on the current node
    // if vector size 3 return
    if (v.size() == 3) {
      return true;
    }

    // if end of word add it the vector
    if (curroot->endofword) {
      v.push_back(words);
    }

    // loop through the trie array sequentilly so lexicographically sorted
    for (int i = 0; i < 26; i++) {
      if (curroot-> dictmap[i] != NULL) {
        char temp = 'a' + i;
        if (autocomplete(curroot-> dictmap[i], words + temp, v)) return true;
      }
    }

    return false;
  }

  vector<vector<string>> suggestedProducts(vector<string>& products,
                                           string searchWord) {
    vector<vector<string>> result;
    // suggesed product
    vector<string> v;
    // creae a trie with products
    createtrie(products);
    string word = "";
    // simulate typing;
    for (int i = 0; i < searchWord.length(); i++) {
      word += searchWord[i];
      // cout << temp << endl;
      Trie* curr = nextxtrieNode(word);
      if (curr == NULL) {
        result.push_back(v);
        continue;
      }

      autocomplete(curr, word, v);

      result.push_back(v);
      v.clear();
    }

    return result;
  }
};

--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
 
https://www.techbayarea.us/
 
whatsapp group : https://chat.whatsapp.com/GxL7anhP9swEWgAsntkrm8
---
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/0c1afcbe-857c-474c-b263-aec3b79c5edd%40googlegroups.com.

Bhavya

unread,
May 16, 2020, 4:23:24 PM5/16/20
to leetcode-meetup
 * 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 isSubtree(TreeNode s, TreeNode t) {
        if (s==null && t==null)
            return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(s);
        while(!q.isEmpty()){
            TreeNode temp = q.poll();
            if (s != null && temp.val == t.val){
                boolean retVal = compareTree(temp,t);
                if (retVal) {
                    return true;
                }
            }
            if (temp.left!=null){
                q.add(temp.left);
            }
            if (temp.right!=null){
                q.add(temp.right);
            }
            
        }
        return false;
        
    }
    
    public boolean compareTree(TreeNode s, TreeNode t){
        if (s == null && t == null)
            return true;
        if (s== null){
            return false;
        }
        if (t==null)
            return false;
        if (s.val == t.val) {
            return compareTree(s.left,t.left) && compareTree(s.right,t.right);
        }
        return false;
    }
}

On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:

rakesh katkam

unread,
May 16, 2020, 4:29:08 PM5/16/20
to leetcode-meetup
What is the time complexity of this algorithm?

rakesh katkam

unread,
May 16, 2020, 5:51:42 PM5/16/20
to leetcode-meetup
class Solution(object):
    def suggestedProducts(self, products, searchWord):
        """
        :type products: List[str]
        :type searchWord: str
        :rtype: List[List[str]]
        """
        products.sort()
        searchString = ""
        results = []
        i = 1
        while i <= len(searchWord):
            searchString = searchWord[:i]
            wordlist = []
            for word in products:
                if searchString == word[:i]:
                    wordlist.append(word)
            results.append(wordlist[:3])
            products = wordlist
            i += 1
        return results

Tarini Pattanaik

unread,
May 17, 2020, 1:57:44 AM5/17/20
to leetcod...@googlegroups.com
572. Subtree of Another Tree

Runtime: 5 ms, faster than 96.49% of Java online submissions for Subtree of Another Tree.

public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null && t == null)
            return true;

        if (isIdentical(s, t))
            return true;

        if (s.left != null && isSubtree(s.left, t))
            return true;

         if (s.right != null && isSubtree(s.right, t))
            return true;

        return false;

    }

    boolean isIdentical(TreeNode node1, TreeNode node2) {
        if (node1 == node2)
            return true;

        if ((node1 == null || node2 == null))
            return false;

        if (node1.val != node2.val)
            return false;

        return (isIdentical(node1.left, node2.left) &&
               isIdentical(node1.right, node2.right));
    }

--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
 
https://www.techbayarea.us/
 
whatsapp group : https://chat.whatsapp.com/GxL7anhP9swEWgAsntkrm8
---
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/20031305-cb28-445c-8e74-ff297b318409%40googlegroups.com.

Tarini Pattanaik

unread,
May 17, 2020, 2:40:00 AM5/17/20
to leetcod...@googlegroups.com
1268. Search Suggestions System

Runtime: 1289 ms, faster than 5.07% of Java online submissions for Search Suggestions System.
 public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        if (products.length == 0)
            return new LinkedList<List<String>>();
       
        Map<String, List<String>> map = new HashMap<String, List<String>>();
       
        for (String product: products) {
            for(int i = 0; i < product.length(); i++) {
                String str = product.substring(0, i+1);
                List<String> list = map.getOrDefault(str, null);
               
                if (list == null) {
                    List<String> newlist = new LinkedList<String>();
                    map.put(str, newlist);
                    list = map.getOrDefault(str, null);
                }
               
                list.add(product);
                Collections.sort(list);
                //System.out.println("adding to map, str = " + str + ", l size" + list.size() );
               
                map.put(str, list);
            }
        }
       
        List<List<String>> retList = new LinkedList<List<String>>();

       
        for (int i = 0; i < searchWord.length(); i++) {
             String str = searchWord.substring(0, i+1);
            List<String> list = map.getOrDefault(str, new LinkedList<String>());
            //int size = list.size();
           
            //System.out.println("size = " + size);
            if (list.size() > 3) {
                int size = list.size();
                for (int j = 0; j < size -3; j++) {
                    list.remove(3);
                    //System.out.println("22size = " + list.size());
                }
            }
           
            //System.out.println("size-1 = " + list.size());
           
            retList.add(list);
        }
       
        return retList;
    }

Abhishek Kaukuntla

unread,
May 18, 2020, 1:16:48 AM5/18/20
to leetcode-meetup

Runtime: 55 ms, faster than 24.39% of Java online submissions for Search Suggestions System.
Memory Usage: 47.5 MB, less than 100.00% of Java online submissions for Search Suggestions System.


class Solution {
    // Date: 05/17/2020
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> result = new ArrayList<List<String>>();
        
        if (searchWord == null || searchWord.trim().length() == 0) {
            return result;
        }
        
        int maxLimit = 3;
        
        // Initialize the dictionary
        Map<String, List<String>> dict = new HashMap<String, List<String>>();
        dict.put("", new ArrayList<String>());
        
        // Build the dictionary
        buildDictionary(products, dict, maxLimit);
        
        // Build the result set
        for (int i=0; i<searchWord.length(); i++) {
            String key = searchWord.substring(0, i+1);
            result.add(dict.getOrDefault(key, new ArrayList<String>()));
        }
        
        return result;
        
    }
    
    private void buildDictionary(String[] products, Map<String, List<String>> dict, int maxLimit) {
        
        for (String prod : products) {
            
            for (int i=0; i<prod.length(); i++) {
                
                String key = prod.substring(0, i+1);
                
                List<String> sortedProducts = null;
                if (dict.containsKey(key)) {
                    sortedProducts = sort(dict.get(key), prod, maxLimit);
                    dict.put(key, sortedProducts);
                    
                } else {
                    sortedProducts = new ArrayList<String>();
                    sortedProducts.add(prod);
                    dict.put(key, sortedProducts);
                }
            }
        }
    }
    
    private List<String> sort(List<String> products, String prod, int maxLimit) {
        
        if (products.isEmpty()) {
            products.add(prod);
        } else {
            int i=0;
            while(i < maxLimit && i < products.size()) {
                if (products.get(i) == null) {
                    break;
                }
                if(prod.compareTo(products.get(i)) < 0) {
                    products.add(i, prod);
                    i = maxLimit;
                    break;
                }
                i++;
            }
            if (i < maxLimit) {
                products.add(i, prod);
            }
            
            resize(products, maxLimit);
        }
        
        
        return products;
    }
    
    private void resize(List<String> products, int maxLimit) {
        while (products.size() > maxLimit) {
            products.remove(maxLimit);
        }
    }
}



On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:

Promila Agarwal

unread,
May 20, 2020, 3:27:24 AM5/20/20
to leetcod...@googlegroups.com
# 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 isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        def isEqual(s:TreeNode, t:TreeNode) -> bool:
            if s == None and t == None:
                return True
            if s == None or t == None:
                return False
            return s.val == t.val and isEqual(s.left, t.left) and isEqual(s.right,t.right)

        return s!= None and (isEqual(s,t) or self.isSubtree(s.left, t) or self.isSubtree(s.right,t))

--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
 
https://www.techbayarea.us/
 
whatsapp group : https://chat.whatsapp.com/GxL7anhP9swEWgAsntkrm8
---
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/bd705979-52a2-49e1-822f-01f0878e0fb1%40googlegroups.com.

karan alang

unread,
May 20, 2020, 8:24:01 PM5/20/20
to leetcode-meetup
lc572 :

def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        
        if not s and not t:
            return True
        if not s or not t:
            return False
        
        return self.isIdentical(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    
    def isIdentical(self, s: TreeNode, t: TreeNode):
        
        if not s and not t:
            return True
        
        if not s or not t:
            return False
        
        return s.val == t.val and self.isIdentical(s.left, t.left) and self.isIdentical(s.right, t.right)


On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:

Abhishek Kaukuntla

unread,
May 21, 2020, 2:07:15 AM5/21/20
to leetcode-meetup
99Recover Binary Search Tree    38.5%Hard

Runtime: 2 ms, faster than 77.43% of Java online submissions for Recover Binary Search Tree.
Memory Usage: 39.9 MB, less than 80.77% of Java online submissions for Recover Binary Search Tree.

Time complexity: O(N) where N is the number of nodes in BST
Space complexity: O(1)



/**
 * 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 void recoverTree(TreeNode root) {
        TreeNode current = root;
        TreeNode first = null, second = null, prev = new TreeNode(Integer.MIN_VALUE);
        
        while (current != null) {
            if (current.left == null) { // if the left node is null then current node needs to be visited
                
                // Time to check if the current is out of place
                if (prev != null && prev.val > current.val) {
                    if (first == null) {
                        first = prev;    
                    }
                    second = current;
                }
                prev = current;
                
                current = current.right; 
                
                
            } else {
                // find the predecessor of the current node (it is the right most node to current)
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right; // keep on going to the right
                }
                
                if (predecessor.right == null) { // we build the link to current node from here
                    predecessor.right = current;
                    current = current.left; // we can move to the left now that we know how to get to the current
                    
                } else { // predecessor.right = current which means we have already visited this subtree
                    predecessor.right = null; // reset the link
                    
                    // Time to check if the current is out of place                    
                    if (prev != null && prev.val > current.val) {
                        if (first == null) {
                            first = prev;    
                        }
                        second = current;
                    }
                    prev = current;
                    
                    current = current.right;
                    
                }
            }
        }
        
        // Now swap the out of place nodes
        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;

Priyank Gupta

unread,
May 22, 2020, 10:48:05 PM5/22/20
to leetcode-meetup


On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:
Please work on the problems at home and post your responses to the thread. I'll be hosting a Zoom session next Saturday to answer questions about these problems.



57244.0%Easy
Runtime: 276 ms, faster than 30.08% of Python3 online submissions for Subtree of Another Tree.
Memory Usage: 14.4 MB, less than 50.00% of Python3 online submissions for Subtree of Another Tree.
# 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 isSame(self, root1, root2):
        if root1 == None and root2 == None:
            return True
        if root1 != None and root2 != None:
            if root1.val == root2.val:
                return self.isSame(root1.left, root2.left) and self.isSame(root1.right, root2.right)
        return False
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if s == None:
            return False
        if s.val == t.val:
            if self.isSame(s,t):
                return True
        return self.isSubtree(s.left,t) or self.isSubtree(s.right,t)

Priyank Gupta

unread,
May 22, 2020, 10:49:41 PM5/22/20
to leetcode-meetup


On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:
Please work on the problems at home and post your responses to the thread. I'll be hosting a Zoom session next Saturday to answer questions about these problems.




126862.0%Medium
Runtime: 108 ms, faster than 66.70% of Python3 online submissions for Search Suggestions System.
Memory Usage: 16.4 MB, less than 100.00% of Python3 online submissions for Search Suggestions System.

'''
This problem can be solved using binary search, sort the products and then find the index where searchWord is getting started each time user types searchWord, once we find the index we have to find the next 3 elements which satisfy searchWord.
'''
# Time : O(k*LogN) k -> len(searchWord), N -> len(products)
# Space : 



class Solution:
    
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        
        res = []
        for i in range(len(searchWord)):
            local = []
            lo = 0
            hi = len(products)-1
            while(hi - lo > 1):
                mid = int((lo+hi)/2)
                if products[mid][:i+1] == searchWord[:i+1]:
                    hi = mid
                elif products[mid][:i+1] > searchWord[:i+1]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            if products[lo][:i+1] == searchWord[:i+1]:
                count = 0
                k = lo
                while(k <= len(products)-1 and products[k][:i+1] == searchWord[:i+1] and count != 3):
                    local.append(products[k])
                    k += 1
                    count += 1
                res.append(local)
            else:
                count = 0
                k = hi
                while(products[k][:i+1] == searchWord[:i+1] and count != 3):
                    local.append(products[k])
                    k += 1
                    count += 1
                res.append(local)
        return res
                
                    

Daryl Wang

unread,
May 23, 2020, 12:55:37 PM5/23/20
to leetcode-meetup
572Subtree of Another Tree    44.0%Easy

This is a simple recursive solution. It is straightforward to write a helper function that checks if two trees are the same. The algorithm is then to:
1) Check if the root of s is the same tree as t
2) Recursively call isSubtree on the children of s if the check in step 1 returned false.

O(s*t) time
O(s) space

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and t:
            return False
        def sameTree(tree1, tree2):
            if not tree1 and not tree2:
                return True
            if (tree1 and not tree2) or (not tree1 and tree2):
                return False
            return tree1.val == tree2.val and sameTree(tree1.left, tree2.left) and sameTree(tree1.right, tree2.right)
        return sameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)


On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,
May 23, 2020, 2:21:56 PM5/23/20
to leetcode-meetup
1268Search Suggestions System    62.0%Medium

The usual solution for word search problems is to use a trie. That is a working approach to this problem, but the question is a little more complication in checking for the existence of a match is not enough, you also need to return the first 3 matches. This requires either walking down the trie tree to look for 3 words, or adding a list of potentially matching words to each trie node.

A simpler solution is to maintain a list of possibly matching words and trim it down as we advance through the searchWord. We create a sorted list of the products. Then we can iterate through the searchWord and check the first 3 words in the product list to see if they match. If they don't, we keep popping off words until we find one that matches or the product list is empty. The fact that we need to return 3 matches creates an edge case where there is only 1 or 2 matches; in this case the front of the product list needs to stay but the remaining products need to be popped.
This Python code uses a deque, but the underlying implementation is just an array with left and right pointers. The basic loop for each letter in searchWord is:
1) Pop off words from the front of the product list that don't match the current letter. (This is just incrementing the left pointer)
2) Pop off words from the back of the product list that don't match the current letter. (This is just decrementing the right pointer)
3) Return the first 3 words in the remaining product list. 

O(s + p log(p)) time, where s is the length of searchWord and p is the length of products
O(p) space, not counting the space taken up by the result list

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        matches = collections.deque(sorted(products), len(products))
        result = []
        for ind in range(len(searchWord)):
            while matches and (ind >= len(matches[0]) or matches[0][ind] != searchWord[ind]):
                matches.popleft()
            while matches and (ind >= len(matches[-1]) or matches[-1][ind] != searchWord[ind]):
                matches.pop()
            cur_result = []
            for i in range(min(3, len(matches))):
                cur_result.append(matches[i])
            result.append(cur_result)
        return result

On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,
May 23, 2020, 3:07:17 PM5/23/20
to leetcode-meetup
99Recover Binary Search Tree    38.5%Hard

The basic idea for this problem is to do an in-order traversal of the tree. If we see a node B smaller than its predecessor A in the in-order traversal, then we know that one of the nodes is the swapped nodes. The first time this happens, we know that A is one of the swapped nodes. The second time we know that B is the swapped node. There is one edge case where we only see one such mismatch during the traversal. In that case, both nodes are the swapped node.
Example 1 from the problem:
In-order traversal: 3 2 1
3 > 2: 3 is one of the swapped nodes
2 > 1: 1 is the other swapped node

Example 2 from the problem:
In-order traversal: 1 3 2 4
3 > 2: both 3 and 2 are the swapped nodes.


The followup is to do this in constant space. A recursive traversal technically requires O(height of tree) for the stack, so the answer is to use the Morris in-order traversal. The basic idea is have the right pointer of leaf nodes point to the next node in the in-order traversal.

O(n) time
O(1) space

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        node1 = None
        node2 = None
        current = root
        preceding = None
        while current:
            # We've discovered two nodes that are out of order.
            if preceding and preceding.val > current.val:
                if not node1:
                    node1 = preceding
                node2 = current
            if current.left:
                prev = current.left
                # Go as far right down current's left subtree to find the node that goes right before current in a in-order traversal
                while prev.right and prev.right != current:
                    prev = prev.right
                if prev.right:
                    assert prev.right == current, "We should have ended with a pointer from the root's preceding node to the root"
                    # Erase the thread we added before
                    prev.right = None
                    preceding = current
                    # Move onto current's right subtree
                    current = current.right
                else:
                    # Have the preceding node point to root
                    prev.right = current
                    # Check the preceding nodes for the left subtree
                    current = current.left
            else:
                # Check preceding nodes for the right subtree
                preceding = current
                current = current.right
        if node1 and node2:
            node1.val, node2.val = node2.val, node1.val

On Saturday, May 16, 2020 at 9:05:18 AM UTC-7, Daryl Wang wrote:
Reply all
Reply to author
Forward
0 new messages