Category: Competitive Programming

vector<int> productExceptSelf(vector<int>& arr) {
        // code here
        vector<int> res(arr.size(), 0);
        int totalProduct = 1;
        int zero = 0, index=-1;
        for(int i=0; i<arr.size(); i++)
        {
            if(arr[i] == 0) zero++, index = i;
            else totalProduct *= arr[i];
        }
        if(zero == 0) {
            for(int i=0; i<arr.size(); i++) {
                res[i] = totalProduct / arr[i];
            }
        } else if(zero == 1) {
            res[index] = totalProduct;
        }
        
        return res;
    }

int maxLen(vector<int> &arr) {
        // Your code here
        int res=0, sum=0;
        unordered_map<int, int> mp;
        
        for(int i=0; i<arr.size(); i++) {
            sum += (arr[i] == 0) ? -1 : 1;
            if(sum == 0) res = max(res, i+1);
            else if(mp.find(sum) != mp.end()) res = max(res, i-mp[sum]);
            else mp[sum] = i;
        }
        
        return res;
    }

int longestSubarray(vector<int>& arr, int k) {
        // code here
        int presum = 0, res=0;
        unordered_map<int, int> mp;
        for(int i=0; i<arr.size(); i++) {
            presum += arr[i];
            if(presum == k)
                res = max(res, i+1);
            else if(mp.find(presum-k) != mp.end())
                res = max(res, i-mp[presum-k]);
            
            if(mp.find(presum) == mp.end())
                mp[presum] = i;
        }
        return res;
    }

int maxWater(vector<int> &arr) {
        // code here
        int i=0, j=arr.size()-1,res=0;
        while(i<j) {
            int water = min(arr[i], arr[j]) * (j-i);
            res = max(res, water);
            if(arr[i] < arr[j]) i++;
            else j--;
        }
        return res;
    }

int maxWater(vector<int> &arr) {
        // code here
        int i=0, j=arr.size()-1, lmax=0, rmax=0, ret=0;
        while(i<j) {
            if(arr[i] <= arr[j]) {
                if(lmax < arr[i]) lmax = arr[i];
                else ret += lmax - arr[i];
                i++;
            } else {
                if(rmax < arr[j]) rmax = arr[j];
                else ret += rmax - arr[j];
                j--;
            }
        }
        return ret;
    }

int longestUniqueSubstr(string &s) {
        // code here
        int i=0, j=0, maxCount=0;
        vector<int> freq(26);
        
        /*while(j<s.size()) {
            while(freq[s[j]-'a'] > 0) {
                freq[s[i]-'a']=0;
                i++;
            }
            freq[s[j]-'a']++;
            maxCount = max(maxCount, j-i+1);
            j++;
        }*/
        
        while(j<s.size()) {
            if(freq[s[j]-'a'] > 0) {
                while(i<j && s[i]!=s[j]) {
                    freq[s[i]-'a']=0;
                    i++;
                }
                i++;
            }
            freq[s[j]-'a']++;
            maxCount = max(maxCount, j-i+1);
            j++;
        }
        return maxCount;
    }

vector<int> countDistinct(vector<int> &arr, int k) {
        // code here.
        vector<int> res;
        unordered_map<int, int> map;
        for(int i = 0; i<k; i++)
            map[arr[i]]++;
        res.push_back(map.size());
        
        for(int i = k; i<arr.size(); i++) {
            map[arr[i]]++;
            map[arr[i-k]]--;
            
            if(map[arr[i-k]] == 0)
                map.erase(arr[i-k]);
            res.push_back(map.size());
        }
        return res;
    }

vector<int> subarraySum(vector<int> &arr, int target) {
        // code here
        int st = 0, end = 0, sum=0;
        for(int i=0; i<arr.size(); i++) {
            sum += arr[i];
            if(sum >= target) end = i;
            while(st<end && sum>target) {
                sum -= arr[st];
                st++;
            }
            if(sum == target) {
                return {st+1, end+1};
            }
        }
        return {-1};
    }

int countTriangles(vector<int>& arr) {
        // code here
        int count = 0;
        sort(arr.begin(), arr.end());
        for(int i=2; i<arr.size(); i++) {
            int j=0, k=i-1;
            while(j<k) {
                if(arr[j]+arr[k] > arr[i]) {
                    count += k-j;
                    k--;
                } else {
                    j++;
                }
            }
        }
        return count;
    }