acash's blog

By acash, history, 5 months ago, In English,

problem link:Leetcode

problem:Given a binary tree, return the vertical order traversal of its nodes values.

This approah is using unorederd_map and i think it is nlog(n) due to n for loop and log(n) for find operation in it.Is it correct?

Traverse the tree tracking x and y coordinates, and populate m[x][y] with values. Note that we use set to hold multiple values and sorts them automatically.

Then, we iterate x [-999, 999] and y [0, 999] and populate our answer. Since the tree size is limited to 1000, our coordinates will be within these intervals.

unordered_map<int, unordered_map<int, set<int>>> m;
void traverse(TreeNode* r, int x, int y) {
  if (r != nullptr) {
    m[x][y].insert(r->val);
    traverse(r->left, x - 1, y + 1);
    traverse(r->right, x + 1, y + 1);
  }
}
vector<vector<int>> verticalTraversal(TreeNode* r) {
  vector<vector<int>> res;
  traverse(r, 0, 0);
  for (int x = -999; x < 1000; ++x) {
    auto it = m.find(x);
    if (it != end(m)) {
      res.push_back(vector<int>());
      for (int y = 0; y < 1000; ++y) {
        auto ity = it->second.find(y);
        if (ity != end(it->second)) {
          res.back().insert(end(res.back()), begin(ity->second), end(ity->second));
        }
      }
    }
  }
  return res;
}

This approach is using map ,I don't know time complexity of this one

We could also use map[x, map[y, set[val]]], and it will simplify the code a bit:

void dfs(TreeNode* r, int x, int y, map<int, map<int, set<int>>> &m) {
  if (r != nullptr) {
    m[x][y].insert(r->val);
    dfs(r->left, x - 1, y + 1, m);
    dfs(r->right, x + 1, y + 1, m);
  }
}
vector<vector<int>> verticalTraversal(TreeNode* r, vector<vector<int>> res = {}) {
  map<int, map<int, set<int>>> m;
  dfs(r, 0, 0, m);
  for (auto itx = m.begin(); itx != m.end(); ++itx) {
      res.push_back(vector<int>());
      for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
          res.back().insert(end(res.back()), begin(ity->second), end(ity->second));
      }
  }
  return res;
}
 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please help someone tomorrow is my interview

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lol. If tomorrow is your interview, I pray that these pieces of code wasn't written by you, otherwise, you are going to fail the interview (because this code is unreadable and it is unnecessarily complex. It is difficult to discern what are the magic numbers -999 and 1000 (I am not going to read the source, it ought to be obvious from your code).

    To answer your post, all I can say is, try rewriting the code in a simpler way. Then analyze its time complexity.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro I just explained my program can you help me this time complexity

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by acash (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Are you trying to find the worst case? If yes then you are wrong. Unordered map has the best case complexity of O(1) and the worst case complexity of O(n). Map has O(logn) in both cases. And Set has the worst case complexity of O(logn). I don't think you need the full answer just consider these things and use your brain. :)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am confused in second one map<int,map<int,set>> here

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Suppose I am using map<int, vector>. Now, look here the key is an integer. And the value is a vector. When you type in v[1].push_back(1) it works just like a normal vector push. Which has a complexity of O(1) and when you are calling v[1] in a map it is going to have a complexity of O(logn). So basically we can say it has a complexity of O(logn). Even though not precisely. When you are using map<int, set> you are basically calling the value in O(logn) and then you are performing normal set operations in that value in O(logn) time mostly. It is as simple as that. Now I hope you will be able to calculate it. :)

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Please help someone I didn't get answer