package Others;

import java.util.Arrays;

/**
 * The two pointer technique is a useful tool to utilize when searching for pairs in a sorted array.
 *
 * <p>link: https://www.geeksforgeeks.org/two-pointers-technique/
 */
class TwoPointers {

  public static void main(String[] args) {
    int[] arr = {10, 20, 35, 50, 75, 80};
    int key = 70;
    assert isPairedSum(arr, key); /* 20 + 60 == 70 */

    arr = new int[] {1, 2, 3, 4, 5, 6, 7};
    key = 13;
    assert isPairedSum(arr, key); /* 6 + 7 == 13 */

    key = 14;
    assert !isPairedSum(arr, key);
  }

  /**
   * Given a sorted array arr (sorted in ascending order). Find if there exists any pair of elements
   * such that their sum is equal to key.
   *
   * @param arr the array contains elements
   * @param key the number to search
   * @return {@code true} if there exists a pair of elements, {@code false} otherwise.
   */
  private static boolean isPairedSum(int[] arr, int key) {
    /* array sorting is necessary for this algorithm to function correctly */
    Arrays.sort(arr);
    int i = 0; /* index of first element */
    int j = arr.length - 1; /* index of last element */

    while (i < j) {
      if (arr[i] + arr[j] == key) {
        return true;
      } else if (arr[i] + arr[j] < key) {
        i++;
      } else {
        j--;
      }
    }
    return false;
  }
}