import java.util.*;

class Solution {

  public int searchTriplets(int[] arr, int target) {
    int count = 0;
    Arrays.sort(arr); //sort
    for (int i = 0; i<arr.length - 2; i++) {
      int lo = i + 1; //find pairs forward from i
      int hi = arr.length - 1;
      while (lo < hi) {
        int currSum = arr[i] + arr[lo] + arr[hi];
        if (currSum < target){
          //since sorted, all numbers from arr[lo] to arr[hi] are valid pairs 
          count = count + (hi - lo); //since decreasing hi until lo will still create sum < target
          lo++; //try new pairing from new lo to hi
        } else {
          hi--; //sum too big, we need smaller sum so decrement hi to get smaller value
        }
      } //end while loop
    }
    return count;
  }
}