// Sliding window

class MaxSumSubArrayOfSizeK {
 public:
  static int findMaxSumSubArray(int k, const vector<int>& arr) {
    int maxSum = 0, sum = 0;
    if (arr.size() < k) {
      return maxSum;
    }
    for (int i = 0; i < arr.size(); i++) {
      if (i < k) {
        sum += arr[i];
        maxSum += arr[i];
      } else {
        sum = sum + arr[i] - arr[i - k];
        maxSum = max(maxSum, sum);
      }
    }
    return maxSum;
  }


// Pair with target sum
class PairWithTargetSum {
 public:
  static pair<int, int> search(const vector<int>& arr, int targetSum) {
    int left = 0, right = arr.size() - 1;
    pair<int, int> result = make_pair(-1, -1);
    while (left < right) {
      if (arr[left] + arr[right] == targetSum) {
        result.first = left;
        result.second = right;
        break;
      } else if (arr[left] + arr[right] < targetSum) {
        left++;
      } else {
        right--;
      }
    }
    // TODO: Write your code here
    return result;
  }
};

// Remove duplicates
class RemoveDuplicates {
 public:
 //[2,3,3,3,6,9,9]
 //[2, 3, 3, 3, 6, 9, 9]
 //[2, 3, 6, 9, 3, 3, 9]
  static int remove(vector<int>& arr) {
    int nDI = 1;
    for (int i = 1; i < arr.size(); i++) {
      if (arr[nDI - 1] != arr[i]) {
        arr[nDI] = arr[i];
        nDI++;
      }
    }
    // TODO: Write your code here
    return nDI;
  }
};

// squares of a sorted array
 public:
  static vector<int> makeSquares(const vector<int>& arr) {
    int n = arr.size();
    vector<int> squares(n);
    int left = 0, right = n - 1;
    while (left <= right) {
      int ls = arr[left] * arr[left];
      int rs = arr[right] * arr[right];

      if (ls > rs) {
        squares[right - left] = ls;
        left++; 
      } else {
        squares[right - left] = rs;
        right--;
      }

    }
    return squares;
  }

// Triplet Sum to zero
using namespace std;

#include <algorithm>
#include <iostream>
#include <vector>

class TripletSumToZero {
 public:
  static vector<vector<int>> searchTriplets(vector<int> &arr) {
    vector<vector<int>> triplets;
    sort(arr.begin(), arr.end());
    if (arr.size() < 3) {
      return triplets;
    }
    for (int i = 0; i < arr.size(); i++) {
      if (arr[i] > 0) { // Found negative number, bail out
        return triplets;
      }
      if (i > 0 && arr[i-1] == arr[i]) { // skip duplicates
        continue;
      }
      searchPair(arr, -arr[i], i + 1, triplets);
    }
    return triplets;
  }

 private:
  static void searchPair(vector<int> &arr, int targetSum, int idx, vector<vector<int>> &triplets)
  {
    int left = idx, right = arr.size() - 1;

    while (left < right) {
      while (left < right && arr[left - 1] == arr[left]) { //skip duplicates
        left++;
      }
      while (left < right && arr[right + 1] == arr[right]) { //skip duplicates
        right--;
      }

      if (arr[left] + arr[right] == targetSum) {
        triplets.push_back({-targetSum, arr[left], arr[right]});
        left++;
        right--;
      } else if (arr[left] + arr[right] < targetSum) {
        left++;
      } else {
        right--;
      }
    }
  }
};
  
// Dutch national Flag probem
class DutchFlag {
 public:
  static void sort(vector<int> &arr) {
    int left = 0, right = arr.size() - 1;
    for (int i = 0; i <= right; ) {
      if (arr[i] == 0) {
        swap(arr, i, left);
        i++;
        left++;
      } else if (arr[i] == 1) {
        i++;
      } else {
        swap(arr, i, right);
        right--;
      }
    }
  }