BinarySearch - Set Bits

[https://binarysearch.com/problems/Set-Bits](https://binarysearch.com/problems/Set-Bits) ## Problem Given an integer n, return the total number of set bits in all integers between 1 and n inclusive. Constraints $ n ≤ 2 ^ {27} $ ## Solution The i-th least significant bit can be calculate as $$ (\frac{n}{2 ^ i}) * 2 ^{i - 1} + n \bmod 2 ^ {i} - (2 ^ {i - 1} - 1) $$ if and only if $$ n \bmod ( 2 ^ {i} ) >= (2 ^ {i - 1} - 1) $$ ``` int solve(int n) { int two = 2, ans = 0; int tmp = n; while (tmp) { ans += (n / two) * (two >> 1); if ((n & (two - 1)) > (two >> 1) - 1) ans += (n & (two - 1)) - (two >> 1) + 1; two <<= 1, tmp >>= 1; } return ans; } ```

BinarySearch - Increasing Subsequences of Size K

[https://binarysearch.com/problems/Increasing-Subsequences-of-Size-K](https://binarysearch.com/problems/Increasing-Subsequences-of-Size-K) ## Problem Given a list of integers nums and an integer k, return the number of subsequences of size k that are strictly increasing. Mod the result by 10 ** 9 + 7. Constraints 0 ≤ n ≤ 1,000 where n is the length of nums. 1 ≤ k ≤ 10 ## Solution Use Dynamic Programming. Define dp[i][j] to store the count of increasing subsequences of size i ending with element nums[j]. $dp[i][j] = 1$, where $i = 1$ and $1 <= j <= n $ $dp[i][j] = dp[i][j] + dp[i - 1][j]$, where $1 < i <= k$, $i <= j <= n$ and $nums[m] < nums[j]$ for $(i - 1) <= m < j$. Time Complexity: $O(k * n ^ 2)$ Space Complexity: $O(k * n)$ ``` int solve(vector& nums, int k) { int n = (int)nums.size(), dp[k][n], ans = 0, mod = 1e9 + 7; memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) dp[0][i] = 1; for (int l = 1; l < k; l++) { for (int i = l; i < n; i++) { dp[l][i] = 0; for (int j = l - 1; j < i; j++) { if (nums[j] < nums[i]) { dp[l][i] = (dp[l][i] + dp[l - 1][j]) % mod; } } } } for (int i = k - 1; i < n; i++) { ans = (ans + dp[k - 1][i]) % mod; } return ans; } ```

BinarySearch - Longest Increasing Path

[https://binarysearch.com/problems/Longest-Increasing-Path](https://binarysearch.com/problems/Longest-Increasing-Path) ## Problem Given a two-dimensional integer matrix, find the length of the longest strictly increasing path. You can move up, down, left, or right. Constraints n, m ≤ 500 where n and m are the number of rows and columns in matrix ## Solution DFS Approach. dp[i][j] means the length of longest increasing path starting from (i,j). Traverse four directions iff the next cell is in the bound and the value is greater than the current one. Calculate it recursively and store it back to dp[i][j]. If dp[i][j] has been calculated, return the cached result directly. ``` int m, n; vector> dp; int dfs(vector>& matrix, int i, int j) { if (dp[i][j]) return dp[i][j]; int v = 1; if (i + 1 < m && matrix[i + 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i + 1, j)); if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i - 1, j)); if (j + 1 < n && matrix[i][j + 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j + 1)); if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j - 1)); dp[i][j] = v; return dp[i][j]; } int solve(vector>& matrix) { m = matrix.size(), n = matrix[0].size(); dp = vector>(m, vector(n, 0)); int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { ans = max(ans, dfs(matrix, i, j)); } } return ans; } ```

BinarySearch - One Edit Distance

[https://binarysearch.com/problems/One-Edit-Distance](https://binarysearch.com/problems/One-Edit-Distance) ## Problem Given two strings s0 and s1 determine whether they are one or zero edit distance away. An edit can be described as deleting a character, adding a character, or replacing a character with another character. Constraints n ≤ 100,000 where n is the length of s0. m ≤ 100,000 where m is the length of s1. ## Solution Short and clean. Find the first index i that s0[i] is not equal to s1[i] Based on the length of s0 and s1, compare the rest of the sub string are same or not. ``` bool solve(string s0, string s1) { int m = s0.size(), n = s1.size(); for (int i = 0; i < min(m, n); i++) { if (s0[i] != s1[i]) { if (m == n) return s0.substr(i + 1) == s1.substr(i + 1); else if (m < n) return s0.substr(i) == s1.substr(i + 1); else return s0.substr(i + 1) == s1.substr(i); } } return abs(m - n) <= 1; } ```

BinarySearch - Escape-Maze

[https://binarysearch.com/problems/Escape-Maze](https://binarysearch.com/problems/Escape-Maze) ## Problem You are given a two dimensional integer matrix, representing a maze where 0 is an empty cell, and 1 is a wall. Given that you start at matrix[0][0], return the minimum number of squares it would take to get to matrix[R - 1][C - 1] (where R and C are the number of rows and columns in the matrix). If it's not possible, return -1. Constraints n, m ≤ 250 where n and m are the number of rows and columns in matrix ## Solution Use standard BFS. Check if the matrix[0][0] and matrix[m-1][n-1] is 1 or not. If so, return -1. Then we need a queue to store the coordinates and the local count. Starting from (0,0), go for four directions and check if the target cell is valid or not. If so, update matrix[xx][yy] so that we won't visit it again and add it to the queue. If xx and yy reaches m-1 and n-1, check if the count is the minimal. ``` int ans = INT_MAX, m, n; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; bool ok(int i, int j) { return !(i < 0 || i > m - 1 || j < 0 || j > n - 1); } int solve(vector>& matrix) { m = matrix.size(), n = matrix[0].size(); if (matrix[0][0] == 1 || matrix[m - 1][n - 1] == 1) return -1; queue, int>> q; // i, j, cnt q.push({{0, 0}, 1}); matrix[0][0] = 1; while (!q.empty()) { auto p = q.front(); q.pop(); int x = p.first.first, y = p.first.second, cnt = p.second; if (x == m - 1 && y == n - 1) ans = min(ans, cnt); for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (ok(xx, yy) && matrix[xx][yy] == 0) { matrix[xx][yy] = 1; q.push({{xx, yy}, cnt + 1}); } } } return ans == INT_MAX ? -1 : ans; } ```

BinarySearch - Sum of Two Numbers

[https://binarysearch.com/problems/Sum-of-Two-Numbers](https://binarysearch.com/problems/Sum-of-Two-Numbers) ## Problem Statement Given a list of numbers nums and a number k, return whether any two elements from the list add up to k. You may not use the same element twice. Note: Numbers can be negative or 0. Constraints n ≤ 100,000 where n is the length of nums ## Solution Use unordered_map to store the complement. If it is found, return true. If not, update m[nums[i]]. ``` bool solve(vector& nums, int k) { unordered_map m; for (int i = 0; i < nums.size(); i++) { if (m.count(k - nums[i])) return true; m[nums[i]] = i; } return false; } ```

BinarySearch - Largest Island Area

[https://binarysearch.com/problems/Largest-Island-Area](https://binarysearch.com/problems/Largest-Island-Area) ## Problem You are given a two-dimensional integer matrix of 1s and 0s. A 1 represents land and 0 represents water, so an island is a group of 1s that are neighboring whose perimeter is surrounded by water. You can assume that the edges of the matrix are surrounded by water. Return the area of the largest island in matrix. Constraints n, m ≤ 250 where n and m are the number of rows and columns in matrix ## Solution Textbook flood fill. Search the cell with value 1 to perform dfs. For each dfs, mark all visited cells to 0 so that it won't be visited again. Compare the return value with ans and take the max one. ``` int dfs(vector>& matrix, int i, int j) { if (i < 0 || i > matrix.size() - 1 || j < 0 || j > matrix[0].size() - 1 || matrix[i][j] == 0) return 0; matrix[i][j] = 0; return 1 + dfs(matrix, i + 1, j) + dfs(matrix, i - 1, j) + dfs(matrix, i, j + 1) + dfs(matrix, i, j - 1); } int solve(vector>& matrix) { int ans = 0; for (int i = 0; i < matrix.size(); i++) { for (int j = 0; j < matrix[i].size(); j++) { if (matrix[i][j] == 1) { ans = max(ans, dfs(matrix, i, j)); } } } return ans; } ```