DAY 3 #coding challenge

Problem Statement (Water the plants : Medium)

A gallery with plants is divided into n parts, numbered 0, 1, 2, 3, ..., n-1. There are provisions for attaching water sprinklers in every division. A sprinkler with range x at division i can water all divisions from i-x to i+x.

Given an array gallery[] consisting of n integers, where gallery[i] is the range of the sprinkler at partition i (a power of -1 indicates no sprinkler attached), return the minimum number of sprinklers that need to be turned on to water the entire gallery. If there is no possible way to water the full length using the given sprinklers, print -1.

Input:
n = 6
gallery[] = {-1, 2, 2, -1, 0, 0}
Output:
2
Explanation: 
Sprinklers at index 2 and 5
can water the full gallery, span of
sprinkler at index 2 = [0,4] and span
of sprinkler at index 5 = [5,5].

here the sprinklers has to cover all the parts and we need to output minimum sprinklers to be started to cover all parts.
I took a vector which stored pair of integers where left integer is the min and right is the max range. After getting the ranges we arrange that in ascending order, then run a while loop from 0 to n , inside which we find the most range covered and keep on counting sprinklers.

int min_sprinklers(int gallery[], int n){
        vector<pair<int, int>> arr;
        for(int i = 0; i < n; i++) {
            if(gallery[i] == -1) continue;
            arr.push_back({max(0, i - gallery[i]), min(n-1, i + gallery[i])});
        }
        sort(arr.begin(), arr.end()); 
        int i = 0, cnt = 0, j = 0, sz = arr.size();
        while(i < n){
            if(arr[j].first > i) return -1;
            int prev_i = i;
            while(j < sz and arr[j].first <= prev_i) i = max(i, arr[j].second + 1), j++;
            cnt++;
        }
        return cnt;
    }

Problem Statement : (Smallest distinct window : medium)(sliding window)

Given a string 's'. The task is to find the smallest window length that contains all the characters of the given string at least one time.
For eg. A = aabcbcdbca, then the result would be 4 as of the smallest window will be dbca.

Input : "AABBBCBBAC"
Output : 3
Explanation : Sub-string -> "BAC"

In this problem we take unique elements first by using set then take the size of set, take map where with the while loop we add the element when map size is equal to set size save the size of substring then start reducing the substring.

int findSubString(string str)
    {
        // Your code goes here 
        set <char> st; 
        for (auto i:str) st.insert(i);
        int size = st.size();
        int i=0,j=0;
        int n = str.size();

        int ans = INT_MAX;
        unordered_map< char,int> mp;
        while( j<n )
        {
            mp[str[j]]++;
            if( mp.size() == size)
            {
                while( mp.size() == size and i<n) {
                ans = min ( ans, j-i+1);
                mp[ str[i] ]--;
                if( mp[ str[i] ] == 0)
                {
                    auto e = mp.find(str[i]);
                    mp.erase(e);
                }
                i++;
                }
            }
            j++;
        }
        return ans;
    }

Problem Statement (Game with String : easy)(priority queue)

Given a string s of lowercase alphabets and a number k, the task is to print the minimum value of the string after removal of k characters. The value of a string is defined as the sum of squares of the count of each distinct character.

Input: s = abccc, k = 1
Output: 6
Explaination:
We remove c to get the value is 1sq + 1sq + 2sq

here we need get the frequency of each character and add it in priority queue then start reducing the frequency of top element then again add the element to priority queue, like this after removing k elements we have to square the frequency to get the answer.

int minValue(string s, int k){
        map<char,int> mp;
        for(int i=0;i<s.length();i++){
            mp[s[i]]++;
        }
        priority_queue<int> pq;
        for(auto it=mp.begin();it!=mp.end();it++){
            pq.push((*it).second);
        }

        while(k--){
            int maxVal = pq.top();
            pq.pop();
            maxVal-=1;
            pq.push(maxVal);
        }

        int res=0;
        while(pq.empty()==false){
            res += pow(pq.top(),2);
            pq.pop();
        }
        return res;
    }

Today I played football as the outdoor activity.