Month: December 2024

// Function to return length of longest subsequence of consecutive integers.
    int longestConsecutive(vector<int>& arr) {
        // Your code here
        set<int> s(arr.begin(), arr.end());
        int res = 0;
        
        for(int i=0; i<arr.size(); i++) {
            if(s.find(arr[i]) != s.end() && s.find(arr[i]-1) == s.end()) {
                int count = 0, cur = arr[i];
                while(s.find(cur) != s.end()) {
                    count++;
                    s.erase(cur);
                    cur++;
                }
                res = max(count, res);
            }
        }
        return res;
    }

int findUnion(vector<int>& a, vector<int>& b) {
        // code here
        unordered_set<int> s(a.begin(), a.end());
        for(int i=0; i<b.size(); i++) {
            s.insert(b[i]);
        }
        return s.size();
    }

vector<vector<int>> findTriplets(vector<int> &arr) {
        // Code here
        // Set to handle duplicates
    set<vector<int>> resSet;
    int n = arr.size();
    unordered_map<int, vector<pair<int, int>>> mp;

    // Store sum of all the pairs with their indices
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            mp[arr[i] + arr[j]].push_back({i, j});
    }

      for (int i = 0; i < n; i++) {

        // Find remaining value to get zero sum
        int rem = -arr[i];
        if (mp.find(rem) != mp.end()) {
            vector<pair<int, int>> pairs = mp[rem];
            for (auto p : pairs) {
              
                  // Ensure no two indices are same in triplet
                if (p.first != i && p.second != i) {
                    vector<int> curr = {i, p.first, p.second};
                    sort(curr.begin(), curr.end());
                    resSet.insert(curr);
                }
            }
        }
    }

    vector<vector<int>> res(resSet.begin(), resSet.end());
    return res;
    }

 bool twoSum(vector<int>& arr, int target) {
        // code here
        std::set<int> s;
        for(int i=0; i<arr.size(); i++) {
            if(s.find(arr[i]) != s.end()) {
                return true;
            } else {
                s.insert(target-arr[i]);
            }
        }
        return false;
    }

void setMatrixZeroes(vector<vector<int>> &mat) {
        // code here
        int row = mat.size(), col = mat[0].size();
        bool isFirstRow = false, isFirstCol = false;
        
        // check 0th row and 0th col, if value is 0
        for(int j=0; j<col; j++) {
            if(mat[0][j] == 0)
                isFirstRow = true;
        }
        for(int i=0; i<row; i++) {
            if(mat[i][0] == 0)
                isFirstCol = true;
        }
        
        // mark from 1st row and 1st col to nth row and mth col
        for(int i=1; i<row; i++) {
            for(int j=1; j<col; j++) {
                if(mat[i][j] == 0) {
                    mat[i][0] = 0;
                    mat[0][j] = 0;
                }
            }
        }
        
        // fill 0 from 1st row and 1st col to nth row and mth col
        for(int i=1; i<row; i++) {
            for(int j=1; j<col; j++) {
                if(mat[i][0] == 0 || mat[0][j] == 0)
                    mat[i][j] = 0;
            }
        }
        
        //fill the first row and first col to 0
        if(isFirstRow) {
            for(int j=0; j<col; j++)
                mat[0][j] = 0;
        }
        if(isFirstCol) {
            for(int i=0; i<row; i++)
                mat[i][0] = 0;
        }
    }

// Function to search a given number in row-column sorted matrix.
    bool searchMatrix(vector<vector<int>> &mat, int x) {
        // your code here
        int i = 0, j=mat[0].size()-1;
        while(i<mat.size() && j>=0) {
            if(mat[i][j] == x) return true;
            
            if(mat[i][j] > x) j--;
            else i++;
        }
        return false;
    }