วีดีโอ

class Solution { private: void pacificAtlantic(int i, int j, vector<vector<int>> &heights, vector<vector<bool>> &visited) { if (visited[i][j]) { return; } visited[i][j] = true; if (i + 1 < heights.size() && heights[i + 1][j] >= heights[i][j]) { pacificAtlantic(i + 1, j, heights, visited); } if (i - 1 >= 0 && heights[i - 1][j] >= heights[i][j]) { pacificAtlantic(i - 1, j, heights, visited); } if (j + 1 < heights[0].size() && heights[i][j + 1] >= heights[i][j]) { pacificAtlantic(i, j + 1, heights, visited); } if (j - 1 >= 0 && heights[i][j - 1] >= heights[i][j]) { pacificAtlantic(i, j - 1, heights, visited); } } public: vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { vector<vector<bool>> pacificVisited(heights.size(), vector<bool>(heights[0].size(), false)); vector<vector<bool>> atlanticVisited(heights.size(), vector<bool>(heights[0].size(), false)); for (int i = 0; i < heights.size(); i++) { pacificAtlantic(i, 0, heights, pacificVisited); pacificAtlantic(i, heights[0].size() - 1, heights, atlanticVisited); } for (int j = 0; j < heights[0].size(); j++) { pacificAtlantic(0, j, heights, pacificVisited); pacificAtlantic(heights.size() - 1, j, heights, atlanticVisited); } vector<vector<int>> res; for (int i = 0; i < heights.size(); i++) { for (int j = 0; j < heights[0].size(); j++) { if (pacificVisited[i][j] && atlanticVisited[i][j]) { res.push_back({ i, j }); } } } return res; } };

class Solution { public: int orangesRotting(vector<vector<int>>& grid) { vector<vector<int>> gridCopy = grid; int numFresh = 0; queue<pair<int, int>> q; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (gridCopy[i][j] == 2) { q.push({ i, j }); } else if (gridCopy[i][j] == 1) { numFresh++; } } } int numMinutes = -1; while (!q.empty()) { int lvlSize = q.size(); for (int k = 0; k < lvlSize; k++) { auto [i, j] = q.front(); q.pop(); if (i + 1 < grid.size() && gridCopy[i + 1][j] == 1) { gridCopy[i + 1][j] = 2; numFresh--; q.push({ i + 1, j }); } if (i - 1 >= 0 && gridCopy[i - 1][j] == 1) { gridCopy[i - 1][j] = 2; numFresh--; q.push({ i - 1, j }); } if (j + 1 < grid[0].size() && gridCopy[i][j + 1] == 1) { gridCopy[i][j + 1] = 2; numFresh--; q.push({ i, j + 1 }); } if (j - 1 >= 0 && gridCopy[i][j - 1] == 1) { gridCopy[i][j - 1] = 2; numFresh--; q.push({ i, j - 1 }); } } numMinutes++; } if (numFresh > 0) { return -1; } if (numMinutes == -1) { return 0; } return numMinutes; } };

class Solution { private: Node* cloneGraph(Node *node, unordered_map<Node*, Node*> &map) { if (map.find(node) != map.end()) { return map[node]; } map[node] = new Node(node->val); for (auto &neighbor : node->neighbors) { map[node]->neighbors.push_back(cloneGraph(neighbor, map)); } return map[node]; } public: Node* cloneGraph(Node* node) { if (!node) { return nullptr; } unordered_map<Node*, Node*> map; return cloneGraph(node, map); } };

class Solution { private: int findArea(int i, int j, vector<vector<bool>> &visited, vector<vector<int>> &grid) { if (!grid[i][j] || visited[i][j]) { return 0; } visited[i][j] = true; int thisArea = 1; if (i + 1 < grid.size()) { thisArea += findArea(i + 1, j, visited, grid); } if (i - 1 >= 0) { thisArea += findArea(i - 1, j, visited, grid); } if (j + 1 < grid[0].size()) { thisArea += findArea(i, j + 1, visited, grid); } if (j - 1 >= 0) { thisArea += findArea(i, j - 1, visited, grid); } return thisArea; } public: int maxAreaOfIsland(vector<vector<int>>& grid) { vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false)); int maxArea = 0; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { maxArea = max(findArea(i, j, visited, grid), maxArea); } } return maxArea; } };

class Solution { private: void floodFill(int i, int j, vector<vector<char>> &grid, vector<vector<bool>> &visited) { if (grid[i][j] == '0' || visited[i][j]) { return; } visited[i][j] = true; if (i + 1 < grid.size()) { floodFill(i + 1, j, grid, visited); } if (i - 1 >= 0) { floodFill(i - 1, j, grid, visited); } if (j + 1 < grid[0].size()) { floodFill(i, j + 1, grid, visited); } if (j - 1 >= 0) { floodFill(i, j - 1, grid, visited); } } public: int numIslands(vector<vector<char>>& grid) { vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false)); int numIslands = 0; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == '1' && !visited[i][j]) { numIslands++; floodFill(i, j, grid, visited); } } } return numIslands; } };

Cracked

just find inorder and return the value at k-1 index

cracked explanation

class MedianFinder { private: priority_queue<int, vector<int>, greater<int>> minHeap; priority_queue<int, vector<int>> maxHeap; public: MedianFinder() { } void addNum(int num) { maxHeap.push(num); minHeap.push(maxHeap.top()); maxHeap.pop(); if (minHeap.size() > maxHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } } double findMedian() { if (maxHeap.size() > minHeap.size()) { return maxHeap.top(); } return ((double) minHeap.top() + (double) maxHeap.top()) / 2.0; } };

class Twitter { private: unordered_map<int, unordered_set<int>> following; unordered_map<int, vector<pair<int, int>>> tweets; int timestamp; struct Comparator { bool operator() (pair<int, int> &a, pair<int, int> &b) { return a.second > b.second; } }; public: Twitter() { timestamp = 0; } void postTweet(int userId, int tweetId) { tweets[userId].push_back({ tweetId, timestamp }); timestamp++; } vector<int> getNewsFeed(int userId) { priority_queue<pair<int, int>, vector<pair<int, int>>, Comparator> minHeap; // get tweets from following for (auto &followeeId : following[userId]) { for (auto &tweet : tweets[followeeId]) { minHeap.push(tweet); if (minHeap.size() > 10) { minHeap.pop(); } } } // get tweets from self for (auto &tweet : tweets[userId]) { minHeap.push(tweet); if (minHeap.size() > 10) { minHeap.pop(); } } // put the tweets into a vector, reverse vector<int> res; while (!minHeap.empty()) { res.push_back(minHeap.top().first); minHeap.pop(); } reverse(res.begin(), res.end()); return res; } void follow(int followerId, int followeeId) { following[followerId].insert(followeeId); } void unfollow(int followerId, int followeeId) { following[followerId].erase(followeeId); } };

class Solution { private: struct Comparator { bool operator() (pair<char, int> &a, pair<char, int> &b) { return a.second < b.second; } }; public: int leastInterval(vector<char>& tasks, int n) { unordered_map<char, int> freq; for (auto &task : tasks) { freq[task]++; } priority_queue<pair<char, int>, vector<pair<char, int>>, Comparator> maxHeap; for (auto &kv : freq) { maxHeap.push({ kv.first, kv.second }); } // task, freq. remaining, interval ready queue<tuple<char, int, int>> q; int intervals = 0; while (!maxHeap.empty() || !q.empty()) { // put tasks finished with cooldown back in heap if (!q.empty()) { auto [task, remaining, interval] = q.front(); if (interval == intervals) { maxHeap.push({ task, remaining }); q.pop(); } } if (maxHeap.empty()) { intervals++; continue; } // do the next task auto [task, remaining] = maxHeap.top(); maxHeap.pop(); remaining--; if (remaining > 0 && n > 0) { q.push(make_tuple(task, remaining, intervals + n + 1)); } else if (remaining > 0) { maxHeap.push({ task, remaining }); } intervals++; } return intervals; } };

class Solution { private: int partition(vector<int> &nums, int l, int r) { int pivot = nums[l]; int begin = l; l++; while (l <= r) { if (pivot > nums[l] && pivot < nums[r]) { swap(nums[l], nums[r]); l++; r--; } if (pivot <= nums[l]) { l++; } if (pivot >= nums[r]) { r--; } } swap(nums[begin], nums[r]); return r; } public: int findKthLargest(vector<int>& nums, int k) { int l = 0; int r = nums.size() - 1; int res; while (true) { int i = partition(nums, l, r); if (i == k - 1) { res = nums[i]; break; } if (i < k - 1) { l = i + 1; } else { r = i - 1; } } return res; } };

class Solution { private: static double getDistanceFromOrigin(vector<int> &a) { return sqrt((a[0] * a[0]) + (a[1] * a[1])); } struct Comparator { bool operator() (vector<int> &a, vector<int> &b) { return getDistanceFromOrigin(a) < getDistanceFromOrigin(b); } }; public: vector<vector<int>> kClosest(vector<vector<int>>& points, int k) { priority_queue<vector<int>, vector<vector<int>>, Comparator> maxHeap; for (auto &point : points) { maxHeap.push(point); if (maxHeap.size() > k) { maxHeap.pop(); } } vector<vector<int>> res; while (!maxHeap.empty()) { res.push_back(maxHeap.top()); maxHeap.pop(); } return res; } };

class Solution { public: int lastStoneWeight(vector<int>& stones) { priority_queue<int, vector<int>> maxHeap; for (const int &stone : stones) { maxHeap.push(stone); } while (maxHeap.size() > 1) { int stone1 = maxHeap.top(); maxHeap.pop(); int stone2 = maxHeap.top(); maxHeap.pop(); if (stone1 != stone2) { maxHeap.push(stone1 - stone2); } } return maxHeap.empty() ? 0 : maxHeap.top(); } };

class KthLargest { private: int k; priority_queue<int, vector<int>, greater<int>> minHeap; public: KthLargest(int k, vector<int>& nums) { this->k = k; for (const int &num : nums) { this->add(num); } } int add(int val) { minHeap.push(val); if (minHeap.size() > k) { minHeap.pop(); } return minHeap.top(); } };

class Solution { private: void solveNQueens(int i, vector<vector<string>> &res, vector<string> &board, unordered_set<int> &cols, unordered_set<int> &diag45, unordered_set<int> &diag135) { if (i == board.size()) { res.push_back(board); return; } for (int j = 0; j < board[0].size(); j++) { // skip column? if (cols.contains(j) || diag45.contains(i + j) || diag135.contains(i - j)) { continue; } // add cols.insert(j); diag45.insert(i + j); diag135.insert(i - j); board[i][j] = 'Q'; // recursion solveNQueens(i + 1, res, board, cols, diag45, diag135); // backtrack cols.erase(j); diag45.erase(i + j); diag135.erase(i - j); board[i][j] = '.'; } } public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> res; vector<string> board(n, string(n, '.')); unordered_set<int> cols; unordered_set<int> diag45; unordered_set<int> diag135; solveNQueens(0, res, board, cols, diag45, diag135); return res; } };

class Solution { private: void letterCombinations(int i, string s, string &digits, vector<string> &res, unordered_map<char, string> &map) { if (s.length() == digits.length()) { res.push_back(s); return; } string options = map[digits[i]]; for (auto &c : options) { s.push_back(c); letterCombinations(i + 1, s, digits, res, map); s.pop_back(); } } public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.length() == 0) { return res; } unordered_map<char, string> map; map['2'] = "abc"; map['3'] = "def"; map['4'] = "ghi"; map['5'] = "jkl"; map['6'] = "mno"; map['7'] = "pqrs"; map['8'] = "tuv"; map['9'] = "wxyz"; letterCombinations(0, "", digits, res, map); return res; } };

class Solution { private: bool isPalindrome(const string &s, int l, int r) { // T: O(n), S: O(1) while (l < r) { if (s[l] != s[r]) { return false; } l++; r--; } return true; } void partition(int i, string &s, vector<string> &par, vector<vector<string>> &res) { if (i == s.length()) { res.push_back(par); return; } for (int j = i; j < s.length(); j++) { if (isPalindrome(s, i, j)) { par.push_back(s.substr(i, j - i + 1)); partition(j + 1, s, par, res); par.pop_back(); } } } public: vector<vector<string>> partition(string s) { // T: O(n(2^n)), S: O(n) - auxiliary space only vector<vector<string>> res; vector<string> par; partition(0, s, par, res); return res; } };

Hey, it was great explanation.

class Solution { private: bool dfs(int pos, int i, int j, string &word, vector<vector<char>> &board) { char c = board[i][j]; if (c == '#') { return false; } if (pos >= word.size() || c != word[pos]) { return false; } if (pos == word.size() - 1 && c == word[pos]) { return true; } pos++; board[i][j] = '#'; if (i + 1 < board.size() && dfs(pos, i + 1, j, word, board)) { return true; } if (i - 1 >= 0 && dfs(pos, i - 1, j, word, board)) { return true; } if (j + 1 < board[0].size() && dfs(pos, i, j + 1, word, board)) { return true; } if (j - 1 >= 0 && dfs(pos, i, j - 1, word, board)) { return true; } board[i][j] = c; return false; } public: bool exist(vector<vector<char>>& board, string word) { for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[0].size(); j++) { if (dfs(0, i, j, word, board)) { return true; } } } return false; } };

class Solution { private: void combinationSum2(int i, int target, vector<int> &combo, vector<vector<int>> &res, vector<int> &candidates) { if (target == 0) { res.push_back(combo); return; } for (int j = i; j < candidates.size(); j++) { if (j > i && candidates[j] == candidates[j - 1]) { continue; } if (target - candidates[j] >= 0) { combo.push_back(candidates[j]); combinationSum2(j + 1, target - candidates[j], combo, res, candidates); combo.pop_back(); } } } public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector<vector<int>> res; vector<int> combo; combinationSum2(0, target, combo, res, candidates); return res; } };

class Solution { private: void subsetsWithDup(vector<vector<int>> &res, vector<int> &subset, vector<int> &nums, int i) { res.push_back(subset); for (int j = i; j < nums.size(); j++) { if (j > i && nums[j] == nums[j - 1]) { continue; } subset.push_back(nums[j]); subsetsWithDup(res, subset, nums, j + 1); subset.pop_back(); } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res(0); vector<int> subset(0); subsetsWithDup(res, subset, nums, 0); return res; } };

class Solution { private: void permute(vector<vector<int>> &res, vector<int> &perm, vector<int> &nums) { if (perm.size() == nums.size()) { res.push_back(perm); return; } for (int i = 0; i < nums.size(); i++) { if (find(perm.begin(), perm.end(), nums[i]) != perm.end()) { continue; } perm.push_back(nums[i]); permute(res, perm, nums); perm.pop_back(); } } public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res(0); vector<int> perm(0); permute(res, perm, nums); return res; } };

class Solution { private: void combinationSum(vector<vector<int>> &res, vector<int> &combo, vector<int> &candidates, int i, int target) { if (target == 0) { res.push_back(combo); return; } for (int j = i; j < candidates.size(); j++) { if (target - candidates[j] >= 0) { combo.push_back(candidates[j]); combinationSum(res, combo, candidates, j, target - candidates[j]); combo.pop_back(); } } } public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> res(0); vector<int> combo(0); combinationSum(res, combo, candidates, 0, target); return res; } };

class Solution { private: void subsets(vector<vector<int>> &res, vector<int> &subset, vector<int> &nums, int i) { res.push_back(subset); for (int j = i; j < nums.size(); j++) { subset.push_back(nums[j]); subsets(res, subset, nums, j + 1); subset.pop_back(); } } public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res(0); vector<int> subset(0); subsets(res, subset, nums, 0); return res; } };

The Volume is too less

struct TrieNode { TrieNode *children[26]; bool isWord; TrieNode() { for (auto &c : children) { c = nullptr; } isWord = false; } }; class Trie { private: TrieNode *root; void clear(TrieNode *tn) { for (auto &c : tn->children) { if (c) { clear(c); } } delete tn; } public: Trie() { root = new TrieNode(); } ~Trie() { this->clear(root); } void addWord(string s) { TrieNode *tn = root; for (auto &c : s) { if (!tn->children[c - 'a']) { tn->children[c - 'a'] = new TrieNode(); } tn = tn->children[c - 'a']; } tn->isWord = true; } TrieNode *getRoot() { return root; } }; class Solution { private: void dfs(vector<vector<char>> &board, vector<string> &res, int i, int j, TrieNode *tn, string word) { char c = board[i][j]; if (c == '#') { return; } tn = tn->children[c - 'a']; if (!tn) { return; } word += c; if (tn->isWord) { res.push_back(word); tn->isWord = false; } board[i][j] = '#'; if (i + 1 < board.size()) { dfs(board, res, i + 1, j, tn, word); } if (i - 1 >= 0) { dfs(board, res, i - 1, j, tn, word); } if (j + 1 < board[0].size()) { dfs(board, res, i, j + 1, tn, word); } if (j - 1 >= 0) { dfs(board, res, i, j - 1, tn, word); } board[i][j] = c; } public: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { Trie myTrie; for (auto &word : words) { myTrie.addWord(word); } vector<string> res; TrieNode *root = myTrie.getRoot(); for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[0].size(); j++) { dfs(board, res, i, j, root, ""); } } return res; } };

struct TrieNode { TrieNode *children[26]; bool isWord; TrieNode() { for (auto &c : children) { c = nullptr; } isWord = false; } }; class WordDictionary { private: TrieNode *root; void clear(TrieNode *tn) { for (int i = 0; i < 26; i++) { if (tn->children[i]) { clear(tn->children[i]); } } delete tn; } bool dfs(TrieNode *tn, string &s, int pos) { // TC: O(26^(min(n, h)), SC: O(min(n, h), n = length of word, h = height of tree if (pos == s.size()) { return tn->isWord; } if (s[pos] != '.') { tn = tn->children[s[pos] - 'a']; if (!tn) { return false; } return dfs(tn, s, pos + 1); } else { for (int i = 0; i < 26; i++) { if (tn->children[i] && dfs(tn->children[i], s, pos + 1)) { return true; } } return false; } } public: WordDictionary() { // overall data structure SC: O(M * N) M = avg length of word, N = total words root = new TrieNode(); } ~WordDictionary() { this->clear(root); } void addWord(string word) { // TC: O(n), SC: O(1) TrieNode *tn = root; for (auto &c : word) { if (!tn->children[c - 'a']) { tn->children[c - 'a'] = new TrieNode(); } tn = tn->children[c - 'a']; } tn->isWord = true; } bool search(string word) { return dfs(root, word, 0); } };

struct TrieNode { TrieNode *children[26]; bool isWord; TrieNode() { for (auto &c : children) { c = nullptr; } isWord = false; } }; class Trie { private: TrieNode *root; void clear(TrieNode *tn) { for (int i = 0; i < 26; i++) { if (tn->children[i]) { clear(tn->children[i]); } } delete tn; } TrieNode *find(string &s) { // TC: O(n), n = length of word TrieNode *tn = root; for (auto &c : s) { if (!tn->children[c - 'a']) { return nullptr; } tn = tn->children[c - 'a']; } return tn; } public: Trie() { // SC: O(M*N) M = average length of word, N = number of words root = new TrieNode(); } ~Trie() { clear(root); } void insert(string word) { // TC: O(n), n = length of word TrieNode *tn = root; for (auto &c : word) { if (!tn->children[c - 'a']) { tn->children[c - 'a'] = new TrieNode(); } tn = tn->children[c - 'a']; } tn->isWord = true; } bool search(string word) { TrieNode *end = find(word); if (end && end->isWord) { return true; } return false; } bool startsWith(string prefix) { if (find(prefix)) { return true; } return false; } };

class Solution { private: int getMaxGain(TreeNode *tn, int &maxPathSum) { if (!tn) { return 0; } int maxLeft = max(getMaxGain(tn->left, maxPathSum), 0); int maxRight = max(getMaxGain(tn->right, maxPathSum), 0); int curMaxPathSum = tn->val + maxLeft + maxRight; maxPathSum = max(maxPathSum, curMaxPathSum); return tn->val + max(maxLeft, maxRight); } public: int maxPathSum(TreeNode* root) { int maxPathSum = INT_MIN; getMaxGain(root, maxPathSum); return maxPathSum; } };

Bro what are the major topics covered to be covered in c++ for DSA

class Codec { private: void serDfs(TreeNode *tn, string &s) { if (!tn) { s.append(",#"); return; } else { s.append(","); s.append(to_string(tn->val)); } serDfs(tn->left, s); serDfs(tn->right, s); } TreeNode *deserDfs(string &s, int &i) { i++; string num; while (i < s.size() && s[i] != ',') { num += s[i]; i++; } if (num == "#") { return nullptr; } TreeNode *tn = new TreeNode(stoi(num)); tn->left = deserDfs(s, i); tn->right = deserDfs(s, i); return tn; } public: // Encodes a tree to a single string. string serialize(TreeNode* root) { // O(n) time, O(h) space string s; serDfs(root, s); return s; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { // O(n) time, O(h) space int i = 0; TreeNode *root = deserDfs(data, i); return root; } };

class Solution { private: TreeNode *build(vector<int> &preorder, vector<int> &inorder, unordered_map<int, int> &map, int pL, int pR, int iL, int iR) { if (pL > pR || iL > iR) { return nullptr; } TreeNode *tn = new TreeNode(preorder[pL]); int root = map[preorder[pL]]; int offset = root - iL; tn->left = build(preorder, inorder, map, pL + 1, pL + offset, iL, root - 1); tn->right = build(preorder, inorder, map, pL + offset + 1, pR, root + 1, iR); return tn; } public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { unordered_map<int, int> map; for (int i = 0; i < inorder.size(); i++) { map[inorder[i]] = i; } int lastIndex = preorder.size() - 1; TreeNode *root = build(preorder, inorder, map, 0, lastIndex, 0, lastIndex); return root; } };

class Solution { private: void dfs(TreeNode* tn, const int &k, int &i, int &res) { if (!tn) { return; } dfs(tn->left, k, i, res); if (k < i) { return; } i++; if (i == k) { res = tn->val; return; } dfs(tn->right, k, i, res); } public: int kthSmallest(TreeNode* root, int k) { int res = -1; int i = 0; dfs(root, k, i, res); return res; } };

class Solution { private: bool dfs(TreeNode *tn, long min, long max) { if (!tn) { return true; } if (tn->val <= min || tn->val >= max) { return false; } if (dfs(tn->left, min, tn->val) && dfs(tn->right, tn->val, max)) { return true; } return false; } public: bool isValidBST(TreeNode* root) { return dfs(root, LONG_MIN, LONG_MAX); } };

class Solution { private: void dfs(TreeNode *tn, int greatest, int &numGoodNodes) { if (!tn) { return; } if (tn->val >= greatest) { numGoodNodes++; } greatest = max(greatest, tn->val); dfs(tn->left, greatest, numGoodNodes); dfs(tn->right, greatest, numGoodNodes); } public: int goodNodes(TreeNode* root) { int numGoodNodes = 0; dfs(root, root->val, numGoodNodes); return numGoodNodes; } };

/* I kept saying this is post order traversal in this video. It is definitely NOT a post order traversal, so don't say that in your interviews lol. Its more like an inverse pre order traversal if such a thing exists */ class Solution { private: void dfs(TreeNode *tn, int level, vector<int> &res) { if (!tn) { return; } if (level > res.size()) { res.push_back(tn->val); } dfs(tn->right, level+1, res); dfs(tn->left, level+1, res); } public: vector<int> rightSideView(TreeNode* root) { vector<int> res; dfs(root, 1, res); return res; } };

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if (!root) { return res; } queue<TreeNode*> q; q.push(root); TreeNode *temp = nullptr; int lvlSize = 0; while (!q.empty()) { vector<int> lvl; lvlSize = q.size(); for (int i = 0; i < lvlSize; i++) { temp = q.front(); q.pop(); lvl.push_back(temp->val); if (temp->left) { q.push(temp->left); } if (temp->right) { q.push(temp->right); } } res.push_back(lvl); } return res; } };

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while (root) { if (p->val > root->val && q->val > root->val) { root = root->right; } else if (p->val < root->val && q->val < root->val) { root = root->left; } else { break; } } return root; }

// my attempty at O(m+n) time complexity w/ basic serialization and advanced kmp matching to get O(m+n) time complexity for finding substring // ***note that time complexity may be inaccurate*** class Solution { private: bool kmpSearch(const string &s1, const string &s2) { vector<int> lps = getlps(s2); int j = 0; for (int i = 0; i < s1.length(); ++i) { while (j > 0 && s1[i] != s2[j]) { j = lps[j - 1]; } if (s1[i] == s2[j]) { j++; } if (j == s2.length()) { return true; } } return false; } vector<int> getlps(const string &s) { vector<int> lps(s.length()); int j = 0; for (int i = 1; i < s.length(); ++i) { while (j > 0 && s[j] != s[i]) { j = lps[j - 1]; } if (s[j] == s[i]) { lps[i] = ++j; } } return lps; } void serialize(TreeNode *tn, string &s) { if (!tn) { s.append(",#"); } else { s.append(","); s.append(to_string(tn->val)); serialize(tn->left, s); serialize(tn->right, s); } } public: bool isSubtree(TreeNode* root, TreeNode* subRoot) { string root_s, subRoot_s; serialize(root, root_s); serialize(subRoot, subRoot_s); return kmpSearch(root_s, subRoot_s); } };

// O(M*N) time complexity class Solution { private: bool isSameTree(TreeNode *p, TreeNode *q) { if (!p && !q) { return true; } if (!p || !q) { return false; } if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right)) { return true; } return false; } public: bool isSubtree(TreeNode* root, TreeNode* subRoot) { if (!root) { return false; } if (isSameTree(root, subRoot)) { return true; } if (isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot)) { return true; } return false; } };

bool isSameTree(TreeNode* p, TreeNode* q) { if (!p && !q) { return true; } if (!p || !q) { return false; } if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right)) { return true; } return false; }

class Solution { private: int checkIsBalanced(TreeNode *tn) { if (!tn) { return 0; } int depthL = checkIsBalanced(tn->left); if (depthL < 0) { return -1; } int depthR = checkIsBalanced(tn->right); if (depthR < 0) { return -1; } if (abs(depthL - depthR) > 1) { return -1; } return max(depthL, depthR) + 1; } public: bool isBalanced(TreeNode* root) { int res = checkIsBalanced(root); if (res < 0) { return false; } return true; } };

class Solution { private: // returns the maximum depth of the subtree at a given node // the maximum diameter at a given node is recalculated with a reference to a variable whose value lives in the function where the recursion was seeded int findMaxD(TreeNode *tn, int &diam) { if (!tn) { return 0; } int depthLeft = findMaxD(tn->left, diam); int depthRight = findMaxD(tn->right, diam); diam = max(diam, depthLeft + depthRight); return max(depthLeft, depthRight) + 1; } public: int diameterOfBinaryTree(TreeNode* root) { int maxDiameter = 0; findMaxD(root, maxDiameter); return maxDiameter; } };

// ITERATIVE DFS: int maxDepth(TreeNode* root) { if (!root) { return 0; } stack<pair<TreeNode*, int>> st; st.push({ root, 1 }); int maxDepth = 1; int depth; while (!st.empty()) { TreeNode *n = st.top().first; depth = st.top().second; maxDepth = max(maxDepth, depth); st.pop(); if (n->left) { st.push({ n->left, depth + 1 }); } if (n->right) { st.push({ n->right, depth + 1 }); } } return maxDepth; } // RECURSIVE DFS: int maxDepth(TreeNode* root) { if (!root) { return 0; } return max(maxDepth(root->left) + 1, maxDepth(root->right) + 1); }

TreeNode* invertTree(TreeNode* root) { stack<TreeNode*> st; st.push(root); TreeNode *n = nullptr; TreeNode *temp = nullptr; while (!st.empty()) { n = st.top(); st.pop(); if (n) { st.push(n->left); st.push(n->right); temp = n->left; n->left = n->right; n->right = temp; } } return root; }

great solution! the idea that you came up with is very nice

ListNode* reverseKGroup(ListNode* head, int k) { ListNode *dummy = new ListNode(); dummy->next = head; // segment markers ListNode *begin = dummy; ListNode *end = head; // reversal markers ListNode *prev = nullptr; ListNode *cur = nullptr; ListNode *next = nullptr; ListNode *fast = head; while (true) { // check to see if we can reverse k nodes for (int i = 0; i < k; i++) { if (!fast) { // deallocate dummy node and return head of list cur = dummy; dummy = dummy->next; delete cur; return dummy; } fast = fast->next; } // reverse segment of k nodes prev = begin; cur = end; // this is the beginning of the segment for (int i = 0; i < k; i++) { next = cur->next; cur->next = prev; prev = cur; cur = next; } // re-attach segment back into list begin->next = prev; // prev is head of reversed segment end->next = cur; // cur is head of rest of list // reset segment markers for next iteration begin = end; end = cur; } }

class Solution { private: ListNode* merge2Lists(ListNode *l1, ListNode *l2) { if (!l1 && !l2) { return nullptr; } else if (l1 && !l2) { return l1; } else if (!l1 && l2) { return l2; } ListNode *dummy = new ListNode(); ListNode *cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1) { cur->next = l1; } else if (l2) { cur->next = l2; } cur = dummy; dummy = dummy->next; delete cur; return dummy; } public: ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.empty()) { return nullptr; } else if (lists.size() == 1) { return lists.front(); } int length = lists.size(); int half; while (length > 1) { half = length / 2; for (int i = 0; i < half; i++) { lists[i] = merge2Lists(lists[i], lists[length - 1 - i]); } length = (length + 1) / 2; } return lists.front(); } };

Node* copyRandomList(Node* head) { // O(1) space if (!head) { return nullptr; } // interleave copied nodes into original list Node *cur = head; while (cur) { Node *temp = cur->next; Node *copy = new Node(cur->val); cur->next = copy; copy->next = temp; cur = temp; } // assign random pointers for copied nodes cur = head; while (cur) { if (cur->random) { cur->next->random = cur->random->next; } cur = cur->next->next; } // separate the lists (restore original list) Node *dummy = new Node(0); cur = dummy; while (head) { // separate new list cur->next = head->next; cur = cur->next; // separate original list head->next = head->next->next; head = head->next; } // prevent mem leak cur = dummy; dummy = dummy->next; delete cur; return dummy; }