April 17 - Daily Programming Diary

17.04.2021 — Diary, Programming — 1 min read

12:30

I started with today's Leetcode Challenge. The question is to remove k identical consecutive letters from a string till it's no longer possible.

The approach that I took is with stack and to store the counter, the stack is modified to be a stack of pairs.

remove-all-adjacent-duplicates-in-string-ii.cpp

1string removeDuplicates(string s, int k) {
2    stack<pair<char, int>> stk;
3
4    for (auto c : s) {
5        if (stk.empty()) {
6            stk.push(make_pair(c, 1));
7        } else {
8            pair<char, int> temp = stk.top();
9            if (temp.first == c) {
10                if (temp.second == k - 1) stk.pop();
11                else {
12                    stk.pop();
13                    stk.push(make_pair(c, temp.second + 1));
14                }
15            } else {
16                stk.push(make_pair(c, 1));
17            }
18        }
19    }
20
21    string ans = "";
22    while (!stk.empty()) {
23        pair<char, int> temp = stk.top();
24        for (int i = 0; i < temp.second; i++) {
25            ans = temp.first + ans;
26        }
27        stk.pop();
28    }
29
30    return ans;
31}

16:20

Trying the question for 11th April.

The simplest approach would be to calculate the depth of the tree and then iterate the tree for the second time and adding the nodes at the level. It would take two iterations.

The next approach could be to store all the levels along with their sums in a map and then finding the sum associated with the maximum value. This would mean just a single iteration over the tree.

deepest-leaves-sum-with-map.cpp

1unordered_map<int, int> umap;
2
3void traverse(TreeNode *root, int level) {
4    if (!root) return;
5
6    umap[level] += root->val;
7
8    traverse(root->left, level + 1);
9    traverse(root->right, level + 1);
10}
11
12int deepestLeavesSum(TreeNode *root) {
13    traverse(root, 0);
14
15    int mx = 0;
16
17    for (auto a : umap) {
18        mx = max(a.first, mx);
19    }
20
21    return umap[mx];
22}

The next approach is to find the maximum depth value as we traverse, and then calculating the sum according to that.

deepest-leaves-sum-with-one-iteration.cpp

1int deepestLevel = 0, sum = 0;
2
3void traverse(TreeNode *root, int level) {
4    if (!root) return;
5
6    if (level > deepestLevel) {
7        deepestLevel = level;
8        sum = 0;
9    }
10
11    if (level == deepestLevel) {
12        sum += root->val;
13    }
14
15    traverse(root->left, level + 1);
16    traverse(root->right, level + 1);
17}
18
19int deepestLeavesSum(TreeNode *root) {
20    traverse(root, 0);
21
22    return sum;
23}

21:30

Okay, done for the day! Bye.

EOD Checklist

Raahee
Leetcode April Challenge
This blog