arrays

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();

        int i = 0;
        int j = n-1;

        while(i<j){
            int sum  = numbers[i] + numbers[j];

            if(sum<target){
                i++;
            }
            else if(sum>target){
                j--;
            }
            else{
                return {i+1, j+1};
            }
        }
        return {};

    }
}; //05-05-2024


class Solution {
public:
    vector<int> getLeftMax(vector<int>& height, int n) {
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for(int i = 1; i<n; i++) {
            leftMax[i] = max(leftMax[i-1], height[i]);
        }
        return leftMax;
    }
    vector<int> getRightMax(vector<int>& height, int n) {
        vector<int> rightMax(n);
        rightMax[n-1] = height[n-1];
        for(int i = n-2; i>=0; i--) {
            rightMax[i] = max(rightMax[i+1], height[i]);
        }
        return rightMax;
    } 
    int trap(vector<int>& height) {
        int n = height.size();
        if(n == 1 || n == 0)
            return 0;
        vector<int> leftMax = getLeftMax(height, n);
        vector<int> rightMax = getRightMax(height, n);
        int sum = 0;
        for(int i = 0; i<n; i++) {
            sum += min(leftMax[i], rightMax[i]) - height[i];
        }
        return sum;
    }
};  // 06-05-24


class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();

        vector<vector<string>> result;

        unordered_map<string, vector <string>> mp;

        for(int i =0; i<n; i++){
            string temp = strs[i];

            sort(begin(temp), end(temp));
            mp[temp].push_back(strs[i]);
        }
        for(auto it: mp){
            result.push_back(it.second);
        }
        return result;
    }
}; // 07-05-24


class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = m;

        for(int i = 0; i<m; i++){
            for(int j = i; j<n; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        for(int i =0; i<m; i++){
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
}; // 08-05-24


class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        
        map<int, vector<int>> mp;
        
        vector<int> result;
        
        //fill the map using [i+j]
        for(int i = 0; i<m; i++) {
            for(int j = 0; j<n; j++) {
                mp[i+j].push_back(mat[i][j]);
            }
        }
        
        bool flip = true;
        for(auto &it : mp) {
            if(flip) {
                //it.second ko reverse kardo
                reverse(it.second.begin(), it.second.end());
            }
            
            for(int &num : it.second) {
                result.push_back(num);
            }
            
            flip = !flip;
        }
        
        return result;
    }
}; // 09-05-24

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(begin(nums), end(nums));
    }
};
  

//Approach-2 (Using counting)
//T.C : O(n+n)
//S.C : O(1)
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        
        int count_0 = 0;
        int count_1 = 0;
        int count_2 = 0;
        
        for(int &num : nums) {
            if(num == 0)
                count_0++;
            else if(num == 1)
                count_1++;
            else
                count_2++;
        }
        
        for(int i = 0; i<n; i++) {
            if(count_0 > 0) {
                nums[i] = 0;
                count_0--;
            } else if(count_1 > 0) {
                nums[i] = 1;
                count_1--;
            } else if(count_2 > 0) {
                nums[i] = 2;
                count_2--;
            }
        }
    }
}; // 10-05-24

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        for(int i=1; i<m; i++){
            for(int j =1; j<n; j++){
                if(matrix[i][j] != matrix[i-1][j-1]){
                    return false;
                }
            }
        }
        return true;
    }
}; // 11-05-24

class Solution {
public:
  void setZeroes(vector<vector<int>>& mat) {
    int m=mat.size(),n=mat[0].size();
    bool r0=false,c0=false;
    for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
        if(mat[i][j]==0){
          if(i==0) r0=true;
          else mat[i][0]=0;
          if(j==0) c0=true;
          else mat[0][j]=0;
        }
      }
    }
    for(int i=1;i<m;i++){
      for(int j=1;j<n;j++){
        if(mat[i][0]==0 || mat[0][j]==0) mat[i][j]=0;
      }
    }
    if(r0){
      for(int j=0;j<n;j++) mat[0][j]=0;
    }
    if(c0){
      for(int i=0;i<m;i++) mat[i][0]=0;
    }
  }
}; // 12-05-24

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        int n = nums.size();

        sort(begin(nums), end(nums));

        for(int i = n-3; i>=0; i--){
            if( nums[i] + nums[i+1] > nums[i+2]){
                return nums[i] + nums[i+1] + nums[i+2];
            }
        }
        return 0;
    }
}; 12-05-24

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        
        int i = n-1;
        for(; i>0; i--) {
            if(nums[i] > nums[i-1]) {
                break;
            }
        }
        if(i != 0) {
            int index = i;
            for(int j = n-1; j>=i; j--) {
                if(nums[j] > nums[i-1]) {
                    index = j;
                    break;
                }
            }
            swap(nums[i-1], nums[index]);
        }
        reverse(nums.begin()+i, nums.end());
    }
}; // 13-05-24

// User function Template for C++

class Solution {
  public:
     string find(string s, map<string, string> &p)
  {
    //If the parent of the node is the node itself, we return the node.
    //Otherwise, we recursively find the parent of the parent until we reach the node whose parent is itself.
    return p[s] == s ? s : find(p[s], p);
  }
  
  //Function to merge the accounts using union-find data structure.
  vector<vector<string>> accountsMerge(vector<vector<string>> &accounts)
  {
    //Creating maps for owner, parent, and unions.
    map<string, string> owner;
    map<string, string> parents;
    map<string, set<string>> unions;
    
    //Looping through all the accounts to initialize the maps.
    for (int i = 0; i < accounts.size(); i++)
    {
      //Setting the parent of each email as the email itself.
      //Setting the owner of each email as the first email in the account.
      for (int j = 1; j < accounts[i].size(); j++)
      {
        parents[accounts[i][j]] = accounts[i][j];
        owner[accounts[i][j]] = accounts[i][0];
      }
    }
    
    //Looping through all the accounts to merge the emails.
    //Merging is done by finding the parent of each email and updating the parent of all emails in the account to the same parent.
    for (int i = 0; i < accounts.size(); i++)
    {
      string p = find(accounts[i][1], parents);
      for (int j = 2; j < accounts[i].size(); j++)
        parents[find(accounts[i][j], parents)] = p;
    }
    
    //Looping through all the accounts to group the emails by their parent.
    //We add each email to the set of emails for its parent.
    for (int i = 0; i < accounts.size(); i++)
      for (int j = 1; j < accounts[i].size(); j++)
        unions[find(accounts[i][j], parents)].insert(accounts[i][j]);

    //Creating the result vector of vectors.
    //For each group of emails (union), we convert the set of emails to a vector and insert the owner as the first element of the vector.
    vector<vector<string>> ans;
    for (pair<string, set<string>> p : unions)
    {
      vector<string> res(p.second.begin(), p.second.end());
      res.insert(res.begin(), owner[p.first]);
      ans.push_back(res);
    }
    //Returning the result vector of vectors.
    return ans;
  }
}; // 15-05-24