DEV Community

Cover image for Array (DSA - 5)
Madhav Ganesan
Madhav Ganesan

Posted on

1 1 1 1 1

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode
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;

}
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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; 
}
Enter fullscreen mode Exit fullscreen mode
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;
}
Enter fullscreen mode Exit fullscreen mode

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 {};
}
Enter fullscreen mode Exit fullscreen mode

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};
}
Enter fullscreen mode Exit fullscreen mode

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];
    }
}
Enter fullscreen mode Exit fullscreen mode

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];
    }
Enter fullscreen mode Exit fullscreen mode

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--;
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

Binary Search

overflow case mid=low+(high-low)/2


Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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();
    }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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();
  }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
  }
  }
Enter fullscreen mode Exit fullscreen mode

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

Image description

    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();
    }
Enter fullscreen mode Exit fullscreen mode

4) Prefix to Postfix
Rules:
-> Operands are added to the stack
-> If we encounter an operator, (operand,operand,operator) to the stack

Image description

    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();
    }
Enter fullscreen mode Exit fullscreen mode

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

Image description

    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();
    }
Enter fullscreen mode Exit fullscreen mode

6) Postfix to Prefix
Rules:
-> Operands are pushed
-> If we encounter an operator, (operator,operand,operand) is pushed

Image description

    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();
    }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more