Array

Binary Search

public int fn(int[] arr, int target){
  int left = 0;
  int right = arr.length - 1;
  while(left <= right){
    int mid = left + (right - left) /2;
    if (arr[mid] == target){
      // do something
      return mid;
    }else if (arr[mid] < target){
      left = mid + 1;
    }else{
      right = mid + 1;
    }
  }

  // left is the insertiont point
  return left;
}

duplicate elements, left-most insertion point

public int fn(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

duplicate elements, right-most insertion point

public int fn(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

for greedy problems

If looking for a minimum:

public int fn(int[] arr) {
    int left = MINIMUM_POSSIBLE_ANSWER;
    int right = MAXIMUM_POSSIBLE_ANSWER;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

public boolean check(int x) {
    // this function is implemented depending on the problem
    return BOOLEAN;
}

If looking for a maximum:

public int fn(int[] arr) {
    int left = MINIMUM_POSSIBLE_ANSWER;
    int right = MAXIMUM_POSSIBLE_ANSWER;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return right;
}

public boolean check(int x) {
    // this function is implemented depending on the problem
    return BOOLEAN;
}

Two Pointer

one input, opposite ends

public int fn(int[] arr){
    int left = 0;
  int right = arr.length - 1;
  int result = 0;

  while (left < right){
    // do some logic here with left and right
    if (CONDITION){
      left++;
    }else {
      right--;
    }
  }

  return result;
}

two inputs, exhaust both

public int fn(int[] arr1, int[] arr2){
  int i = 0;
  int j = 0;
  int result = 0;

  while(i < arr1.length && j < arr2.length){
    // do some logic here
    if (CONDITION){
      i++;
    }else{
      j++;
    }
  }

  while(i < arr1.length){
    // do logic
    i++;
  }

  while(j < arr2.length){
    // do logic
    j++;
  }

  return result;
}

Sliding window

public int fn(int[] arr){
  int left = 0;
  int result = 0;
  int cur = 0;

  for (int right = 0; right < arr.length; right++){
    // 1. add new 
    // do logic here to add arr[right] to cur

    // 2. remove old
    while (WINDOW_CONDITION_BROKEN){
      // remove arr[left] from cur
      left++;
    }

    // 3. update result;
  }

  return result;
}

Prefix Sum

public int[] fn(int[] arr){
  int[] prefix = new int[rr.length];

  prefix[0] = arr[0];

  for (int i = 1; i < arr.length; i++){
    prefix[i] = prefix[i - 1] + arr[i];
  }

  return prefix;
}

Efficient string building

public String fn(char[] arr){
  StringBuilder sb = new StringBuilder();
  for (char c: arr){
    sb.append(c);
  }

  return sb.toString();
}