Questions

💡 First try with yourself, if you are unable to solve the question then see the solution.

First negative integer in every window of size k

First negative integer in every window of size k (gfg)

vector<long long> printFirstNegativeInteger(long long int arr[], long long int N, long long int K) {

    vector<long long> ans;
    queue<int> q;
    int i = 0;  
    int j = 0;

    while(j < N){

        if(arr[j] < 0){
            q.push(arr[j]);
        }

        if(j-i+1 < K){
            j++;
        }
        else if(j-i+1 == K){

            if(q.empty()){
                ans.push_back(0);
            }
            else{
                ans.push_back(q.front());
            }

            if(arr[i] < 0){
                q.pop();
            }
            i++;
            j++;
        }
    }

    return ans;
}

Count Occurences of Anagrams

Count Occurences of Anagrams (gfg)

class Solution{
    public:
    int search(string pat, string txt) {

        map<char , int> mp;
        for(int i = 0 ; i < pat.length() ; i++){
            mp[pat[i]]++;
        }

        int count = mp.size();
        int k = pat.length();
        int ans = 0;
        int i = 0;
        int j = 0;

        while(j < txt.length()){

            if(mp.find(txt[j]) != mp.end()){
                mp[txt[j]]--;
                if(mp[txt[j]] == 0){
                    count--;
                }
            }
            if(j-i+1 < k){
                j++;
            }
            else if(j-i+1 == k){
                if(count == 0){
                    ans++;
                }
                if(mp.find(txt[i]) != mp.end()){
                    mp[txt[i]]++;
                    if(mp[txt[i]] == 1){
                        count++;
                    }
                }
                i++;
                j++;
            }
        }
        return ans;
    }

};

Maximum of all subarrays of size k

Maximum of all subarrays of size k (gfg)

class Solution{
    public:
    vector<int> max_of_subarrays(vector<int> arr, int n, int k) {

        vector<int> ans;
        int maxi = INT_MIN;
        int i = 0;
        int j = 0;
        while(j < n){

            if(arr[j] > maxi){
                maxi = arr[j];
            }

            if(j-i+1 < k){
                j++;
            }
            else if(j-i+1 == k){
                ans.push_back(maxi);
                if(arr[i] != maxi){
                    i++;
                    j++;
                }
                else if(arr[i] == maxi){
                    i++;
                    j = i;
                    maxi = 0;
                }

            }
        }
        return ans;
    }
};

Number of subarray whose sum equals to K

Subarray Sum Equals K (leetcode)

class Solution {
    public:
    int subarraySum(vector<int>& nums, int k) {

        int count = 0;
        int sum = 0;
        map<int,int> mp;

        for(int i = 0 ; i < nums.size() ; i++){
            sum += nums[i];

            if(sum == k){
                count++;
            }

            if(mp.find(sum-k) != mp.end()){
                count += mp[sum-k];
            }

            mp[sum]++;

        }

        return count;

    }
};

Number of Substrings Containing All Three Characters

Number of Substrings Containing All Three Characters (leetcode)

BruteForce

class Solution {
    public:
    int numberOfSubstrings(string s) {

        int n = s.length();
        int count = 0;
        for(int i = 0; i < n ; i++){
            vector<int> hash(3,0);
            for(int j = i ; j < n ; j++){
                hash[s[j]-'a'] = 1;
                if(hash[0]+hash[1]+hash[2] == 3){
                    count += n-j;
                    break;
                }
            }
        }
        return count;
    }
};

Optimal

class Solution {
    public:
    int numberOfSubstrings(string s) {

        vector<int> last_seen(3,-1);
        int ans = 0;
        int j = 0;

        while(j < s.length()){

            last_seen[s[j]-'a'] = j;
            if(last_seen[0] != -1 && last_seen[1] != -1 && last_seen[2] != -1){
                int mini = min(last_seen[0],min(last_seen[1],last_seen[2]));
                ans += mini+1;
            }
            j++;
        }
        return ans;
    }
};

🥇 🥇 🥇

Questions

Other Important Questions List