Blog | Autzoko Lang

You are given a 0-indexed array of positive integers nums.
In one operation, you can swap any two adjacent elements if they have the same number of set bits (1 presented in binary). You are allowed to do this operation any number of times (including zero).
Return true if you can sort the array, else return false.

Examples:

1
2

Input: nums = [8, 4, 2, 30, 15] => [0x1000, 0x100, 0x10, 0x11110, 0x1111];
Output: True => Sorted to [0x10, 0x100, 0x1000, 0x1111, 0x11110] == [2, 4, 8, 15, 30];

1
2

Input: nums = [3, 16, 8, 4, 2];
Output: False;

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    static bool canSortArray(const vector<int>& nums) {
        uint16_t pmax = 0, cmin = 0; cmax = 0;
        uint8_t pcnt = 0;
        for (const uint16_t v : nums) {
            if (const uint8_t ccnt = popcount(v); pcnt == ccnt) {
                cmin = min(cmin, v);
                cmax = max(cmax, v);
            } else if (cmin < pmax) {
                return false;
            } else {
                pmax = cmax;
                cmin = cmax = v;
                pcnt = ccnt;
            }
        }
        return cmin >= pmax;
    }
}

Explanation:

This solution divides the array into several groups by the number of bits that are set. The popcount() function here is an library function that used to find the number of set bits in a variable. And the if (const uint8_t ccnt = popcount(v); pcnt == ccnt) structure is to define a variable within the if-else if-else structure and use it for boolean expression in a brief way.
The if-else if-else structure in the code is doing mainly for:

• Checking set bits of current variable v, if current number of set bit ccnt equals the number of set bits of last variable pcnt, then they are in the same group. Then update the maximum and the minimum value of current group into cmin and cmax.
• If the minimum value of current group cmin is less than the greatest value of the last group pmax, then this array cannot be sorted because every number that presents in a relative back group must be greater than every number in a front group. Thus, program return false here.
• If ccnt does not equal pcnt, current value v belongs to a new group, so the maximum value of current group is assigned to pmax, the maximum of the previous group, then update cmin and cmax with current value, and pcnt with the number of set bit of v.

Above all, the core of this solution is to guarantee that for each group, their minimum value must be greater than the maximum value of every group in its front.

Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins’ value. Two nodes of a binary tree are cousins if they have the same depth with different parents.
Return the root of the modified tree.

Examples:

1
2

Input: root = [5, 4, 9, 1, 10, null, 7];
Output: [0, 0, 0, 7, 7, null, 11];

1
2

Input: root = [3, 1, 2];
Output = [0, 0, 0]

Constraints:

• The number of nodes in the tree is in the range $[1, 10^6]$.
• $1 \le Node.val \le 10^4$

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        if (!root) return nullptr;
        queue<TreeNode*> q;

        int prev = root->val;
        q.push(root);

        while (!q.empty()) {
            int n = q.size();
            int curr = 0;
            while (n--) {
                TreeNode* temp = q.front();
                q.pop();
                int childrenSum = (temp->left ? temp->left->val : 0) + (temp->right ? temp->right->val : 0);

                if (temp->left) {
                    temp->left->val = childrenSum;
                    q.push(temp->right);
                }
                if (temp->right) {
                    temp->right->val = childrenSum;
                    q.push(temp->right);
                }

                curr += childrenSum;
                temp->val = prev - temp->val;
            }
            prev = curr;
        }
        return root;
    }
}

Explanation:
The whole process of this solution is based on the breadth-first traversal of a binary tree. We use variable $n$ to hold the remained elements in the queue. Then calculate the sum of the children nodes of the front-element in the queue then pop it after finishing the computation. Then push all children nodes of current node into the queue if it has. At first, we use current node to hold the sum of its siblings and itself, and use variable $prev$ to hold the sum of nodes in the same level. Then subtract the $prev$ with itself can get the sum of its cousins.
In short, the logic of this solution is to calculate the sum of children nodes of current node and store the sum into the all of its children nodes (which are siblings for each other). And calculate the sum of the whole level, then subtract the sum by each node’s value (which is the sum of itself with its sibling) can get the sum of cousins. If there is only two nodes in a level, each nodes get no cousins, thus the sum of whole level equals the sum with sibling, hence the result that store into this node is zero.

Given the root of a binary tree and a positive integer $ k $. The level sum in the tree is the sum
of the values of the nodes that are on the same level.
Return the $k^{th}$ largest level sum in the tree (not necessary distinct). If there are fewer than $k$ levels in the tree, return -1.

Example:

1
2
3

Input: root = [5, 8, 9, 2, 1, 3, 7, 4, 6], k = 2;
Output: 13;
Explanation: Level 3 has the 2nd largest sum;

1
2

Input: root = [1, 2, null, 3], k = 1;
Output: 3;

Constraints:

• The number of nodes in the tree is $n$.
• $2 \le Node.val \le 10^5 $
• $1 \le k \le n$

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        vector<long long> res;
        queue<TreeNode*> q;

        q.push(root);

        while(!q.empty()) {
            int n = q.size();
            long long sum = 0;

            while (n--) {
                sum += (long long)q.front()->val;
                if (q.front()->left) q.push(q.front()->left);
                if (q.front()->right) q.push(q.front()->right);
                q.pop();
            }
            res.push_back(sum);
        }

        if (k > res.size()) return -1;
        sort(res.begin(), res.end(), greater<long long>());

        return res[k - 1];
    }
};

Explanation:
Since this problem needs us to calculate the sum of each level of the binary tree, a breadth-first traversal is required. The most used method for breadth-first traversal is to use a queue, the CPP style example code is this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void printTreeBreadthFirst(TreeNode* root) {
    queue<TreeNode*> q;

    if (root != nullptr) {
        q.push(root);
    }

    while (!q.empty()) {
        cout << q.front()->val << " --> ";
        if (q.front()->left) q.push(q.front()->left);
        if (q.front()->right) q.push(q.front()->right);
        q.pop();
    }
}

In this problem, the variable $n$ holds the number of nodes in this level, which $n$ equals current size of the queue. Thus, it only needs to use a inner loop to calculate the sum of the level by popping values from the queue, and meanwhile import the nodes of the next level by accessing the children of current head node of the queue.

Given two 0-indexed integer arrays $nums1$ and $nums2$, return a list answer if size 2 where:

• answer[0] is a list of all distinct integers in $nums1$ which are not present in $nums2$.
• answer[1] is a list of all distinct integers in $nums2$ which are not present in $nums1$.

Examples:

1
2

Input: nums1 = [1, 2, 3], nums2 = [2, 4, 6];
Output = [[1, 3], [4, 6]];

1
2

Input: nums1 = [1, 2, 3, 3], nums2 = [1, 1, 2, 2];
Output: [[3], []];

Constraints:

• $ 1 \le len(nums1), len(nums2) \le 1000$
• $ -1000 \le nums1_i, nums2_i \le 1000

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.begin());
        unordered_set<int> set2(nums2.begin(), nums2.begin());

        vector<int> distinct_nums1, distinct_nums2;

        for (int num : set1) {
            if (set2.count(num) == 0) distinct_nums1.push_back(num);
        }
        for (int num : set2) {
            if (set1.count(num) == 0) distinct_nums2.push_back(num);
        }

        return {distinct_nums1, distinct_nums2};
    }
}

Explanation:

Convert the two array into set, same elements will be merged within a set, and since the unordered_set in C++ is implmented with hash table with separate chaining method, using a specific algorithm to hash element into difference bucket which points to a chain that contains valid elements. Thus, in ideal case, the find function can get the target value with the time complexity of $O(1)$, and the worst case the time complexity reduces to $O(n)$. So, in the solution, the unordered_set is utilized to merge same elements and for faster method to judge whether a value the set is contained.

You are given an integer array nums consisting of $ n$ elements, and an integer $ k$. Find a contiguous subarray whose length is equal to $ k$ that has the maximum average value and return this value. Any answer with a calculation error less than $10^{-5}$ will be accepted.

Example:

1
2

Input: nums = [1, 12, -5, -6, 50, 3], k = 4;
Output: 12.75000;

1
2

Input: nums = [5], k = 1;
Output: 5.00000;

Constraints:

• $ n = len(nums) $
• $ 1 \le k \le n \le 1-^5 $
• $ -10^4 \le nums_i \le 10^4 $

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    using LL = long long;
    double findMaxAverage(vector<int>& nums, int k) {
        LL sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        LL maxSum = sum;
        for (int i = 0, j = k; j < nums.size(); i++, j++) {
            sum = sum - nums[i] + nums[j];
            maxSum = max(maxSum, sum);
        }
        return (double)maxSum / (double)k;
    }
}

Explanation:

This problem uses the Sliding Window technique. To reduce the calculation when sliding, first we do not compute the average each time, we can only calculate the sum of the window and divide it at last when return. Since the length of the window is fixed, so each step it move we just need to subtract the left margin value and add the value next to the right margin then the new sum of the window is get. Slide it step by step and update the maxSum to find the maximum value of the array.

You are given an integer array height of length $n$. There are $n$ vertical lines drawn such that the two endpoints of the $i^{th}$ line are $(i,0)$ and $(i, height_i)$.

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of the water a container can store.

Examples:

1
2

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
Output = 49;

1
2

Input: height = [1, 1];
Output = 1;

Constraints:

• $ n = len(height) $
• $ 2 \le n \le 10^5 $
• $ 0 \le height_i \le 10^4 $

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    using LL = long long;
    int maxArea(vector<int>& height) {
        LL left = 0, right = height.size() - 1;
        LL maxA = 0;

        while (left < right) {
            LL currentArea = min(height[left], height[right]) * (right - left);
            maxA = max(maxA, currentArea);

            if (height[left] < height[right]) left++;
            else right--;
        }
        
        return maxA;
    }
}

Explanation:

To solve this problem the two pointers technique is adopted. The left pointer starting at the index 0 and the right pointer starts at the end of the vector. Use maxA to keep track of the maximum area found. Then calculate the current area of the container and update it to the maxA. And we need to move the two pointers inwards to find the global maximum area. The method for moving inwards the pointers is to always move the smaller one (low one) the seeking a greater value that may increase the area.

The basic pattern of a binary search problem is to find a target element in an orderly list.

The model problem is Leetcode 704

Here are two points that would make mistakes:

• The boundary conditions for the loop
• The redefinition of search interval boundaris

To the boundary conditions for the loop

1

while (left < right)

or

1

while (left <= right)

we need to know when conditions can make the left and right boundary values equal and when not.

To the value of search interval boundaris

1

right = mid;

or

1

right = mid + 1;

we need to know how to redefine the boundary values of left and right.

Loop Invariant

The loop invariant is a property (or expression) that always be true within every iteration of the loop. For the binary search problem, the loop invariant here is the search interval, aka. the value of boundaries left and right.

Here we discuss this search interval should be left-closed, right-open or left-closed, right-closed.

Left-closed Right-closed Interval

Since this is a closed interval, both the left and right boundary values of the interval should be valid (i.e., legitimate values). There for, at that time, the left pointer will point to 0, and the right pointer will point to nums.size()-1.

1

int left = 0, right = nums.size() - 1;

For the loop condition, since both the left and right boundaris can be included in a closed interval, it is reasonable for the left and right boundaries to be equal. Therefore, the condition for the while loop should be left <= right.

When updating the boundary values in this case, we should notice that the right boundary is closed, thus the new right boudary is $mid - 1$ when nums[mid] > target and left boundary is $mid + 1$ when nums[mid] < target.

Left-closed Right-open Interval

Similar to the left-closed right-closed interval, the boundary values are updated in the same way. However, in this case, since the right boundary is open, the condition of the while loop should be left < right here. And when updating boundary values, the right one should be $ mid$ rather than $mid + 1$ because the boundary value is included by the interval.

Given an integer array nums, move all $0$‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that it must be done in-place without making a copy of the array.

Example:

1
2

Input: nums = [0, 1, 0, 3, 12];
Output: [1, 3, 12, 0, 0];

1
2

Input: nums = [0];
Output: [0];

Constraints:

• $ 1 \le len_{nums} \le 10^4 $
• $ -2^{31} \le nums_i \le 2^{32} - 1$

Solution

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] != 0) {
                swap(nums[right], nums[left]);
                left++;
            }
        }
    }
}

Explanation:
The solution use two pointers to separatly point to a non-zero value and a zero value. Initialy, these two point both point to the index 0. And if the right pointer is not 0, two pointers will be moved to their next index simultaneously. When the left point meets a zero value, it will stay on it, and swap the value with the right pointer. In other words, the zeroes with move to the tail of the vector like bulbles (imagine the bulble sort algorithm).

Given an array of characters chars, compress it using following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group length is $1$, append the character to s.
• Otherwise, append the charactoer followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are $10$ or longer will be split into multiple characters in chars.

After modifying the input array, return the new length of the array.

Example:

1
2

Input: chars = ["a","a","b","b","c","c","c"];
Output: 6, ["a","2","b","2","c","3"];

1
2

Input: chars = ["a"];
Output: 1, ["a"];

1
2

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"];
Output: 4, ["a","b","1","2"];

Constraints:

• $ 1 \le l_{chars} \le 2000 $
• $chars_i$ is a lower case English letter, uppercase English letter, digit, or symbol.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int compress(vector<char>& chars) {
        int ans = 0;

        for (int i = 0; i < chars.size();) {
            const char letter = chars[i];
            int count = 0;

            while (i < chars.size() && chars[i] == letter) {
                count++;
                i++;
            }

            chars[ans++] = letter;

            if (count > 1) {
                for (const char c : to_string(count)) {
                    chars[ans++] = c;
                }
            }
        }
        return ans;
    }
}

Explanation:

Using two pointers to iterate original string and trach generated new string. Here, use i to iterate whole string and count the length of each group. Once a group’s length is detected, use another pointer ans to write on the original string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

"aabbccc"
 ^              <-- i = 0
 ^              <-- ans = 0

"aabbccc"
  ^             <-- i++
 ^

"aabbccc"
   ^            <-- i++, n = 2, letter = a
 ^

"aabbccc"
   ^
  ^             <-- chars[ans++] = a

"a2bbccc"
   ^
   ^            <-- chars[ans++] = 2

"a2bbccc"
    ^           <-- i++, n = 1
   ^

"a2bbccc"
     ^          <-- i++, n = 2, letter = b
   ^

"a2bbccc"
     ^
    ^           <-- chars[ans++] = b

"a2b2ccc"
     ^
     ^          <-- chars[ans++] = 2

"a2b2ccc"
      ^         <-- i++
     ^

"a2b2ccc"
       ^        <-- i++, n = 3, letter = c
     ^

"a2b2ccc"
       ^
      ^         <-- chars[ans++] = c

"a2b2c3c"
       ^
       ^        <-- chars[ans++] = 3

Given an integer array nums, return true if there exists a triple of indices $[i, j, k]$ such that $ i \lt j \lt k$ and $nums_i \lt nums_j \lt nums_k$. If no such indices exists, return false.

Example:

1
2

Input: nums = [1, 2, 3, 4, 5];
Output: true;

1
2

Input: nums = [5, 4, 3, 2, 1];
Output: false;

1
2

Input: nums = [2, 1, 5, 0, 4, 6];
Output: true;

Constraints:

• $ 1 \le l_{nums} \le 5 \times 10^5 $
• $ -2^{31} \le nums_i \le 2^{31}-1$

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() < 3) return false;

        int i = INT_MAX, j = INT_MAX;

        for (int num : nums) {
            if (num <= i) {
                i = num;
            } else if (num <= j) {
                j = num;
            } else {
                return true;
            }
        }
        return false;
    }
};

Explanation:
The solution is based on keeping track of two minimum values, $i$ and $j$, while iterating through the array.

• Initialize two variables, $i$ and $j$, to INT_MAX.
• • If the element is less than or equal to $i$, update $i$ with the element.
• • If the element if greater than $i$ but less than or equal to $j$, update $j$ with the element.
• • If the element is greater than both $i$ and $j$, it means an increasing triplet is found, and the function returns true.
• If the loop completes without finding an increasing triplet, return false.

The time complexity is $O(n)$ and the space complexity is $O(1)$.