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;
}Category: Competitive Programming
GFG PTOD | 12 Jan 2025 | Trapping Rain Water
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;
}GFG PTOD | 11 Jan 2025 | Longest substring with distinct characters
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;
}GFG PTOD | 10 Jan 2025 | Count distinct elements in every window
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;
}GFG PTOD | 09 Jan 2025 | Indexes of Subarray Sum
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};
}GFG PTOD | 08 Jan 2025 | Count the number of possible triangles
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;
}GFG PTOD | 07 Jan 2025 | Pair with given sum in a sorted array
int countPairs(vector<int> &arr, int target) {
// Complete the function
int count = 0, i=0, j=arr.size()-1;
while(i<j) {
int sum = arr[i] + arr[j];
if(sum < target) i++;
else if(sum > target) j--;
else {
int el1 = arr[i], el2=arr[j];
int ci = 0, cj=0;
while(arr[i] == el1 && i<=j) ci++, i++;
while(arr[j] == el2 && i<=j) cj++, j--;
if(el1 == el2) count += ci*(ci-1)/2;
else count += ci*cj;
}
}
return count;
}GFG PTOD | 06 Jan 2025 | Sum Pair closest to target
vector<int> sumClosest(vector<int>& arr, int target) {
// code here
sort(arr.begin(), arr.end());
int diff = INT_MAX, i=0, j=arr.size()-1;
vector<int> res;
while(i<j) {
int sum = arr[i] + arr[j];
if(abs(sum-target) < diff) {
diff = abs(sum-target);
res={arr[i], arr[j]};
}
if(sum < target) i++;
else j--;
}
return res;
}GFG PTOD | 05 Jan 2025 | Count Pairs whose sum is less than target
int countPairs(vector<int> &arr, int target) {
// Your code here
sort(arr.begin(), arr.end());
int count=0, l=0, r=arr.size()-1;
while(l<r) {
int sum = arr[l]+arr[r];
if(sum < target) {
count += r-l;
l++;
} else {
r--;
}
}
return count;
}GFG PTOD | 04 Jan 2025 | Count all triplets with given sum in sorted array
int countTriplets(vector<int> &arr, int target) {
// Code Here
int count = 0;
int n = arr.size();
for(int i=0; i<n-2; i++) {
int j = i+1, k=n-1;
while(j<k) {
int sum = arr[i] + arr[j] + arr[k];
if(sum < target) j++;
else if(sum > target) k--;
else if(sum == target) {
count++;
int temp = j+1;
while(arr[temp] == arr[temp-1] && temp<k) {
count++;
temp++;
}
k--;
}
}
}
return count;
}