
# 1-bit and 2-bit Characters Problem & Solution

We have two special characters:

- The first character can be represented by one bit 0.
- The second character can be represented by two bits (10 or 11).

Given a binary array `bits` that ends with 0, return true if the last character must be a one-bit character.

See the [1-bit and 2-bit characters problem on LeetCode](https://leetcode.com/problems/1-bit-and-2-bit-characters).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool isOneBitCharacter(vector<int>& bits) {
    for (int i = 0; i < bits.size(); ++i) {

      // Skips two positions if `bits[i]` is 1 because the next position can't be a one-bit character.
      if (bits[i] == 1) {
        i += 1;
      } else if (i == bits.size() - 1 && bits[i] == 0) {
        return true;
      }
    }

    return false;
  }
};
```


Solution for we have two special characters: The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11). Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.

1-bit and 2-bit Characters

LeetCode 1-bit and 2-bit Characters Solution


# 3Sum Closest Problem & Solution

See the [3sum closest problem on LeetCode](https://leetcode.com/problems/3sum-closest).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());

    auto best = target;
    auto min = numeric_limits<int>::max();

    for (auto i = 0; i < (int)nums.size() - 2; ++i) {
      auto j = i + 1;
      auto k = nums.size() - 1;
      while (j < k) {
        auto sum = nums[i] + nums[j] + nums[k];

        if (abs(target - sum) < min) {
          min = abs(target - sum);
          best = sum;
        }
        
        if (sum > target) {
          --k;
        } else if (sum < target) {
          ++j;
        } else {
          break;
        }
      }
    }
    
    return best;
  }
};
```


Solution for the 3sum closest problem from LeetCode.

3Sum Closest

LeetCode 3Sum Closest Solution


# 3Sum Problem & Solution

See the [3sum problem on LeetCode](https://leetcode.com/problems/3sum).

## C++ Solution

The runtime complexity of this algorithm is $O(n\log{}n + n^2)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;

    sort(nums.begin(), nums.end());

    for (int i = 0; i < (int)nums.size() - 2; ++i) {
      int j = i + 1;
      int k = nums.size() - 1;
      while (j < k) {
        int sum = nums[i] + nums[j] + nums[k];
        if (sum > 0) {
          —k;
        } else if (sum < 0) {
          ++j;
        } else {
          result.push_back({nums[i], nums[j], nums[k]});
          while (j < (int)nums.size() - 1 && nums[j] == nums[j + 1]) ++j;
          while (k > 0 && nums[k] == nums[k - 1]) —k;
          ++j;
          —k;
        }
      }

      while (i < (int)nums.size() - 1 && nums[i] == nums[i + 1]) ++i;
    }

    return vector<vector<int>>(result.begin(), result.end());
  }
};
```


Solution for the 3sum problem from LeetCode.

3Sum

LeetCode 3Sum Solution


# 4Sum Problem & Solution

See the [4sum problem on LeetCode](https://leetcode.com/problems/4sum).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

using namespace std;

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;

    sort(nums.begin(), nums.end());
    
    for (int i = 0; i < (int)nums.size() - 3; ++i) {
      for (int j = i + 1; j < (int)nums.size() - 2; ++j) {
        int k = j + 1;
        int l = nums.size() - 1;
        while (k < l) {
          long sum = static_cast<long>(nums[i]) + nums[j] + nums[k] + nums[l];
          if (sum < target) {
            ++k;
          } else if (sum > target) {
            --l;
          } else {
            result.push_back({nums[i], nums[j], nums[k], nums[l]});
            while (k < nums.size() - 1 && nums[k] == nums[k + 1]) { ++k; }
            while (l > 0 && nums[l] == nums[l - 1]) { --l; }
            ++k;
            --l;
          }
        }
        
        while (j < nums.size() - 1 && nums[j] == nums[j + 1]) { ++j; }
      }
      
      while (i < nums.size() - 1 && nums[i] == nums[i + 1]) { ++i; }
    }
    
    return result;
  }
};
```


Solution for the 4sum problem from LeetCode.

4Sum

LeetCode 4Sum Solution


# Add Binary Problem & Solution

Given two binary strings `a` and `b`, return their sum as a binary string.

See the [add binary problem on LeetCode](https://leetcode.com/problems/add-binary).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string addBinary(string a, string b) {
    int longest = max(a.size(), b.size());
    string sum(longest, '0');

    int i = a.size() - 1;
    int j = b.size() - 1;
    int k = longest - 1;
    int carryover = 0;
    while (i >= 0 && j >= 0) {
      int ci = a[i--] == '1' ? 1 : 0;
      int cj = b[j--] == '1' ? 1 : 0;
      sum[k--] = (ci + cj + carryover) % 2 + '0';
      carryover = (ci + cj + carryover) / 2;
    }

    while (i >= 0) {
      int ci = a[i--] == '1' ? 1 : 0;
      sum[k--] = (ci + carryover) % 2 + '0';
      carryover = (ci + carryover) / 2;
    }

    while (j >= 0) {
      int cj = b[j--] == '1' ? 1 : 0;
      sum[k--] = (cj + carryover) % 2 + '0';
      carryover = (cj + carryover) / 2;
    }

    if (carryover > 0) {
      sum.insert(0, "1");
    }

    return sum;
  }
};
```


Solution for the add binary problem from LeetCode.

Add Binary

LeetCode Add Binary Solution


# Add Digits Problem & Solution

Given an integer `num`, repeatedly add all its digits until the result has only one digit, and return it.

See the [add digits problem on LeetCode](https://leetcode.com/problems/add-digits).

## C++ Solution

The runtime complexity of this algorithm is $O(1)$.

```cpp
#pragma GCC optimize("Ofast")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int addDigits(int num) {
    if (num == 0) {
      return 0;
    }

    // https://en.wikipedia.org/wiki/Digital_root
    return 1 + (num - 1) % 9;
  }
};
```


Solution for the add digits problem from LeetCode.

Add Digits

LeetCode Add Digits Solution


# Add to Array-Form of Integer Problem & Solution

The array-form of an integer `num` is an array representing its digits in left to right order.

For example, for `num = 1321`, the array form is `[1,3,2,1]`.
Given `num`, the array-form of an integer, and an integer `k`, return the array-form of the integer `num + k`.

See the [add to array-form of integer problem on LeetCode](https://leetcode.com/problems/add-to-array-form-of-integer).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("fast-math")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> addToArrayForm(vector<int>& num, int k) {
    int carry = 0;
    int i = 0;
    while (k > 0 || carry > 0) {
      if (i == num.size()) {
        num.insert(num.begin(), 0);
      }

      int j = num.size() - i - 1;
      int digit = k % 10;
      int sum = num[j] + digit + carry;
      k /= 10;
      num[j] = sum % 10;
      carry = sum / 10;

      ++i;
    }

    return num;
  }
};
```


Solution for the array-form of an integer num is an array representing its digits in left to right order. For example, for num = 1321, the array form is [1,3,2,1]. Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.

Add to Array-Form of Integer

LeetCode Add to Array-Form of Integer Solution


# Array Partition I Problem & Solution

Given an integer array `nums` of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized.
Return the maximized sum.

See the [array partition i problem on LeetCode](https://leetcode.com/problems/array-partition-i).

## C++ Solution

The runtime complexity of this algorithm is $O(n\log{}n)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());

    int sum = 0;
    for (int i = 0; i < nums.size(); i += 2) {
      sum += min(nums[i], nums[i + 1]);
    }

    return sum;
  }
};
```


Solution for the array partition i problem from LeetCode.

Array Partition I

LeetCode Array Partition I Solution


# Assign Cookies Problem & Solution

Assume you are an awesome parent and want to give your children some cookies.
But, you should give each child at most one cookie.

Each child `i` has a greed factor `g[i]`, which is the minimum size of a cookie that the child will be content with; and each cookie `j` has a size `s[j]`.
If `s[j] >= g[i]`, we can assign the cookie `j` to the child `i`, and the child `i` will be content.
Your goal is to maximize the number of your content children and output the maximum number.

See the [assign cookies problem on LeetCode](https://leetcode.com/problems/assign-cookies).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());

    int i = 0;
    int j = 0;
    while (i < g.size()) {
      while (j < s.size() && s[j] < g[i]) {
        ++j;
      }

      if (j == s.size()) {
        break;
      }

      ++i;
      ++j;
    }

    return i;
  }
};
```


Solution for the assign cookies problem from LeetCode.

Assign Cookies

LeetCode Assign Cookies Solution


# Balanced Binary Tree Problem & Solution

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

See the [balanced binary tree problem on LeetCode](https://leetcode.com/problems/balanced-binary-tree).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  bool isBalanced(TreeNode* root) {
    bool ok = true;

    isBalanced(root, ok);

    return ok;
  }

private:
  int isBalanced(TreeNode* root, bool& ok) {
    if (root == nullptr) {
      return 0;
    }

    int left = isBalanced(root->left, ok);
    int right = isBalanced(root->right, ok);

    if (abs(left - right) > 1) {
      ok = false;
    }

    return max(left, right) + 1;
  }
};
```


Solution for the balanced binary tree problem from LeetCode.

Balanced Binary Tree

LeetCode Balanced Binary Tree Solution


# Base 7 Problem & Solution

Given an integer `num`, return a string of its base 7 representation.

See the [base 7 problem on LeetCode](https://leetcode.com/problems/base-7).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string convertToBase7(int num) {
    int positive = abs(num);

    string result;
    while (positive > 0) {
      result += positive % 7 + '0';
      positive /= 7;
    }

    if (num < 0) {
      result += '-';
    } else if (num == 0) {
      result = "0";
    }

    reverse(result.begin(), result.end());

    return result;
  }
};
```


Solution for given an integer num, return a string of its base 7 representation.

Base 7

LeetCode Base 7 Solution


# Best Time to Buy and Sell Stock II Problem & Solution

You are given an array prices where `prices[i]` is the price of a given stock on the `i`th day.

Find the maximum profit you can achieve.
You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

See the [best time to buy and sell stock ii problem on LeetCode](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int profit = 0;
    for (int i = 1; i < prices.size(); ++i) {
      if (prices[i - 1] < prices[i]) {
        profit += prices[i] - prices[i - 1];
      }
    }

    return profit;
  }
};
```


Solution for you are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Best Time to Buy and Sell Stock II

LeetCode Best Time to Buy and Sell Stock II Solution


# Best Time to Buy and Sell Stock Problem & Solution

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`th day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction.
If you cannot achieve any profit, return 0.

See the [best time to buy and sell stock problem on LeetCode](https://leetcode.com/problems/best-time-to-buy-and-sell-stock).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int min_value = INT_MAX;
    int result = 0;

    for (int i = 0; i < prices.size(); ++i) {
      if (min_value > prices[i]) {
        min_value = prices[i];
      } else if (prices[i] - min_value > result) {
        result = prices[i] - min_value;
      }
    }

    return result;
  }
};
```


Solution for the best time to buy and sell stock problem from LeetCode.

Best Time to Buy and Sell Stock

LeetCode Best Time to Buy and Sell Stock Solution


# Binary Gap Problem & Solution

Given a positive integer `n`, find and return the longest distance between any two adjacent `1`'s in the binary representation of `n`.
If there are no two adjacent `1`'s, return `0`.

Two `1`'s are adjacent if there are only `0`'s separating them (possibly no `0`'s).
The distance between two `1`'s is the absolute difference between their bit positions.
For example, the two `1`'s in `"1001"` have a distance of 3.

See the [binary gap problem on LeetCode](https://leetcode.com/problems/binary-gap).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int binaryGap(int n) {
    string s;
    while (n > 0) {
      s += n % 2 + '0';
      n /= 2;
    }

    int best = 0;
    int low = -1;
    int high = 0;
    while (high < s.size()) {
      if (s[high] == '1') {
        if (low != -1) {
          best = max(best, high - low);
        }

        low = high;
      }

      ++high;
    }

    return best;
  }
};
```


Solution for given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0. Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Binary Gap

LeetCode Binary Gap Solution


# Binary Number with Alternating Bits Problem & Solution

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

See the [binary number with alternating bits problem on LeetCode](https://leetcode.com/problems/binary-number-with-alternating-bits).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool hasAlternatingBits(int n) {
    int prev = n % 2;
    n /= 2;

    while (n > 0) {
      int mod = n % 2;
      n /= 2;

      if (mod == prev) {
        return false;
      }

      prev = mod;
    }

    return true;
  }
};
```


Solution for given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Binary Number with Alternating Bits

LeetCode Binary Number with Alternating Bits Solution


# Binary Search Problem & Solution

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`.
If `target` exists, then return its index.
Otherwise, return -1.

You must write an algorithm with $O(\log{}n)$ runtime complexity.

See the [binary search problem on LeetCode](https://leetcode.com/problems/binary-search).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int search(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    while (low < high) {

      // Uses this way of calculating the midpoint vs. `(low + high) / 2` to avoid overflow.
      int mid = low + (high - low) / 2;
      if (target > nums[mid]) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    return target == nums[low] ? low : -1;
  }
};
```


Solution for given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

Binary Search

LeetCode Binary Search Solution


# Binary Tree Inorder Traversal Problem & Solution

Given the `root` of a binary tree, return the inorder traversal of its nodes' values.

See the [binary tree inorder traversal problem on LeetCode](https://leetcode.com/problems/binary-tree-inorder-traversal).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> path;

    inorderTraversal(root, path);

    return path;
  }

private:
  void inorderTraversal(TreeNode* node, vector<int>& path) {
    if (node == nullptr) {
      return;
    }

    inorderTraversal(node->left, path);
    path.push_back(node->val);
    inorderTraversal(node->right, path);
  }
};
```


Solution for the binary tree inorder traversal problem from LeetCode.

Binary Tree Inorder Traversal

LeetCode Binary Tree Inorder Traversal Solution


# Binary Tree Paths Problem & Solution

Given the `root` of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.

See the [binary tree paths problem on LeetCode](https://leetcode.com/problems/binary-tree-paths).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> results;

    binaryTreePaths(root, "", results);

    return results;
  }

private:
  void binaryTreePaths(TreeNode* root, string result, vector<string>& results) {
    if (root == nullptr) {
      return;
    }

    if (root->left == nullptr && root->right == nullptr) {
      result += to_string(root->val);
      results.push_back(result);
    }

    string tmp = result + to_string(root->val) + "->";

    binaryTreePaths(root->left, tmp, results);
    binaryTreePaths(root->right, tmp, results);
  }
};
```


Solution for the binary tree paths problem from LeetCode.

Binary Tree Paths

LeetCode Binary Tree Paths Solution


# Binary Tree Postorder Traversal Problem & Solution

Given the `root` of a binary tree, return the postorder traversal of its nodes' values.

See the [binary tree postorder traversal problem on LeetCode](https://leetcode.com/problems/binary-tree-postorder-traversal).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  vector<int> postorderTraversal(TreeNode* root) {
    vector<int> traversal;

    postorderTraversal(root, traversal);

    return traversal;
  }

private:
  void postorderTraversal(TreeNode* node, vector<int>& traversal) {
    if (node == nullptr) {
      return;
    }

    postorderTraversal(node->left, traversal);
    postorderTraversal(node->right, traversal);
    traversal.push_back(node->val);
  }
};
```


Solution for the binary tree postorder traversal problem from LeetCode.

Binary Tree Postorder Traversal

LeetCode Binary Tree Postorder Traversal Solution


# Binary Tree Preorder Traversal Problem & Solution

Given the `root` of a binary tree, return the preorder traversal of its nodes' values.

See the [binary tree preorder traversal problem on LeetCode](https://leetcode.com/problems/binary-tree-preorder-traversal).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  vector<int> preorderTraversal(TreeNode* root) {
    vector<int> traversal;

    preorderTraversal(root, traversal);

    return traversal;
  }

private:
  void preorderTraversal(TreeNode* node, vector<int>& traversal) {
    if (node == nullptr) {
      return;
    }

    traversal.push_back(node->val);
    preorderTraversal(node->left, traversal);
    preorderTraversal(node->right, traversal);
  }
};
```


Solution for the binary tree preorder traversal problem from LeetCode.

Binary Tree Preorder Traversal

LeetCode Binary Tree Preorder Traversal Solution


# Binary Tree Tilt Problem & Solution

Given the `root` of a binary tree, return the sum of every tree node's tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values.
If a node does not have a left child, then the sum of the left subtree node values is treated as 0.
The rule is similar if there the node does not have a right child.

See the [binary tree tilt problem on LeetCode](https://leetcode.com/problems/binary-tree-tilt).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  int findTilt(TreeNode* root) {
    int result = 0;
    findTilt(root, result);

    return result;
  }

private:
  int findTilt(TreeNode* root, int& sum) {
    if (root == nullptr) {
      return 0;
    }

    if (root->left == nullptr && root->right == nullptr) {
      return root->val;
    }

    int left = findTilt(root->left, sum);
    int right = findTilt(root->right, sum);

    sum += abs(left - right);

    return left + right + root->val;
  }
};
```


Solution for given the root of a binary tree, return the sum of every tree node's tilt. The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if there the node does not have a right child.

Binary Tree Tilt

LeetCode Binary Tree Tilt Solution


# Can Place Flowers Problem & Solution

You have a long flowerbed in which some of the plots are planted, and some are not.
However, flowers cannot be planted in adjacent plots.

Given an integer array `flowerbed` containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer `n`, return if `n` new flowers can be planted in the `flowerbed` without violating the no-adjacent-flowers rule.

See the [can place flowers problem on LeetCode](https://leetcode.com/problems/can-place-flowers).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    int j = 0;
    for (int i = 0; i < flowerbed.size(); ++i) {
      if (flowerbed[i] == 1) {
        continue;
      }

      bool left = i == 0 || (i > 0 && flowerbed[i - 1] == 0);
      bool right = i == flowerbed.size() - 1 || (i < flowerbed.size() - 1 && flowerbed[i + 1] == 0);

      if (left && right) {
        flowerbed[i] = 1;
        ++j;
      }
    }

    return j >= n;
  }
};
```


Solution for you have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Can Place Flowers

LeetCode Can Place Flowers Solution


# Climbing Stairs Problem & Solution

You are climbing a staircase.
It takes `n` steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

See the [climbing stairs problem on LeetCode](https://leetcode.com/problems/climbing-stairs).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int climbStairs(int n) {
    if (n <= 2) {
      return n;
    }

    int result = 0;
    int first = 1;
    int second = 2;

    for (int i = 3; i <= n; ++i) {
      int tmp = result;

      result = first + second;
      first = second;
      second = result;
    }

    return result;
  }
};
```


Solution for the climbing stairs problem from LeetCode.

Climbing Stairs

LeetCode Climbing Stairs Solution


# Complement of Base 10 Integer Problem & Solution

The complement of an integer is the integer you get when you flip all the `0`'s to `1`'s and all the `1`'s to `0`'s in its binary representation.

For example, the integer `5` is `"101"` in binary and its complement is `"010"` which is the integer `2`.
Given an integer `n`, return its complement.

See the [complement of base 10 integer problem on LeetCode](https://leetcode.com/problems/complement-of-base-10-integer).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int bitwiseComplement(int n) {
    if (n == 0) {
      return 1;
    }

    vector<int> bits;
    while (n > 0) {
      bits.push_back(n % 2);
      n /= 2;
    }

    int m = 0;
    for (int i = bits.size() - 1; i >= 0; --i) {
      m *= 2;
      m += bits[i] == 0 ? 1 : 0;
    }

    return m;
  }
};
```


Solution for the complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation. For example, the integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer n, return its complement.

Complement of Base 10 Integer

LeetCode Complement of Base 10 Integer Solution


# Construct the Rectangle Problem & Solution

A web developer needs to know how to design a web page's size.
So, given a specific rectangular web page's area, your job by now is to design a rectangular web page, whose length `L` and width `W` satisfy the following requirements:

- The area of the rectangular web page you designed must equal to the given target area.
- The width `W` should not be larger than the length `L`, which means `L >= W`.
- The difference between length `L` and width `W` should be as small as possible.

Return an array `[L, W]` where `L` and `W` are the length and width of the web page you designed in sequence.

See the [construct the rectangle problem on LeetCode](https://leetcode.com/problems/construct-the-rectangle).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> constructRectangle(int area) {

    // Starts with the square root and keeps decrementing to find an exact match.
    for (int i = sqrt(area); i > 0; --i) {
      if (area % i == 0) {

        // The denominator keeps getting smaller, so `area / i` will be larger.
        return {area / i, i};
      }
    }

    // If the area is a prime number, return itself because it's the only way to decompose.
    return {area, 1};
  }
};
```


Solution for a web developer needs to know how to design a web page's size. So, given a specific rectangular web page's area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements: The area of the rectangular web page you designed must equal to the given target area. The width W should not be larger than the length L, which means L >= W. The difference between length L and width W should be as small as possible. Return an array [L, W] where L and W are the length and width of the web page you designed in sequence.

Construct the Rectangle

LeetCode Construct the Rectangle Solution


# Container with Most Water Problem & Solution

See the [container with most water problem on LeetCode](https://leetcode.com/problems/container-with-most-water).

## C++ Solution

The runtime complexity of this algorithm is $O(n)$.

```cpp
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int maxArea(vector<int>& height) {
    int best = (height.size() - 1) * min(height[0], height[height.size() - 1]);

    int i = 0, j = height.size() - 1;
    while (i < j) {

      // Keeps moving the smallest height towards the center.
      if (height[i] < height[j]) {
        ++i;
      } else {
        --j;
      }

      best = max(best, (j - i) * min(height[i], height[j]));
    }

    return best;
  }
};
```


Solution for the container with most water problem from LeetCode.

Container with Most Water

LeetCode Container with Most Water Solution


# Contains Duplicate II Problem & Solution

Given an integer array `nums` and an integer `k`, return true if there are two distinct indices `i` and `j` in the array such that `nums[i] == nums[j]` and `abs(i - j) <= k`.

See the [contains duplicate ii problem on LeetCode](https://leetcode.com/problems/contains-duplicate-ii).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool containsNearbyDuplicate(vector<int>& nums, int k) {

    // Represents the most recent position we saw for each number.
    unordered_map<int, int> js;
    for (int i = 0; i < nums.size(); ++i) {
      if (js.find(nums[i]) != js.end() &&
          abs(i - js[nums[i]]) <= k) {
        return true;
      }

      // Keeps track of the last position we saw for `nums[i]`.
      js[nums[i]] = i;
    }

    return false;
  }
};
```


Solution for given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Contains Duplicate II

LeetCode Contains Duplicate II Solution


# Contains Duplicate Problem & Solution

Given an integer array `nums`, return true if any value appears at least twice in the array, and return false if every element is distinct.

See the [contains duplicate problem on LeetCode](https://leetcode.com/problems/contains-duplicate).

## C++ Solution

The runtime complexity of the algorithm is $O(n\log{}n)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size() - 1; ++i) {
      if (nums[i] == nums[i + 1]) {
        return true;
      }
    }

    return false;
  }
};
```


Solution for the contains duplicate problem from LeetCode.

Contains Duplicate

LeetCode Contains Duplicate Solution


# Convert a Number to Hexadecimal Problem & Solution

Given an integer `num`, return a string representing its hexadecimal representation.
For negative integers, two’s complement method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

Note: You are not allowed to use any built-in library method to directly solve this problem.

See the [convert a number to hexadecimal problem on LeetCode](https://leetcode.com/problems/convert-a-number-to-hexadecimal).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string toHex(int num) {
    if (num == 0) {
      return "0";
    }

    string result = "";

    // Converts to two's complement.
    uint unum = (uint)num;

    while (unum > 0) {
      int r = unum % 16;
      result += r < 10 ? r + '0' : r - 10 + 'a';
      unum /= 16;
    }

    reverse(result.begin(), result.end());

    return result;
  }
};
```


Solution for the convert a number to hexadecimal problem from LeetCode.

Convert a Number to Hexadecimal

LeetCode Convert a Number to Hexadecimal Solution


# Convert Sorted Array to Binary Search Tree Problem & Solution

Given an integer array `nums` where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

See the [convert sorted array to binary search tree problem on LeetCode](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimizations("max-inline-insns-recursive-auto")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
    TreeNode* root = nullptr;
    sortedArrayToBST(nums, 0, nums.size() - 1, &root);

    return root;
  }

private:
  void sortedArrayToBST(vector<int>& nums, int low, int high, TreeNode** node) {
    if (low > high) {
      return;
    }

    int mid = low + (high - low) / 2;
    *node = new TreeNode(nums[mid]);
    sortedArrayToBST(nums, low, mid - 1, &(*node)->left);
    sortedArrayToBST(nums, mid + 1, high, &(*node)->right);
  }
};
```


Solution for given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Convert Sorted Array to Binary Search Tree

LeetCode Convert Sorted Array to Binary Search Tree Solution


# Count Negative Numbers in a Sorted Matrix Problem & Solution

See the [count negative numbers in a sorted matrix problem on LeetCode](https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int countNegatives(vector<vector<int>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); ++i) {
      for (int j = 0; j < grid[i].size(); ++j) {
        if (grid[i][j] < 0) {
          count += grid[i].size() - j;
          break;
        }
      }
    }

    return count;
  }
};
```


Solution for the count negative numbers in a sorted matrix problem from LeetCode.

Count Negative Numbers in a Sorted Matrix

LeetCode Count Negative Numbers in a Sorted Matrix Solution


# Count Primes Problem & Solution

Count the number of prime numbers less than a non-negative number, `n`.

See the [count primes problem on LeetCode](https://leetcode.com/problems/count-primes).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int countPrimes(int n) {
    if (n < 2) {
      return 0;
    }

    vector<bool> sieve(n, true);
    sieve[0] = false;
    sieve[1] = false;

    for (int i = 2; i < n; ++i) {
      if (sieve[i]) {
        for (int j = i * 2; j < n; j += i) {
          sieve[j] = false;
        }
      }
    }

    int result = 0;
    for (int i = 2; i < n; ++i) {
      if (sieve[i]) {
        result += 1;
      }
    }

    return result;
  }
};
```


Solution for the count primes problem from LeetCode.

Count Primes

LeetCode Count Primes Solution


# Counting Bits Problem & Solution

Given an integer `n`, return an array `ans` of length `n + 1` such that for each `i (0 <= i <= n)`, `ans[i]` is the number of 1's in the binary representation of `i`.

See the [counting bits problem on LeetCode](https://leetcode.com/problems/counting-bits).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> countBits(int n) {
    vector<int> results(n + 1, 0);

    for (int i = 1; i < results.size(); ++i) {
      results[i] = __builtin_popcount(i);
    }

    return results;
  }
};
```


Solution for the counting bits problem from LeetCode.

Counting Bits

LeetCode Counting Bits Solution


# Cousins in Binary Tree Problem & Solution

Given the `root` of a binary tree with unique values and the values of two different nodes of the tree `x` and `y`, return `true` if the nodes corresponding to the values `x` and `y` in the tree are cousins, or `false` otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the `root` node is at the depth `0`, and children of each depth `k` node are at the depth `k + 1`.

See the [cousins in binary tree problem on LeetCode](https://leetcode.com/problems/cousins-in-binary-tree).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  bool isCousins(TreeNode* root, int x, int y) {
    metadata left = getMetadata(root, x, 0);
    metadata right = getMetadata(root, y, 0);

    return left.depth == right.depth &&
      left.parent != right.parent;
  }

private:
  struct metadata {
    TreeNode* parent;
    int depth;
  };

  metadata getMetadata(TreeNode* root, int val, int depth) {
    if (root == nullptr) {
      return {nullptr, 0};
    }

    if (root->left && root->left->val == val) {
      return {root, depth + 1};
    }

    if (root->right && root->right->val == val) {
      return {root, depth + 1};
    }

    metadata left = getMetadata(root->left, val, depth + 1);
    if (left.parent) {
      return left;
    } else {
      return getMetadata(root->right, val, depth + 1);
    }
  }
};
```


Solution for given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise. Two nodes of a binary tree are cousins if they have the same depth with different parents. Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Cousins in Binary Tree

LeetCode Cousins in Binary Tree Solution


# Day of the Year Problem & Solution

See the [day of the year problem on LeetCode](https://leetcode.com/problems/day-of-the-year).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("fast-math")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int dayOfYear(string date) {
    int year = stoi(date.substr(0, 4));
    int month = stoi(date.substr(5, 2));
    int day = stoi(date.substr(8, 2));
    vector<int> days{
      31, // January

      // https://en.wikipedia.org/wiki/Leap_year
      year % 4 == 0 && (year % 100 != 0 || (year % 100 == 0 && year % 400 == 0)) ? 29 : 28, // February
      31, // March
      30, // April
      31, // May
      30, // June
      31, // July
      31, // August
      30, // September
      31, // October
      30, // November
      31, // December
    };

    int total = 0;
    for (int i = 0; i < month - 1; ++i) {
      total += days[i];
    }

    total += day;

    return total;
  }
};
```


Solution for the day of the year problem from LeetCode.

Day of the Year

LeetCode Day of the Year Solution


# Degree of an Array Problem & Solution

Given a non-empty array of non-negative integers `nums`, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of `nums`, that has the same degree as `nums`.

See the [degree of an array problem on LeetCode](https://leetcode.com/problems/degree-of-an-array).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int findShortestSubArray(vector<int>& nums) {
    int degree = 0;
    unordered_map<int, help> freq;
    for (int i = 0; i < nums.size(); ++i) {
      if (freq.find(nums[i]) == freq.end()) {
        freq[nums[i]] = {1, i, i};
      } else {
        ++freq[nums[i]].count;
        freq[nums[i]].high = i;
      }

      degree = max(degree, freq[nums[i]].count);
    }

    int argdegree = numeric_limits<int>::max();
    for (auto it = freq.begin(); it != freq.end(); ++it) {
      if (it->second.count == degree) {
        argdegree = min(argdegree, it->second.high - it->second.low + 1);
      }
    }

    return argdegree;
  }

private:
  struct help {
    int count;
    int low;
    int high;
  };
};
```


Solution for given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Degree of an Array

LeetCode Degree of an Array Solution


# Delete Node in a Linked List Problem & Solution

Write a function to delete a node in a singly-linked list.
You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.
It is guaranteed that the node to be deleted is not a tail node in the list.

See the [delete node in a linked list problem on LeetCode](https://leetcode.com/problems/delete-node-in-a-linked-list).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  void deleteNode(ListNode* node) {
    ListNode* cursor = node->next;

    // Saves the next node onto the node to be deleted; so, the node to be deleted is actually the next node now.
    *node = *cursor;

    // Frees up memory occupied by the next node; otherwise, the next node lives in memory twice.
    // This deletes the initial location of the next node.
    delete cursor;
  }
};
```


Solution for write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly. It is guaranteed that the node to be deleted is not a tail node in the list.

Delete Node in a Linked List

LeetCode Delete Node in a Linked List Solution


# Detect Capital Problem & Solution

We define the usage of capitals in a word to be right when one of the following cases holds:

- All letters in this word are capitals, like "USA".
- All letters in this word are not capitals, like "leetcode".
- Only the first letter in this word is capital, like "Google".

Given a string `word`, return true if the usage of capitals in it is right.

See the [detect capital problem on LeetCode](https://leetcode.com/problems/detect-capital).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool detectCapitalUse(string word) {
    bool uppercase = true;
    bool lowercase = true;
    bool sentencecase = true;
    for (int i = 0; i < word.size(); ++i) {
      uppercase &= word[i] >= 'A' && word[i] <= 'Z';
      lowercase &= word[i] >= 'a' && word[i] <= 'z';
      sentencecase &= i == 0
        ? word[i] >= 'A' && word[i] <= 'Z'
        : word[i] >= 'a' && word[i] <= 'z';
    }

    return uppercase || lowercase || sentencecase;
  }
};
```


Solution for we define the usage of capitals in a word to be right when one of the following cases holds: All letters in this word are capitals, like USA. All letters in this word are not capitals, like leetcode. Only the first letter in this word is capital, like Google. Given a string word, return true if the usage of capitals in it is right.

Detect Capital

LeetCode Detect Capital Solution


# DI String Match Problem & Solution

A permutation `perm` of `n + 1` integers of all the integers in the range `[0, n]` can be represented as a string `s` of length `n` where:

- `s[i] == 'I'` if `perm[i] < perm[i + 1]`, and
- `s[i] == 'D'` if `perm[i] > perm[i + 1]`.

Given a string `s`, reconstruct the permutation `perm` and return it.
If there are multiple valid permutations `perm`, return any of them.

See the [DI string match problem on LeetCode](https://leetcode.com/problems/di-string-match).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> diStringMatch(string s) {
    int low = 0;
    int high = s.size();

    vector<int> result(s.size() + 1, 0);
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == 'I') {
        result[i] = low++;
      } else {
        result[i] = high--;
      }
    }

    result[s.size()] = low;

    return result;
  }
};
```


Solution for a permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where: s[i] == 'I' if perm[i] < perm[i + 1], and s[i] == 'D' if perm[i] > perm[i + 1]. Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

DI String Match

LeetCode DI String Match Solution


# Diameter of Binary Tree Problem & Solution

Given the `root` of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree.
This path may or may not pass through the `root`.

The length of a path between two nodes is represented by the number of edges between them.

See the [diameter of binary tree problem on LeetCode](https://leetcode.com/problems/diameter-of-binary-tree).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * 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:
  int diameterOfBinaryTree(TreeNode* root) {
    int result = 0;
    diameterOfBinaryTree(root, result);

    return result;
  }

private:
  int diameterOfBinaryTree(TreeNode* root, int& diameter) {
    if (root == nullptr) {
      return -1;
    }

    int left = 1 + diameterOfBinaryTree(root->left, diameter);
    int right = 1 + diameterOfBinaryTree(root->right, diameter);
    diameter = max(diameter, left + right);

    return max(left, right);
  }
};
```


Solution for given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

Diameter of Binary Tree

LeetCode Diameter of Binary Tree Solution


# Distance between Bus Stops Problem & Solution

A bus has `n` stops numbered from `0` to `n - 1` that form a circle.
We know the distance between all pairs of neighboring stops where `distance[i]` is the distance between the stops number `i` and `(i + 1) % n`.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given `start` and `destination` stops.

See the [distance between bus stops problem on LeetCode](https://leetcode.com/problems/distance-between-bus-stops).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    int clockwise = 0;
    int node = start;
    while (node != destination) {
      clockwise += distance[node];
      node = (node + 1) % distance.size();
    }

    int counterclockwise = 0;
    node = destination;
    while (node != start) {
      counterclockwise += distance[node];
      node = (node + 1) % distance.size();
    }

    return min(clockwise, counterclockwise);
  }
};
```


Solution for a bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n. The bus goes along both directions i.e. clockwise and counterclockwise. Return the shortest distance between the given start and destination stops.

Distance between Bus Stops

LeetCode Distance between Bus Stops Solution


# Distribute Candies Problem & Solution

Alice has `n` candies, where the ith candy is of type `candyType[i]`.
Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat `n / 2` of the candies she has (`n` is always even).
Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array `candyType` of length `n`, return the maximum number of different types of candies she can eat if she only eats `n / 2` of them.

See the [distribute candies problem on LeetCode](https://leetcode.com/problems/distribute-candies).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int distributeCandies(vector<int>& candyType) {
    unordered_set<int> uniques;

    for (int i = 0; i < candyType.size(); ++i) {
      uniques.insert(candyType[i]);
    }

    return min(uniques.size(), candyType.size() / 2);
  }
};
```


Solution for the distribute candies problem from LeetCode.

Distribute Candies

LeetCode Distribute Candies Solution


# Duplicate Zeros Problem & Solution

See the [duplicate zeros problem on LeetCode](https://leetcode.com/problems/duplicate-zeros).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  void duplicateZeros(vector<int>& arr) {
    int count = 0;
    int size = arr.size() - 1;
    for (int i = 0; i <= size - count; ++i) {
      if (arr[i] == 0) {
        if (i == size - count) {
          arr[size--] = 0;
          break;
        }

        ++count;
      }
    }

    for (int i = size - count; i >= 0; —i) {
      if (arr[i] == 0) {
        arr[i + count--] = 0;
        arr[i + count] = 0;
      } else {
        arr[i + count] = arr[i];
      }
    }
  }
};
```


Solution for the duplicate zeros problem from LeetCode.

Duplicate Zeros

LeetCode Duplicate Zeros Solution


# Excel Sheet Column Number Problem & Solution

Given a string `columnTitle` that represents the column title as appears in an Excel sheet, return its corresponding column number.

See the [Excel sheet column number problem on LeetCode](https://leetcode.com/problems/excel-sheet-column-number).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int titleToNumber(string columnTitle) {
    int result = 0;

    for (int i = 0; i < columnTitle.size(); ++i) {

      // The parentheses to calculate the digits are used to avoid overflow.
      result = result * 26 + (columnTitle[i] - 'A' + 1);
    }

    return result;
  }
};
```


Solution for given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

Excel Sheet Column Number

LeetCode Excel Sheet Column Number Solution


# Excel Sheet Column Title Problem & Solution

Given an integer `columnNumber`, return its corresponding column title as it appears in an Excel sheet.

See the [Excel sheet column title problem on LeetCode](https://leetcode.com/problems/excel-sheet-column-title).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string convertToTitle(int columnNumber) {
    string result;

    while (columnNumber > 0) {

      // Must take into account the offset of the column number.
      --columnNumber;

      result += columnNumber % 26 + 'A';
      columnNumber /= 26;
    }

    reverse(result.begin(), result.end());

    return result;
  }
};
```


Solution for the Excel sheet column title problem from LeetCode.

Excel Sheet Column Title

LeetCode Excel Sheet Column Title Solution


# Factorial Trailing Zeroes Problem & Solution

Given an integer `n`, return the number of trailing zeroes in `n!`.

See the [factorial trailing zeroes problem on LeetCode](https://leetcode.com/problems/factorial-trailing-zeroes).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int trailingZeroes(int n) {
    int result = 0;

    // Sums up the powers of 5 at each step, skipping other factors than 5.
    while (n > 0) {
      result += n / 5;
      n /= 5;
    }

    return result;
  }
};
```


Solution for the factorial trailing zeroes problem from LeetCode.

Factorial Trailing Zeroes

LeetCode Factorial Trailing Zeroes Solution


# Fibonacci Number Problem & Solution

The Fibonacci numbers, commonly denoted `F(n)` form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.
That is,

```
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
```

Given `n`, calculate `F(n)`.

See the [fibonacci number problem on LeetCode](https://leetcode.com/problems/fibonacci-number).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int fib(int n) {
    if (n == 0) {
      return 0;
    } else if (n == 1) {
      return 1;
    } else {
      int first = 0;
      int second = 1;

      for (int i = 2; i <= n; ++i) {
        int tmp = first + second;

        first = second;
        second = tmp;
      }

      return second;
    }
  }
};
```


Solution for the Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Fibonacci Number

LeetCode Fibonacci Number Solution


# Find All Numbers Disappeared in an Array Problem & Solution

Given an array `nums` of `n` integers where `nums[i]` is in the range `[1, n]`, return an array of all the integers in the range `[1, n]` that do not appear in `nums`.

See the [find all numbers disappeared in an array problem on LeetCode](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> findDisappearedNumbers(vector<int>& nums) {
    vector<int> results;

    for (int i = 0; i < nums.size(); ++i) {
      int j = abs(nums[i]);
      if (nums[j - 1] > 0) {

        // Flips the sign for the positions of the numbers we iterated on.
        nums[j - 1] *= -1;
      }
    }

    for (int i = 0; i < nums.size(); ++i) {

      // The missing numbers will be the positions which are still positive integers.
      if (nums[i] > 0) {
        results.push_back(i + 1);
      }
    }

    return results;
  }
};
```


Solution for given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Find All Numbers Disappeared in an Array

LeetCode Find All Numbers Disappeared in an Array Solution


# Find Common Characters Problem & Solution

Given a string array `words`, return an array of all characters that show up in all strings within the `words` (including duplicates).
You may return the answer in any order.

See the [find common characters problem on LeetCode](https://leetcode.com/problems/find-common-characters).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<string> commonChars(vector<string>& words) {
    vector<int> freq('z' - 'a' + 1, numeric_limits<int>::max());
    for (int i = 0; i < words.size(); ++i) {
      vector<int> row('z' - 'a' + 1, 0);
      for (int j = 0; j < words[i].size(); ++j) {
        ++row[words[i][j] - 'a'];
      }

      for (int j = 0; j < row.size(); ++j) {
        freq[j] = min(freq[j], row[j]);
      }
    }

    vector<string> result;
    for (int i = 0; i < freq.size(); ++i) {
      for (int j = 0; j < freq[i]; ++j) {
        result.push_back(string(1, i + 'a'));
      }
    }

    return result;
  }
};
```


Solution for given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

Find Common Characters

LeetCode Find Common Characters Solution


# Find Pivot Index Problem & Solution

Given an array of integers `nums`, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

See the [find pivot index problem on LeetCode](https://leetcode.com/problems/find-pivot-index).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int pivotIndex(vector<int>& nums) {

    // Memoizes the sums from left to right.
    vector<int> leftSum(nums.size(), 0);
    for (int i = 1; i < nums.size(); ++i) {
      leftSum[i] = leftSum[i - 1] + nums[i - 1];
    }

    // Memoizes the sums from right to left.
    vector<int> rightSum(nums.size(), 0);
    for (int i = nums.size() - 2; i >= 0; --i) {
      rightSum[i] = rightSum[i + 1] + nums[i + 1];
    }

    for (int i = 0; i < nums.size(); ++i) {
      if (leftSum[i] == rightSum[i]) {
        return i;
      }
    }

    return -1;
  }
};
```


Solution for given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right. If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array. Return the leftmost pivot index. If no such index exists, return -1.

Find Pivot Index

LeetCode Find Pivot Index Solution


# Find Smallest Letter Greater Than Target Problem & Solution

Given a characters array `letters` that is sorted in non-decreasing order and a character `target`, return the smallest character in the array that is larger than `target`.

Note that the letters wrap around.

For example, if `target == 'z'` and `letters == ['a', 'b']`, the answer is `'a'`.

See the [find smallest letter greater than target problem on LeetCode](https://leetcode.com/problems/find-smallest-letter-greater-than-target).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  char nextGreatestLetter(vector<char>& letters, char target) {
    int low = 0;
    int high = letters.size() - 1;
    while (low < high) {
      int mid = low + (high - low) / 2;
      if (letters[mid] < target) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    if (letters[low] == target) {
      while (low < letters.size() && letters[low] == target) {
        ++low;
      }

      return letters[low < letters.size() ? low : 0];
    } else if (letters[low] > target) {
      return letters[low];
    } else {
      return letters[0];
    }
  }
};
```


Solution for given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target. Note that the letters wrap around. For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

LeetCode

Problems and Solutions