sourabh2k15

class Solution {
public:
    int firstUniqChar(string s) {
        if(s.length() == 0) return -1;
        
        vector<int> frequency(26, -1);
        
        for(int i = 0; i < s.length(); i++){
            if(frequency[s[i] - 'a'] == -1) frequency[s[i] - 'a'] = i;
            else{

sourabh2k15

// recursive version , computes many subproblems again and again 
int lcsRecursive(string& s1, string& s2, int i, int j){
    if(i >= s1.length() || j >= s2.length()) return 0;
 
    if(s1[i] == s2[j]) return 1 + lcsRecursive(s1, s2, i+1, j+1);
    else{
        return max(lcsRecursive(s1, s2, i+1, j), lcsRecursive(s1, s2, i, j+1));
    }
}

sourabh2k15

bool isSubsequence(string& s1, string& s2){
    int l1 = s1.length(), l2 = s2.length();
    
    for(int i = 0, j = 0; i < l1; i++){
        if(s1[i] == s2[j] && ++j == l2) return true;
    }
    
    return s2.empty();
}

sourabh2k15

class Solution {
public:
    // DFS magic : initialize stack and do the following 
    // pop top, retrieve neighbours for top, push unvisited neighbours to stack | repeat while stack not empty 
    // because this is a tree no need to keep track of visited as no cycles possible. 
    
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> result;
        

sourabh2k15

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0; // number of groups 
      
        // iterating through given grid to find a '1'
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == '1'){
                    ans++; // start a group and visit all members of this group using dfs

sourabh2k15

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<bool> visited(n, false);
        vector<vector<int>> adjList(n, vector<int>(0));
        stack<int> dfs;
        
        int count = 0;
        int ans = 0;
        

sourabh2k15

void levelOrder(TreeNode* root) {
    queue<TreeNode*> bfs;
    bfs.push(root);
        
    while(!bfs.empty()){
        TreeNode* current = bfs.front(); bfs.pop();
            
        if(current){
            cout << current->val << " ";
                

sourabh2k15

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result; // array of arrays to store final result 
        vector<int> levelresult;    // array storing result for each level temporarily
        
        queue<TreeNode*> bfs;       // bfs queue
        TreeNode* marker = new TreeNode(INT_MIN);  // dummy node to mark end of level
        
        bfs.push(root);

sourabh2k15

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> even;
        queue<TreeNode*> odd;
        vector<vector<int>> result;
        
        even.push(root);
        
        while(!even.empty() || !odd.empty()){

sourabh2k15

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        queue<vector<int>> bfs;
        int dist = 0;
        int m = matrix.size(), n = matrix[0].size();
        
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[i].size(); j++){
                if(matrix[i][j] == 0) bfs.push(vector<int>({i, j}));    // keep track of all 0's