Leetcode Patterns & Related Problems
This page summarizes Leetcode problems by their core algorithmic patterns. Use it to quickly find related problems and practice similar techniques.
How to Use This Page
- Find a pattern you want to practice;
- Try all problems in that group to master the technique;
- Understand the similarities and differences between problems to deepen your understanding;
- Good reference for catorizing Leetcode problems;
Prefix Sum
Show C++ Solution
C++
class Solution {
public:
int maxFrequency(vector<int>& nums, int k, int numOperations) {
int count[100001] = {0};
for (auto c : nums)
count[c]++;
for (int i = 1; i <= 100000; i++)
count[i] += count[i-1];
int ans = 0;
for(int c = 0; c <= 100000; c++) {
int l = c-k-1;
int left = l < 0? 0 : count[l];
int r = c+k;
int right = r > 100000? count[100000] : count[r];
int freq = count[c] - (c ? count[c-1]: 0);
ans = max(ans, min(right - left - freq, numOperations) + freq);
}
return ans;
}
};
DFS + Backtracking + DP + Bit Manipulation
How to select items to reach a specific value (similar to knapsack problems but it is a bit different):
Show C++ Solution
C++
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2) return false;
int target = sum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
for (int i = target; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
};
Show C++ Solution
C++
class Solution {
public:
//dfs -> dfs + dp -> how to achieve dp -> bit as key
unordered_map<int, bool> m;
bool helper(vector<int>& nums, int k, int target, int cur, int visited){
if(m.count(visited))
return m[visited];
if(k == 0){
m[visited] = true;
return true;
}
if(cur > target){
m[visited] = false;
return false;
}
if(cur == target){
m[visited] = helper(nums, k-1, target, 0, visited);
return m[visited];
}
for(int i = 0; i < nums.size(); i++){
if((visited & (1 << i)) == 0 && target >= cur + nums[i]){
int last = visited;
visited |= 1 << i;
bool temp = helper(nums, k, target, cur+nums[i], visited);
if(temp){
m[visited] =true;
return true;
}
visited = last;
}
}
m[visited] = false;
return false;
}
bool makesquare(vector<int>& m) {
int val = accumulate(m.begin(), m.end(), 0);
if (val%4) return false;
return helper(m, 4, val/4, 0, 0);
}
};
Show C++ Solution
C++
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k) return false;
int target = sum / k;
sort(nums.rbegin(), nums.rend());
vector<bool> used(nums.size(), false);
function<bool(int, int, int)> dfs = [&](int start, int curSum, int count) {
if (count == k) return true;
if (curSum == target) return dfs(0, 0, count + 1);
for (int i = start; i < nums.size(); ++i) {
if (!used[i] && curSum + nums[i] <= target) {
used[i] = true;
if (dfs(i + 1, curSum + nums[i], count)) return true;
used[i] = false;
}
}
return false;
};
return dfs(0, 0, 0);
}
};
Show C++ Solution
C++
class Solution {
public:
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= capacity; ++w) {
dp[i][w] = dp[i-1][w];
if (w >= weights[i-1])
dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
}
}
return dp[n][capacity];
}
};
Bit Manipulation
Show C++ Solution
C++
class Solution {
public:
int minFlips(int a, int b, int c) {
int flips = 0;
for (int i = 0; i < 32; ++i) {
int bitA = (a >> i) & 1;
int bitB = (b >> i) & 1;
int bitC = (c >> i) & 1;
if ((bitA | bitB) != bitC) {
flips += bitC ? 1 : 2;
}
}
return flips;
}
};
Show C++ Solution
C++
class Solution {
public:
long long maximumOr(vector<int>& nums, int k) {
vector<int> count(32, 0);
for (auto& c : nums) {
for (int i = 0; i < 32; i++) {
if ((c>>i) & 1)
count[i]++;
}
}
long long ans = 0;
for (auto& c : nums) {
auto t = count;
for (int i = 0; i < 32; i++) {
if ((c>>i) & 1)
t[i]--;
}
long long cur = ((long long)c << k);
for (int i = 0; i < 32; i++) {
if (t[i])
cur |= (1 << i);
}
ans = max(ans, cur);
}
return ans;
}
};
Standard DP Problem
One dimensional or two dimensional or three dimensional DP problems:
Show C++ Solution
C++
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
unordered_map<string, int> memo;
function<int(vector<int>&)> dfs = [&](vector<int>& currNeeds) {
string key = "";
for (int n : currNeeds) key += to_string(n) + ",";
if (memo.count(key)) return memo[key];
int minCost = 0;
for (int i = 0; i < currNeeds.size(); ++i) {
minCost += currNeeds[i] * price[i];
}
for (const auto& offer : special) {
vector<int> nextNeeds = currNeeds;
bool valid = true;
for (int i = 0; i < currNeeds.size(); ++i) {
nextNeeds[i] -= offer[i];
if (nextNeeds[i] < 0) {
valid = false;
break;
}
}
if (valid) {
minCost = min(minCost, offer.back() + dfs(nextNeeds));
}
}
memo[key] = minCost;
return minCost;
};
return dfs(needs);
}
};
Show C++ Solution
C++
class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = dp[i][j - 1] + 1;
for (int k = i; k < j; ++k) {
if (s[k] == s[j]) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1]);
}
}
}
}
return dp[0][n - 1];
}
};
DFS
Show C++ Solution
C++
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return buildBST(nums, 0, nums.size() - 1);
}
private:
TreeNode* buildBST(const vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildBST(nums, left, mid - 1);
root->right = buildBST(nums, mid + 1, right);
return root;
}
};
Show C++ Solution
C++
class Solution {
public:
bool isSubPath(ListNode* head, TreeNode* root) {
if (!root) return false;
return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
}
private:
bool dfs(ListNode* head, TreeNode* node) {
if (!head) return true;
if (!node) return false;
if (head->val != node->val) return false;
return dfs(head->next, node->left) || dfs(head->next, node->right);
}
};
Show C++ Solution
C++
class Solution {
public:
void dfs(int node, const unordered_map<int, vector<int>>& graph, vector<bool>& visited, int& count) {
visited[node] = true;
count++;
for (int neighbor : graph.at(node)) {
if (!visited[neighbor]) {
dfs(neighbor, graph, visited, count);
}
}
}
long long countPairs(int n, vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graph;
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
for (int i = 0; i < n; ++i) {
if (!graph.count(i)) graph[i] = {};
}
vector<bool> visited(n, false);
long long totalPairs = (long long)n * (n - 1) / 2;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
int componentSize = 0;
dfs(i, graph, visited, componentSize);
totalPairs -= (long long)componentSize * (componentSize - 1) / 2;
}
}
return totalPairs;
}
};
Show C++ Solution
C++
class Solution {
public:
int helper(const unordered_map<int, vector<int>>& graph, int node, int parent, int& ans) {
int pre = -1, acc = 1;
bool same = true;
bool isLeaf = true;
for (int neighbor : graph.at(node)) {
if (neighbor == parent) continue;
isLeaf = false;
int temp = helper(graph, neighbor, node, ans);
if (pre == -1)
pre = temp;
else if (pre != temp)
same = false;
acc += temp;
}
if (isLeaf || same) ans++;
return acc;
}
int countGoodNodes(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graph;
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
int ans = 0;
helper(graph, 0, -1, ans);
return ans;
}
};
BFS
Show C++ Solution
C++
class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<vector<bool>>> visited(m, vector<vector<bool>>(n, vector<bool>(k + 1, false)));
queue<tuple<int, int, int>> q; // (row, col, remaining k)
q.push({0, 0, k});
visited[0][0][k] = true;
int steps = 0;
vector<int> directions = {0, 1, 0, -1, 0};
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto [row, col, remK] = q.front();
q.pop();
if (row == m - 1 && col == n - 1) return steps;
for (int d = 0; d < 4; ++d) {
int newRow = row + directions[d];
int newCol = col + directions[d + 1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
int newRemK = remK - grid[newRow][newCol];
if (newRemK >= 0 && !visited[newRow][newCol][newRemK]) {
visited[newRow][newCol][newRemK] = true;
q.push({newRow, newCol, newRemK});
}
}
}
}
steps++;
}
return -1;
}
};
Union Find
Consider use DFS or BFS first, if not work, then use Union Find. Here just show Union Find solutions that can be resolved by DFS or BFS as well:
Show C++ Solution
C++
class Solution {
public:
int find(int x, vector<int>& parent) {
if (parent[x] != x) {
parent[x] = find(parent[x], parent);
}
return parent[x];
}
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
vector<int> parent(n);
for (int i = 0; i < n; ++i) parent[i] = i;
int components = n;
for (const auto& conn : connections) {
int rootA = find(conn[0], parent);
int rootB = find(conn[1], parent);
if (rootA != rootB) {
parent[rootA] = rootB;
components--;
}
}
return components - 1;
}
};
Linked List
Problems involving manipulation of linked lists, including traversal, modification, and insertion:
Show C++ Solution
C++
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* curr = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = carry;
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
}
return dummy.next;
}
};
Show C++ Solution
C++
class Solution {
public:
ListNode* insertGreatestCommonDivisors(ListNode* head) {
ListNode* curr = head;
while (curr && curr->next) {
int gcd = __gcd(curr->val, curr->next->val);
ListNode* node = new ListNode(gcd);
node->next = curr->next;
curr->next = node;
curr = node->next;
}
return head;
}
};
Stack
Problems involving using stack data structure for solving problems:
Show C++ Solution
C++
class Solution {
public:
bool isValid(string s) {
string temp;
unordered_map<char, char> m = {{')', '('}, {']', '['}, {'}', '{'},};
for (auto c : s) {
if (!m.count(c)) temp+= c;
else {
if (temp.empty() || temp.back() != m[c]) return false;
temp.pop_back();
}
}
return temp.size() == 0;
}
};
Show C++ Solution
C++
class Solution {
public:
int minLength(string s) {
string stack;
for (char c : s) {
if (!stack.empty() && ((c == 'B' && stack.back() == 'A') || (c == 'D' && stack.back() == 'C'))) {
stack.pop_back();
} else {
stack.push_back(c);
}
}
return stack.size();
}
};
Braintease + Thinking (Analysis) + Simulation
Problems involving creative problem solving, array manipulation, and simulating real-world processes:
Show C++ Solution
C++
class Solution {
public:
int getLastMoment(int n, vector<int>& left, vector<int>& right) {
int res = 0;
for (int x : left) res = max(res, x);
for (int x : right) res = max(res, n - x);
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
// Simulate the falling path of each ball
vector<int> findBall(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> res(n, 0);
for (int j = 0; j < n; ++j) {
int col = j;
for (int i = 0; i < m; ++i) {
int dir = grid[i][col];
col += dir;
if (col < 0 || col >= n || grid[i][col] != dir) {
col = -1;
break;
}
}
res[j] = col;
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int countPermutations(vector<int>& complexity) {
int n = complexity.size();
long long MOD = 1e9 + 7;
// Step 1: Verify if computer 0 is strictly the smallest.
// If any other computer has equal or lower complexity, it cannot be unlocked.
for (int i = 1; i < n; ++i) {
if (complexity[i] <= complexity[0]) {
return 0;
}
}
// Step 2: If computer 0 is the strict minimum, it can unlock everything.
// Any permutation of the remaining (n-1) computers is valid.
long long ans = 1;
for (int i = 1; i < n; ++i) {
ans = (ans * i) % MOD;
}
return (int)ans;
}
};
Math
Problems involving mathematical concepts:
Show C++ Solution
C++
// Geometry problem: calculate area of two rectangles minus overlapping area
class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int areaA = (ax2 - ax1) * (ay2 - ay1);
int areaB = (bx2 - bx1) * (by2 - by1);
int overlapWidth = max(0, min(ax2, bx2) - max(ax1, bx1));
int overlapHeight = max(0, min(ay2, by2) - max(ay1, by1));
int overlapArea = overlapWidth * overlapHeight;
return areaA + areaB - overlapArea;
}
};
Show C++ Solution
C++
string fractionAddition(string expression) {
istringstream in(expression);
int A = 0, B = 1, a, b;
char _;
while (in >> a >> _ >> b) {
A = A * b + a * B;
B *= b;
int g = abs(__gcd(A, B));
A /= g;
B /= g;
}
return to_string(A) + '/' + to_string(B);
}
Show C++ Solution
C++
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
long long res = 0, count = 0;
for (int num : nums) {
if (num == 0) {
count++;
res += count;
} else {
count = 0;
}
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int alternateDigitSum(int n) {
int sum = 0, sign = 1;
while (n > 0) {
sum += sign * (n % 10);
n /= 10;
sign *= -1;
}
return sum * (-sign);
}
};
Binary Tree or Binary Search Tree
Problems involving binary tree or binary search trees, mostly about recursion:
Show C++ Solution
C++
class Solution {
public:
void inorder(TreeNode* root, vector<int>& vals) {
if (!root) return;
inorder(root->left, vals);
vals.push_back(root->val);
inorder(root->right, vals);
}
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
vector<int> vals;
inorder(root, vals);
vector<vector<int>> res;
for (int q : queries) {
auto it = lower_bound(vals.begin(), vals.end(), q);
int floor = -1, ceil = -1;
if (it != vals.end() && *it == q) {
floor = ceil = q;
} else {
if (it != vals.end()) ceil = *it;
if (it != vals.begin()) floor = *(prev(it));
}
res.push_back({floor, ceil});
}
return res;
}
};
Sorting - both O(n log n) and O(n)
Show C++ Solution
C++
class Solution {
public:
int sum = 0;
TreeNode* bstToGst(TreeNode* root) {
if (!root) return nullptr;
bstToGst(root->right);
sum += root->val;
root->val = sum;
bstToGst(root->left);
return root;
}
};
Show C++ Solution
C++
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int res = INT_MAX;
for (int i = 0; i <= nums.size() - k; ++i) {
res = min(res, nums[i + k - 1] - nums[i]);
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {
unordered_set<string> pos(positive_feedback.begin(), positive_feedback.end());
unordered_set<string> neg(negative_feedback.begin(), negative_feedback.end());
vector<pair<int, int>> scores;
for (int i = 0; i < report.size(); ++i) {
int score = 0;
stringstream ss(report[i]);
string word;
while (ss >> word) {
if (pos.count(word)) score += 3;
else if (neg.count(word)) score -= 1;
}
scores.push_back({-score, student_id[i]});
}
sort(scores.begin(), scores.end());
vector<int> res;
for (int i = 0; i < k; ++i) {
res.push_back(scores[i].second);
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int maxProduct(int n)
{
int max1 = -1, max2 = -1;
while (n > 0) {
int digit = n % 10;
if (digit > max1) {
max2 = max1;
max1 = digit;
} else if (digit > max2) {
max2 = digit;
}
n /= 10;
}
return max1 * max2;
}
};
Binary Search
Show C++ Solution
C++
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int n = nums.size();
int totalMissing = nums[n - 1] - nums[0] - (n - 1);
if (k > totalMissing) {
return nums[n - 1] + (k - totalMissing);
}
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int missingUntilMid = nums[mid] - nums[0] - mid;
if (missingUntilMid < k) {
left = mid + 1;
} else {
right = mid;
}
}
int missingUntilLeftMinusOne = nums[left - 1] - nums[0] - (left - 1);
return nums[left - 1] + (k - missingUntilLeftMinusOne);
}
};
Show C++ Solution
C++
class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int n = mountainArr.length();
int left = 0, right = n - 1;
// Find peak index
while (left < right) {
int mid = left + (right - left) / 2;
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
int peak = left;
// Search in the ascending part
left = 0; right = peak;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = mountainArr.get(mid);
if (val == target) return mid;
if (val < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// Search in the descending part
left = peak; right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = mountainArr.get(mid);
if (val == target) return mid;
if (val > target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};
Show C++ Solution
C++
class Solution {
public:
int minOperations(vector<int>& target, vector<int>& arr) {
// LCS O(mn) -> LIS O(nlgn)
unordered_map<int, int> pos;
for (int i = 0; i < target.size(); ++i) {
pos[target[i]] = i;
}
vector<int> lis;
for (int num : arr) {
if (pos.count(num)) {
int index = pos[num];
auto it = lower_bound(lis.begin(), lis.end(), index);
if (it == lis.end()) {
lis.push_back(index);
} else {
*it = index;
}
}
}
return target.size() - lis.size();
}
};
Show C++ Solution
C++
class RangeFreqQuery {
unordered_map<int, vector<int>> indices;
public:
RangeFreqQuery(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) {
indices[arr[i]].push_back(i);
}
}
int query(int left, int right, int value) {
if (!indices.count(value)) return 0;
const auto& vec = indices[value];
int l = lower_bound(vec.begin(), vec.end(), left) - vec.begin();
int r = upper_bound(vec.begin(), vec.end(), right) - vec.begin();
return r - l;
}
};
Hashing
Problems involving hashing and count frequencies of elements:
Show C++ Solution
C++
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (const string& s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[key].push_back(s);
}
vector<vector<string>> res;
for (auto& p : groups) res.push_back(p.second);
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
unordered_map<string, vector<string>> groups;
for (const string& s : strings) {
string key;
for (int i = 1; i < s.size(); ++i) {
int diff = (s[i] - s[i-1] + 26) % 26;
key += to_string(diff) + ",";
}
groups[key].push_back(s);
}
vector<vector<string>> res;
for (auto& p : groups) res.push_back(p.second);
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int flipgame(vector<int>& fronts, vector<int>& backs) {
unordered_set<int> same;
for (int i = 0; i < fronts.size(); ++i) {
if (fronts[i] == backs[i]) {
same.insert(fronts[i]);
}
}
int res = INT_MAX;
for (int x : fronts) {
if (!same.count(x)) res = min(res, x);
}
for (int x : backs) {
if (!same.count(x)) res = min(res, x);
}
return res == INT_MAX ? 0 : res;
}
};
Show C++ Solution
C++
class Solution {
public:
vector<string> removeAnagrams(vector<string>& words) {
vector<string> res;
for (const string& w : words) {
if (res.empty() || !isAnagram(res.back(), w)) {
res.push_back(w);
}
}
return res;
}
bool isAnagram(const string& a, const string& b) {
if (a.size() != b.size()) return false;
vector<int> count(26, 0);
for (char c : a) count[c - 'a']++;
for (char c : b) count[c - 'a']--;
for (int c : count) if (c != 0) return false;
return true;
}
};
Show C++ Solution
C++
class Solution {
public:
int minimumLength(string s) {
unordered_map<char, int> c;
for (auto d : s)
c[d]++;
int ans = 0;
for (auto d : c)
if (d.second % 2 == 1)
ans++;
else
ans += 2;
return ans;
}
};
Show C++ Solution
C++
class Solution {
public:
int minOperations(vector<int>& nums, int k) {
if (*min_element(nums.begin(), nums.end()) < k)
return -1;
unordered_set<int> s(nums.begin(), nums.end());
return s.count(k) ? s.size() - 1 : s.size();
}
};
Greedy
Show C++ Solution
C++
// Solution 1: dynamic programming with greedy choice property:
// Solution 2: greedy + binary search
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int num : nums) {
auto it = lower_bound(dp.begin(), dp.end(), num);
if (it == dp.end()) {
dp.push_back(num);
} else {
*it = num;
}
}
return dp.size();
}
};
Show C++ Solution
C++
// This is similar to Question 300. Longest Increasing Subsequence
// but with non-decreasing sequence, so we use upper_bound instead of lower_bound
class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> dp, res;
for (int obs : obstacles) {
auto it = upper_bound(dp.begin(), dp.end(), obs);
if (it == dp.end()) {
dp.push_back(obs);
res.push_back(dp.size());
} else {
*it = obs;
res.push_back(it - dp.begin() + 1);
}
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int minMoves(int target, int maxDoubles) {
int moves = 0;
while (target > 1 && maxDoubles > 0) {
if (target % 2 == 0) {
target /= 2;
maxDoubles--;
} else {
target -= 1;
}
moves++;
}
return moves + target - 1;
}
};
Show C++ Solution
C++
class Solution {
public:
long long maximumImportance(int n, vector<vector<int>>& roads) {
vector<int> degree(n, 0);
for (const auto& road : roads) {
degree[road[0]]++;
degree[road[1]]++;
}
sort(degree.begin(), degree.end());
long long res = 0;
for (int i = 0; i < n; ++i) {
res += 1LL * degree[i] * (i + 1);
}
return res;
}
};
Heap
Use heap to manage a dynamic set of elements, allowing for efficient retrieval of the largest or smallest elements, and design the data structure accordingly:
Show C++ Solution
C++
class MedianFinder {
priority_queue<int, vector<int>, greater<int>> pq1; // minimum
priority_queue<int, vector<int>, less<int>> pq2; // maximum
public:
MedianFinder() {
}
void addNum(int num) {
pq2.push(num);
pq1.push(pq2.top());
pq2.pop();
while(pq1.size() - pq2.size() > 1) {
int val = pq1.top();
pq1.pop();
pq2.push(val);
}
}
double findMedian() {
return pq1.size() == pq2.size()? ((double)pq1.top() + pq2.top()) / 2 : pq1.top();
}
};
Simple heap usage:
Show C++ Solution
C++
class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
long long res = 0;
for (int i = 0; i < k; ++i) {
int top = pq.top(); pq.pop();
res += top;
pq.push((top + 2) / 3);
}
return res;
}
};
Segment Tree
Use segment tree to efficiently perform range queries and updates on an array, and design the data structure accordingly.
See problem list here.
Binary Indexed Tree (BIT - also called Fenwick Tree)
Show C++ Solution
C++
// Prefix sum -> BIT or Segment Tree
class NumArray {
vector<int> bit;
vector<int> nums;
int n;
public:
NumArray(vector<int>& nums) {
this->n = nums.size();
this->nums = nums;
bit.resize(n + 1, 0);
for (int i = 0; i < n; ++i) {
add(i + 1, nums[i]);
}
}
void add(int i, int delta) {
for (; i <= n; i += i & -i) bit[i] += delta;
}
int sumPrefix(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
void update(int index, int val) {
int delta = val - nums[index];
nums[index] = val;
add(index + 1, delta);
}
int sumRange(int left, int right) {
return sumPrefix(right + 1) - sumPrefix(left);
}
};
Count Elements By Subarray
Show C++ Solution
C++
class Solution {
public:
int uniqueLetterString(string s) {
vector<vector<int>> pos(26);
for (int i = 0; i < 26; i++) pos[i].push_back(-1);
for (int i = 0; i < s.size(); i++) pos[s[i]-'A'].push_back(i);
for (int i = 0; i < 26; i++) pos[i].push_back(s.size());
int ans = 0;
for (int i = 0; i < 26; i++) {
for (int j = 1; j < pos[i].size() - 1; j++) {
ans += (pos[i][j] - pos[i][j-1]) * (pos[i][j+1] - pos[i][j]);
}
}
return ans;
}
};
Two Pointers
Show C++ Solution
C++
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0, valid = 0;
int start = 0, len = INT_MAX;
while (right < s.size()) {
char c = s[right];
right++;
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) valid++;
}
while (valid == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] == need[d]) valid--;
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
Show C++ Solution
C++
class Solution {
public:
void reverseWords(vector<char>& s) {
// space O(1) is important for this question
reverse(s.begin(), s.end());
int index = 0;
while(index < s.size()) {
int b = index;
while(index < s.size() && s[index] != ' ') index++;
reverse(s.begin() + b, s.begin() + index);
index++;
}
}
};
Show C++ Solution
C++
class Solution {
public:
bool checkPalindromeFormation(string a, string b) {
return check(a, b) || check(b, a);
}
private:
bool isPal(const string &s, int l, int r) {
while (l < r && s[l] == s[r]) { l++; r--; }
return l >= r;
}
bool check(const string &a, const string &b) {
int i = 0, j = (int)a.size() - 1;
while (i < j && a[i] == b[j]) { i++; j--; }
return isPal(a, i, j) || isPal(b, i, j);
}
};
Show C++ Solution
C++
class Solution {
public:
bool canMakeSubsequence(string str1, string str2) {
int i = 0, j = 0;
while (i < str1.size() && j < str2.size()) {
if (str1[i] == str2[j] || (str1[i] + 1 - 'a') % 26 + 'a' == str2[j]) {
j++;
}
i++;
}
return j == str2.size();
}
};
Simulation + Digital Counting and Finding
Show C++ Solution
C++
class Solution {
public:
char kthCharacter(long long k, const vector<int>& ops) {
const long long INF = (long long)4e18;
long long len = 1;
int n = ops.size(), i = 0, shift = 0;
while (i < n && len < k) { len = min(INF, len * 2); ++i; }
for (int j = i - 1; j >= 0; --j) {
long long half = len / 2;
if (k > half) {
k -= half;
if (ops[j] == 1) shift = (shift + 1) % 26;
}
len = half;
}
return char('a' + shift);
}
};
Geometry
Show C++ Solution
C++
class Solution {
public:
int numberOfPairs(vector<vector<int>>& p) {
sort(p.begin(), p.end(), [](vector<int>& a, vector<int>& b) {
if (a[0] == b[0])
return a[1] > b[1];
return a[0] < b[0];
});
int ans = 0;
for (int i = 0; i < p.size(); i++) {
int y = INT_MIN;
for (int j = i + 1; j < p.size(); j++) {
if (p[j][1] <= p[i][1] && y < p[j][1]) {
ans++;
y = p[j][1];
}
}
}
return ans;
}
};
Game Theory
Check the Problems List.
Show C++ Solution
C++
class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};
Sliding Window
Show C++ Solution
C++
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
string t = "123456789";
for (int len = 1; len <= t.size(); len++) {
for (int i = 0; i <= t.size() - len; i++) {
int v = stoi(t.substr(i, len));
if (v >= low && v <= high)
ans.push_back(v);
}
}
return ans;
}
};
Kadane's Algorithm
Show C++ Solution
C++
class Solution {
public:
int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int total1 = accumulate(nums1.begin(), nums1.end(), 0);
int total2 = accumulate(nums2.begin(), nums2.end(), 0);
int maxDiff1 = kadane(nums1, nums2);
int maxDiff2 = kadane(nums2, nums1);
return max(total1 + maxDiff1, total2 + maxDiff2);
}
private:
int kadane(const vector<int>& a, const vector<int>& b) {
int maxEndingHere = 0;
int maxSoFar = 0;
for (int i = 0; i < a.size(); ++i) {
maxEndingHere = max(0, maxEndingHere + b[i] - a[i]);
maxSoFar = max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
};
Backtracking
Show C++ Solution
C++
class Solution {
public:
vector<int> splitIntoFibonacci(string s) {
vector<int> res;
backtrack(s, res, 0);
return res;
}
private:
bool backtrack(const string& s, vector<int>& res, int index) {
if (index == s.size() && res.size() >= 3) {
return true;
}
long long num = 0;
for (int i = index; i < s.size(); ++i) {
if (i > index && s[index] == '0') break; // leading zero
num = num * 10 + (s[i] - '0');
if (num > INT_MAX) break;
if (res.size() >= 2) {
long long sum = (long long)res[res.size() - 1] + res[res.size() - 2];
if (num < sum) continue;
if (num > sum) break;
}
res.push_back((int)num);
if (backtrack(s, res, i + 1)) {
return true;
}
res.pop_back();
}
return false;
}
};