Array (DSA - 5)

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