1) Remove duplicates in-place from sorted array
int removeDuplicates(vector<int>& arr, int n) {
if (n == 0) return 0;
int i = 0;
for (int j = 1; j < n; j++) {
if (arr[i] != arr[j]) {
i++;
arr[i] = arr[j];
}
}
return i + 1;
}
2) Move zeros to the end
vector<int> moveZeros(vector<int>& arr) {
int n = arr.size();
int nonZeroIndex = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] != 0) {
swap(arr[i], arr[nonZeroIndex]);
nonZeroIndex++;
}
}
return arr;
}
3) Find Missing Number
int findMissingNumber(const vector<int>& arr, int n) {
int xorArray = 0;
int xorRange = 0;
// XOR all elements in the array
for (int num : arr) {
xorArray ^= num;
}
// XOR all numbers from 1 to n
for (int i = 1; i <= n; ++i) {
xorRange ^= i;
}
return xorArray ^ xorRange;
}
int findMissingNumber(const vector<int>& arr, int n) {
int totalSum = n * (n + 1) / 2;
int actualSum = accumulate(arr.begin(), arr.end(), 0);
return totalSum - actualSum;
}
4) Find the number that appears once and the others twice
int singleElement(int arr[] ,int N) {
// code here
int uniqueNumber = 0;
// XOR all elements in the array
for (int num : arr) {
uniqueNumber ^= num;
}
return uniqueNumber;
}
5) Kadane Algorithm
Brute: Three loops
Optimal
int maxSubArray(const vector<int>& nums) {
int max_current = nums[0];
int max_global = nums[0];
for (size_t i = 1; i < nums.size(); i++) {
max_current = max(nums[i], max_current + nums[i]);
if (max_current > max_global) {
max_global = max_current;
}
}
return max_global;
}
6) Longest Common Sequence
int longestSuccessiveElements(std::vector<int>& nums) {
if (nums.empty()) return 0;
sort(nums.begin(), nums.end());
int n = nums.size();
int lastSmaller = INT_MIN;
int cnt = 0;
int longest = 1;
for (int i = 0; i < n; ++i) {
if (nums[i] == lastSmaller + 1) {
cnt += 1;
} else if (nums[i] != lastSmaller) {
cnt = 1;
}
lastSmaller = nums[i];
longest = max(longest, cnt);
}
return longest;
}
7) Rearrange array based on sign
vector<int> rearrangeArray(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, 0);
int posIndex = 0;
int negIndex = 1;
for (int i = 0; i < n; ++i) {
if (nums[i] < 0) {
ans[negIndex] = nums[i];
negIndex += 2;
} else {
ans[posIndex] = nums[i];
posIndex += 2;
}
}
return ans;
}
8) Majority Element (>n/2)
int majorityElement(const vector<int>& v) {
unordered_map<int, int> mpp;
for (int i = 0; i < v.size(); ++i) {
mpp[v[i]]++;
}
for (const auto& it : mpp) {
if (it.second > (v.size() / 2)) {
return it.first;
}
}
return -1;
}
int majorityElement(const vector<int>& v) {
int cnt = 0;
int el = 0;
// Phase 1: Find a candidate for the majority element
for (int i = 0; i < v.size(); ++i) {
if (cnt == 0) {
el = v[i];
cnt = 1;
} else if (v[i] == el) {
cnt++;
} else {
cnt--;
}
}
// Phase 2: Verify if the candidate is majority element
cnt = 0;
for (int i = 0; i < v.size(); ++i) {
if (v[i] == el) {
cnt++;
}
}
if (cnt > v.size() / 2) {
return el;
}
return -1;
}
9) Two sum
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> num_map;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (num_map.find(complement) != num_map.end()) {
return {num_map[complement], i};
}
num_map[nums[i]] = i;
}
return {};
}
10) Find the missing and repeating number
#include <vector>
vector<int> findMissingRepeatingNumbers(const vector<int>& a) {
int n = a.size();
vector<int> hash(n + 1, 0);
for (int i = 0; i < n; ++i) {
hash[a[i]]++;
}
int repeating = -1, missing = -1;
for (int i = 1; i <= n; ++i) {
if (hash[i] == 2) {
repeating = i;
} else if (hash[i] == 0) {
missing = i;
}
if (repeating != -1 && missing != -1) {
break;
}
}
return {repeating, missing};
}
11) Rotate Array
void leftRotate(int arr[], int n, int d) {
if (d == 0) {
return; // No rotation needed if d is 0
}
// To handle if d is greater than n
d = d % n;
int temp[d];
// Store the first d elements in temp
for (int i = 0; i < d; i++) {
temp[i] = arr[i];
}
// Shift the rest of the array
for (int i = d; i < n; i++) {
arr[i - d] = arr[i];
}
// Copy the temp elements back to the array
for (int i = 0; i < d; i++) {
arr[n - d + i] = temp[i];
}
}
12) Kth Smallest Element in a BST
void inorder(TreeNode* root,vector<int>&res){
if(root==nullptr)return;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
int kthSmallest(TreeNode* root, int k) {
vector<int> res;
inorder(root,res);
return res[k-1];
}
13) Dutch National Flag
void sortColors(vector<int>& nums) {
int low=0,mid=0;
int high=nums.size()-1;
while(mid<=high){
if(nums[mid]==0){
swap(nums[low],nums[mid]);
low++;
mid++;
}else if(nums[mid]==1){
mid++;
}else{
swap(nums[mid],nums[high]);
high--;
}
}
}
13) Stock Buy And Sell
int maxProfit(const std::vector<int>& prices) {
if (prices.empty()) return 0; // No days to trade
int min_price = prices[0]; // Initialize with the first day's price
int max_profit = 0; // No profit initially
for (int price : prices) {
// Update the minimum price encountered so far
min_price = std::min(min_price, price);
// Calculate the profit if selling at the current price
int profit = price - min_price;
// Update the maximum profit
max_profit = std::max(max_profit, profit);
}
return max_profit;
}
14) Find the missing number in an array
int findMissingNumber(const std::vector<int>& nums, int N) {
int sum_expected = N * (N + 1) / 2;
int sum_actual = 0;
for (int num : nums) {
sum_actual += num;
}
return sum_expected - sum_actual;
}
Matrix
Search an element in sorted rows
bool binarySearchRow(const vector<vector<int>>& matrix, int target) {
for (auto row : matrix) {
int low = 0, high = row.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (row[mid] == target) {
return true;
} else if (row[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return false;
}
Set Matrix to zero
vector<vector<int>> zeroMatrix(vector<vector<int>> &matrix, int n, int m) {
// Create arrays to mark rows and columns
vector<int> row(n, 0);
vector<int> col(m, 0);
// Mark rows and columns that need to be zeroed
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
col[j] = 1;
}
}
}
// Set entire rows and columns to zero based on the marks
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
return matrix;
}
Binary Search
overflow case mid=low+(high-low)/2
1) Find floor of a number
int findFloor(vector<long long>& arr, long long n, long long x) {
int low = 0, high = n - 1;
int ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2; // to avoid overflow
if (arr[mid] <= x) {
ans = arr[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
2) Find the peak element
int findPeakElement(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
while(left<right){
int mid=(left+right)/2;
if(nums[mid]>nums[mid+1]){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
Search in sorted rotated array
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]==target){
return mid;
}
if(nums[left]<=nums[mid]){
if(nums[left]<=target && target<nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
}else{
if(nums[mid]<target && target<=nums[right]){
left=mid+1;
}else{
right=mid-1;
}
}
}
return -1;
}
Median of Two Sorted Arrays of different sizes
double median(vector<int>& a, vector<int>& b) {
//size of two given arrays:
int n1 = a.size(), n2 = b.size();
vector<int> arr3;
//apply the merge step:
int i = 0, j = 0;
while (i < n1 && j < n2) {
if (a[i] < b[j]) arr3.push_back(a[i++]);
else arr3.push_back(b[j++]);
}
//copy the left-out elements:
while (i < n1) arr3.push_back(a[i++]);
while (j < n2) arr3.push_back(b[j++]);
//Find the median:
int n = n1 + n2;
if (n % 2 == 1) {
return (double)arr3[n / 2];
}
double median = ((double)arr3[n / 2] + (double)arr3[(n / 2) - 1]) / 2.0;
return median;
}
Prefix Sum
vector<int> computePrefixSum(const vector<int>& arr) {
int n = arr.size();
vector<int> prefix(n);
prefix[0] = arr[0];
// Compute prefix sums
for (int i = 1; i < n; ++i) {
prefix[i] = prefix[i - 1] + arr[i];
}
return prefix;
}
Subarray Sum Equals K
Contiguous Array
Range Sum Query - Immutable
Two pointer Approach
Sliding window
int maxSumSubarray(const std::vector<int>& nums, int k) {
int n = nums.size();
if (n < k) {
std::cerr << "The size of the array must be at least " << k << std::endl;
return -1; // Handle case where array size is less than k
}
// Calculate the sum of the first 'k' elements
int window_sum = 0;
for (int i = 0; i < k; i++) {
window_sum += nums[i];
}
int max_sum = window_sum;
// Slide the window from the start of the array to the end
for (int i = k; i < n; i++) {
window_sum = window_sum - nums[i - k] + nums[i];
max_sum = std::max(max_sum, window_sum);
}
return max_sum;
}
Stack
Stack in C++ is a data structure that follows the Last In, First Out (LIFO) principle, where the last element added is the first to be removed
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(10); // Push elements into the stack
s.pop(); // Pop the top element
s.top(); // See the top element
// Check if the stack is empty
if (s.empty()) {
cout << "Stack is empty.";
} else {
cout << "Stack is not empty.";
}
// Get the size of the stack
cout << "Stack size: " << s.size();
return 0;
}
1) Valid Parentheses
bool isValid(string s) {
stack<char> st;
for(char each:s){
if((each == ')' || each == ']' || each == '}') && st.empty()) {
return false;
}
if(each==')' && st.top()=='('){
st.pop();
}else if(each==']' && st.top()=='['){
st.pop();
}else if(each=='}' && st.top()=='{'){
st.pop();
}else{
st.push(each);
}
}
return st.empty();
}
2) Monotonic stack (Increasing)
vector<int> nextGreaterElement(const std::vector<int>& nums) {
stack<int> s;
vector<int> result(nums.size(), -1);
for (int i = 0; i < nums.size(); ++i) {
while (!s.empty() && nums[s.top()] < nums[i]) {
result[s.top()] = nums[i];
s.pop();
}
s.push(i);
}
return result;
}
Prefix infix posfix conversions
Postfix (Reverse Polish Notation )
1) Infix to Postfix
Ex. a+b*(c^d-e) -> abcd^e-*+
Rules:
-> Return operands
-> Operators and brackets are added to stack ensure that top element has more priority than below element
-> If above condition is not satisfied, it is popped out until 2nd condition is obeyed
-> When you encounter ')', pop out till you find '('
int prec(char c) {
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s) {
stack < char > st; //For stack operations, we are using C++ built in stack
string result;
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
result += c;
else if (c == '(')
st.push('(');
else if (c == ')') {
while (st.top() != '(') {
result += st.top();
st.pop();
}
st.pop();
}
//If an operator is scanned
else {
while (!st.empty() && prec(s[i]) <= prec(st.top())) {
result += st.top();
st.pop();
}
st.push(c);
}
}
// Pop all the remaining elements from the stack
while (!st.empty()) {
result += st.top();
st.pop();
}
}
2) Infix to Prefix
Rules:
-> Reverse the infix expression
-> Perform Infix to Postfix with a condition
-> Reverse the result
else {
if(s[i]=='^'){
while (!st.empty() && prec(s[i]) <= prec(st.top())) {
result += st.top();
st.pop();
}
st.push(c);
}
}else{
while (!st.empty() && prec(s[i]) < prec(st.top())) {
result += st.top();
st.pop();
}
st.push(c);
}
}
}
3) Prefix to Infix
Rules:
-> Iterate from the back
-> Operands are pushed to the stack
-> If you encounter an operator, pop two elements and wrap it up inside a bracket
string prefixToInfix(string prefix) {
stack<string> st;
// Traverse the expression from right to left
for (int i = prefix.length() - 1; i >= 0; i--) {
char each = prefix[i];
if (isalpha(each) || isdigit(each)) {
st.push(each);
} else {
string op1 = st.top(); st.pop();
string op2 = st.top(); st.pop();
// Form the infix expression and push it back to the stack
string infix = "(" + op1 + each + op2 + ")";
st.push(infix);
}
}
return st.top();
}
4) Prefix to Postfix
Rules:
-> Operands are added to the stack
-> If we encounter an operator, (operand,operand,operator) to the stack
string prefixToPostfix(string prefix) {
stack<string> st;
for (int i = prefix.length() - 1; i >= 0; i--) {
char each = prefix[i];
if (isOperand(each)) {
st.push(each);
} else {
string op1 = st.top(); st.pop();
string op2 = st.top(); st.pop();
string postfix = op1 + op2 + each;
st.push(postfix);
}
}
return st.top();
}
5) Postfix to Infix
Rules:
-> Operands are pushed into the stack
-> If you encounter an operator, pop two elements and wrap it up inside a bracket
string postfixToInfix(string postfix) {
stack<string> st;
for (char each : postfix) {
if (isalpha(each) || isdigit(each)) {
st.push(string(1, each));
} else {
string op1 = st.top(); st.pop();
string op2 = st.top(); st.pop();
string infix = "(" + op2 + each + op1 + ")";
st.push(infix);
}
}
return st.top();
}
6) Postfix to Prefix
Rules:
-> Operands are pushed
-> If we encounter an operator, (operator,operand,operand) is pushed
string postfixToPrefix(string postfix) {
stack<string> st;
for (char each : postfix) {
if (isOperand(each)) {
// If the character is an operand, push it to the stack
st.push(string(1, each));
} else {
// It's an operator, pop two elements from the stack
string op1 = st.top(); st.pop();
string op2 = st.top(); st.pop();
// Form the prefix expression and push it back to the stack
string prefix = each + op2 + op1;
st.push(prefix);
}
}
return st.top();
}
Monotonic Stack
vector<int> nextGreaterElement(vector<int>& arr) {
int n = arr.size();
vector<int> nge(n, -1);
stack<int> st;
// Iterate from the end of the array to the beginning
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && st.top() <= arr[i]) {
st.pop();
}
if (!st.empty()) {
nge[i] = st.top();
}
st.push(arr[i]);
}
return nge;
}
Stay Connected!
If you enjoyed this post, donβt forget to follow me on social media for more updates and insights:
Twitter: madhavganesan
Instagram: madhavganesan
LinkedIn: madhavganesan
Top comments (0)