In this article, we will discuss some of similar questions that are easy to solve with few changes in solution codes. Leetcode is a platform to practice DSA problems for those who want to learn DSA and practice these online. You can practice those DSA problems and qualify the DSA round of many product based companies to become software engineer or data scientist.
We will discuss the set of problems in this article. First we will discuss a problem with its solution and approach. Then we will solve another problem that has been solved using the same or similar approach of the first problem. Note that we will not discuss bruteforce solutions of any problem because our goal is to find an approach to solve many problems.
Let’s start to make leetcode easy to solve!
1. Fibonacci Number
This is problem number 509 in the leetcode – https://leetcode.com/problems/fibonacci-number/description/
We need to implement this sequence in C++ –
F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1
As we know that we can solve this problem using recursion. But we will solve it here using iteration to avoid any stack for recursion. Our solution is –
class Solution {
public:
int fib(int n) {
if(n < 2) return n; // base
vector<int> ans(n+1);
ans[0] = 0; // 0
ans[1] = 1;
for(int i = 2; i <= n; i++) ans[i] = ans[i-1] + ans[i-2];
return ans[n];
}
};
We just took an 1D array and filled it using the for loop according to the given recurrence relation. Then we returned the last element of this array as a result.
2. Climbing Stairs
This is problem number 78 in leetcode – https://leetcode.com/problems/climbing-stairs/description/
We can solve this problem using the same above Fibonacci number. The only difference is base value in recurrence relation. In Fib problem base values are 0 and 1, but in the Climbing stairs problem both the base values are 1.
class Solution {
public:
int climbStairs(int n) {
vector<int> ans(n+1);
ans[0] = 1;
ans[1] = 1;
for(int i = 2; i <= n; i++) ans[i] = ans[i - 1] + ans[i - 2];
return ans[n];
}
};
3. Tribonacci Number
This is problem number 1137 in the leetcode – https://leetcode.com/problems/n-th-tribonacci-number/description/
We need to solve this recurrence relation –
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
The only difference from the Fibonacci series is that the Tribonacci series have three base values. These are 0, 1, and 1. So we need to return these relevant values when the value is less than 3. Also we need to add three previous values to get the next value, unlike in fibonacci series where we need to add only the previous two values to get the next value.
class Solution {
public:
int tribonacci(int n) {
if(n == 0) return 0;
if(n < 3) return 1;
vector<int> ans(n+1);
ans[0] = 0;
ans[1] = 1;
ans[2] = 1;
for(int i = 3; i < n + 1; i++)
ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];
return ans[n];
}
};
1. Max Dept of BT
This is problem number 104 in the leetcode – https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
We need to find the maximum depth of a given binary tree. We can solve this problem simple as given here –
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return 1 + max(left, right);
}
};
If the root is empty then return 0 depth. Otherwise return 1 + max of left child and right child.
2. Min Dept of BT
This is problem number 111 in the leetcode – https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
We need to find the minimum depth of a given binary tree. We can solve this problem as above –
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
return 1 + (min(left, right) ? min(left, right) : max(left, right));
}
};
The only difference is returning value – min(left, right) ? min(left, right) : max(left, right) checks –
- If both left and right children exist, it returns the smaller depth of the two.
- If one of the subtrees is missing (0 depth). It takes the depth of the existing subtree (hence, max(left, right)).
This is case in this given binary tree –
So we need to call maximum whenever one of the sides is missing in a given binary tree.
1. Count Squares
This is problem number 1277 in the leetcode – https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/
We need to count the total number of squares that exist with number 1 in the given matrix.
We can solve this problem using a dynamic approach. We have taken 2D vector of size (rows+1)*(cols+1) and initializes all the cells with 0. We have also taken a variable “count” whose initial value is 0.
We traverse the given matrix row by row and find if the given cell has value 1.
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
if(!rows) return 0;
vector<vector<int>> table(rows + 1, vector<int>(cols + 1, 0)); // 0
int count = 0;
for(int i = 1; i < rows + 1; i++) {
for(int j = 1; j < cols + 1; j++) {
if(matrix[i - 1][j - 1] == 1) {
table[i][j] = min({table[i - 1][j - 1], table[i - 1][j], table[i][j - 1]}) + 1;
count += table[i][j];
}
}
}
return count;
}
};
We filled 2D matrix using this recurrence relation –
table[i][j] = min({table[i-1][j-1], table[i-1][j], table[i][j-1]}) + 1;
We will fill this cell if the previous cell value is 1
Then we also add this cell value to the count –
count += table[i][j];
Then we returned count as the result.
2. Max Square
This is problem number 221 in the leetcode – https://leetcode.com/problems/maximal-square/
We need to find the maximal square of ‘1’ instead of the total number of squares in the given matrix.
The solution is exactly similar as above. The only difference is that we find the maximum side of the maximum square, so we can return the size of the maximal square in the given matrix.
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
if(!rows) return 0;
vector<vector<int>> table(rows + 1, vector<int>(cols + 1, 0));
int size = 0;
for(int i = 1; i < rows + 1; i++) {
for(int j = 1; j < cols + 1; j++) {
if(matrix[i - 1][j - 1] == '1') {
table[i][j] = min({table[i - 1][j - 1], table[i - 1][j], table[i][j - 1]}) + 1;
size = max(size, table[i][j]);
}
}
}
return size * size;
}
};
Also note that in this matrix cell values have characters instead of integers.
1. Remove Duplicates from Sorted Array (allow once)
This is problem number 26 in the leetcode – https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
We need to remove all the duplicates from the array, so it will become a unique array. For example –
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
We need to return the number of unique elements remaining in the array.
The solution –
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int count = 0;
int j = 1;
for(int i = 1; i < nums.size(); i++) {
if(nums[i - 1] == nums[i]) count++;
else count = 0;
if(count < 1)
nums[j++] = nums[i];
}
return j; // number of unique elements
}
};
We take two variable count = 0 and j = 1.
We traverse the given array. For each element in the array, we compare previous elements from the current element of the array, if the same then we increase the count value. Otherwise, it is a unique element, so make count = 0.
Also if the count value is less than 1, then put this current element in place of the j index in the array, then increase the value of j.
Finally, we will return j which is the last index value of a unique element in this array.
2. Remove Duplicates from Sorted Array II (allow twice)
This is problem number 80 in the leetcode – https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/
This is a similar problem as above. The only difference is we can allow elements in twice instead of once in the array. For example –
Input: nums = [0,0,1,1,1,1,2,3,3] Output: 7, nums = [0,0,1,1,2,3,3,_,_]
So the solution is –
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int count = 0;
int j = 1;
for(int i = 1; i < nums.size(); i++) {
if(nums[i - 1] == nums[i]) count++;
else count = 0;
if(count < 2)
nums[j++] = nums[i];
}
return j; // number of unique elements
}
};
So we only difference in the if condition we have condition count<2 instead of count<1.
Conclusion
We have discussed a few similar approach leetcode problems. There are more such problems, you can understand their approach easily. You can understand one approach and implement more problems to learn efficiently and effectively.