TwoPointer.java

import java.util.*;

// When and where to use two pointer approach?
// 1. When we have to find a pair in an array which satisfies a condition.
// 2. When we have to find a triplet in an array which satisfies a condition.
// 3. When we have to find a subarray in an array which satisfies a condition.
// 4. When we have to find a subsequence in an array which satisfies a condition.
// 5. When we have to find a substring in a string which satisfies a condition.
// 6. When we have to find a subsequence in a string which satisfies a condition.
// 7. When we have to find a subarray in an array which satisfies a condition and the array is sorted.
// 8. When we have to find a subsequence in an array which satisfies a condition
// 9. When we have to find a substring in a string which satisfies a condition and the string is sorted.
// 10. When we have to find a subsequence in a string which satisfies a condition and the string is sorted. 

public class TwoPointer{
    public static int[] TwoSum(int[] arr,int target){
        
        Arrays.sort(arr); // sort allowed because we want to return the actual nums not indexes

        int i = 0;
        int j = arr.length - 1;

        while(i < j){ // (i < j) not (i <= j)
            int sum = arr[i] + arr[j];
            if(sum == target){
                return new int[]{arr[i], arr[j]};
            }
            else if(sum < target){
                i++;
            }
            else{ // sum > target
                j--;
            }
        }

        return new int[]{-1, -1};
    }

    public static int removeDuplicates(int[] arr){
       int i = 1; // coz 0th position will always be unique element
       int j = 1;

       while(j != arr.length){
            if(arr[j-1] != arr[j]){
                arr[i] = arr[j];
                i++;
                j++;
            }else{
                j++;
            }
       }  
       return i; // returning unique people
    }

    public void mergeTwoSortedArrays(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; //last element's index in num1
        int j = n - 1; //last element's index in num2
        int k = m + n - 1; // last index in num1 (i.e of extra 0's not the elements)

        while(j >= 0){
            if(i >= 0 && nums1[i] > nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }   
    
    }

    public int[] sortedSquares(int[] nums) {

        int i = 0; // points to first element of given array
        int j = nums.length - 1; // points to last element of given array
        int[] ans = new int[nums.length]; // initialize an array for answer
        int k = ans.length - 1; // points to last element of answer array

        while(i<=j){
            if(Math.abs(nums[i]) >= Math.abs(nums[j])){
                ans[k] = nums[i] * nums[i];
                k--;
                i++;
                // can be written as ans[k--] = nums[i] * nums[i++]
            }else{
                ans[k] = nums[j] * nums[j];
                k--;
                j--;
                // can be wriiten as ans[k--] = nums[j] * nums[j--]
            }
        }

        return ans;

    }

    public static List<List<Integer>> threeSum(int[] nums) {

        if (nums.length < 3) {
            return new ArrayList<>();
        }

        List<List<Integer>> ans = new ArrayList<>();

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {

            // skip duplicate first element
            if (i > 0 && nums[i - 1] == nums[i])
                continue;

            int x = i + 1;
            int y = nums.length - 1;

            while (x < y) {

                if (nums[x] + nums[y] == -nums[i]) {

                    ans.add(Arrays.asList(nums[i], nums[x], nums[y]));

                    x++;
                    y--;

                    // skip duplicates for x
                    while (x < y && nums[x - 1] == nums[x]) {
                        x++;
                    }

                    // skip duplicates for y
                    while (x < y && nums[y] == nums[y + 1]) {
                        y--;
                    }

                } 
                else if (nums[x] + nums[y] < -nums[i]) {
                    x++;
                } 
                else {
                    y--;
                }
            }
        }

        return ans;
    }

    public static int threeSumClosest(int[] nums, int target) {

        if (nums.length < 3)
            return -1;

        Arrays.sort(nums);

        int min_diff = Integer.MAX_VALUE;
        int closestSum = 0;

        for (int i = 0; i < nums.length - 2; i++) {

            int x = i + 1;
            int y = nums.length - 1;

            while (x < y) {

                int sum = nums[i] + nums[x] + nums[y];

                if (sum == target) {
                    return sum;
                }

                int diff = Math.abs(target - sum);

                if (diff < min_diff) {
                    min_diff = diff;
                    closestSum = sum;
                }

                if (sum > target) {
                    y--;
                } else {
                    x++;
                }
            }
        }

        return closestSum;
    }

   //https://www.geeksforgeeks.org/problems/count-triplets-with-sum-smaller-than-x5549/1
    public static int countTriplets(int sum, int arr[]) {
        Arrays.sort(arr);
        // code here
        int value = 0;
        int count = 0;
        for(int i = 0;i < arr.length-2;i++){
            int x = i+1;
            int y = arr.length - 1;
            while(x<y){
                value = arr[i] + arr[x] + arr[y];
                if(value < sum){
                    count += (y - x);
                    x++;
                }else if(value >= sum ){
                    y--;
                }
            }
        }
        return count;    
    }

    public static void main(String[] args){
        int[] arr1 = {12,7,2,15};
        //int target = 19;
        //System.out.println(Arrays.toString(TwoSum(arr1, target)));

        int[] arr2 = {1,1,2,2,2,3,3};
        //System.out.println(removeDuplicates(arr2));

        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        int m = 3;
        int n = 3;  
        TwoPointer obj1 = new TwoPointer();
        obj1.mergeTwoSortedArrays(nums1,m,nums2,n);

        //System.out.println(Arrays.toString(nums1));

        int[] nums = {-4,-1,0,3,10};
        //System.out.println(Arrays.toString(obj1.sortedSquares(nums)));

        int[] num = {-1, 0, 1, 2, -1, -4};

        //System.out.println(threeSum(num));

        int[] num2 = {-1, 2, 1, -4};
        //int target = 1;

        //System.out.println(threeSumClosest(num2, target));
        
        int[] num3 = {0,3,-2,1};
        int sum = 2;

        //System.out.println(countTriplets(sum, num3));
    
    }
}