Coding From Basic To Adv 

Basic:

ArrayBased:

Given an unsorted integer array, find a pair with the given sum in it.

package org.niteshsynergy.arrayBased;

import java.util.*;
import java.util.stream.IntStream;
public class Main {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       List<Integer> arrayList = new ArrayList<Integer>();
       System.out.println("Enter array elements:");
       int N = sc.nextInt();
       System.out.println("Enter numbers separated by space");
       for (int i = 0; i < N; i++) {
           arrayList.add(sc.nextInt());
       }
       System.out.println("Enter Target Values");
       int target = sc.nextInt();
       System.out.println("Your Result For  Code01PairWithSumArray.solution1()");
       Code01PairWithSumArray.solution1(arrayList, target);
       System.out.println("Your Result For  Code01PairWithSumArray.solution2()");
       Code01PairWithSumArray.solution2(arrayList, target);
       System.out.println("Your Result For  Code01PairWithSumArray.solution3()");
       Code01PairWithSumArray.solution3(arrayList, target);
       System.out.println("Your Result For  Code01PairWithSumArray.solution4()");

   }

}
class Code01PairWithSumArray{
   public static void solution1(List<Integer> arrayList,int target) {
       /*
       Brute Force Approach
       Description: Iterate through all possible pairs in the array and check if the sum of any pair equals the target.
       Time Complexity: O(n)
       Space Complexity:O(1)
       */
      for (int i = 0; i < arrayList.size()-1; i++) {
          for (int j = i + 1; j < arrayList.size(); j++) {
              int sum = arrayList.get(i) + arrayList.get(j);
              if (sum == target) {
                  System.out.println("Elements Found:"+arrayList.get(i) + " & " + arrayList.get(j));
                  break;
              }
          }
      }
   }
  /*
    Using Hashing (HashSet for Complements)
    Description: Use a HashSet to store numbers as you iterate through the array. For each number, check if its complement (target - number) exists in the set.
    Time Complexity: O(n)
    Space Complexity:O(n)
   */
   public static void solution2(List<Integer> arrayList,int target) {
       HashSet<Integer> set = new HashSet<Integer>();
       for(int num : arrayList) {
           int complement = target - num;
           if(set.contains(complement)) {
               System.out.println("Elements Found:"+arrayList.get(num));
           }
           set.add(num);
       }
   }
   /*
    Using Two Pointers Approach (After Sorting)
    Description: Sort the array and use two pointers (one starting at the beginning and the other at the end).
                 Adjust pointers based on whether their sum is less than, equal to, or greater than the target.
    Time Complexity: O(nlog)-> for sorting +O(n)-> for Two Pointers Approach
    Space Complexity:O(1)
   */
   public static void solution3(List<Integer> arrayList,int target) {
       Collections.sort(arrayList);
       int left = 0, right = arrayList.size()-1;
       while(left < right) {
           int sum= arrayList.get(left) + arrayList.get(right);
           if(sum == target) {
               System.out.println("Elements Found:"+arrayList.get(left));
               left++;
               right--;
           }
           else if(sum < target)
               left++;
           else
               right--;
       }
   }
   /*
    Using a Map to Track Indices
    Description: Use a HashMap to store the indices of elements as you traverse the array. For each element, check if its complement exists in the map.
      Time Complexity:O(n), (single traversal).
      Space Complexity:O(n),  (extra space for the map).
    */
   public static void solution4(List<Integer> arrayList,int target) {
       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       for(int i = 0; i < arrayList.size(); i++) {
           int complement = target - arrayList.get(i);
           if(map.containsKey(complement)) {
               System.out.println("Elements Found:(" + arrayList.get(i) + ", " + complement + ")");
           }
           map.put(arrayList.get(i), i);
       }
   }
   /*
    Generate All Pairs Using Streams (Functional Approach)
    Description: Use Java Streams to generate all pairs of indices, filter them based on the target sum, and collect the results.
    Time Complexity: O(n^2)
    Space Complexity: : Depends on the number of pairs stored in the result.
    */
   public static void solution5(List<Integer> arrayList,int target) {
       IntStream
               .range(0, arrayList.size())
               .boxed()
               .flatMap(
                       i-> IntStream.range(i+1,arrayList.size())
                       .filter(j-> arrayList.get(i)+arrayList.get(j)==target)
                       .mapToObj(j -> "(" + arrayList.get(i)+ ", " + arrayList.get(j) + ")")
               )
               .forEach(System.out::println);
   }
   /*
   Sliding Window (For Sorted Array or Specific Ranges)
Description: This approach is useful when the array is sorted or when you know the range of numbers you're working with.
It uses a sliding window to find pairs in the sorted array. The window shifts over the array while keeping track of the current sum.
    Time Complexity: O(n)
    Space Complexity: :O(1)
    */
   public static void solution6(List<Integer> arrayList,int target) {
       Collections.sort(arrayList);
       int left = 0, right = arrayList.size()-1;
       while (left < right) {
           int sum = arrayList.get(left) + arrayList.get(right);
           if (sum == target) {
               System.out.println("Pair found: (" + arrayList.get(left) + ", " + arrayList.get(right) + ")");
               left++;
               right--;
           } else if (sum < target) {
               left++;
           } else {
               right--;
           }
       }
   }
   /*
   Using Priority Queue (Min-Heap or Max-Heap)
   Description: Use a priority queue (min-heap or max-heap) to store elements in a specific order.
   This approach can be useful when you need to keep track of the smallest or largest elements efficiently while finding pairs.
 Time Complexity: O(nlogn),(due to the heap operations)
    Space Complexity: :O(n), (for storing elements in the heap).
    */
   public static void solution7(List<Integer> arrayList,int target) {
       PriorityQueue<Integer> minHeap = new PriorityQueue<>();
       for(int num : arrayList) {
           minHeap.offer(num);
       }
       while (!minHeap.isEmpty()) {
           int num = minHeap.poll();
           int complement = target - num;
           if(minHeap.contains(complement)) {
               System.out.println("Pair found: (" + num + ", " + complement + ")");
           }
       }
   }
       /*
  Using a Custom Comparator for Sorting with Pair Lookup
   Description: In this approach, we can implement a custom comparator to sort the array in a way that can help optimize the search for pairs.
   This method involves sorting and using binary search techniques or customized sorting for better performance.
 Time Complexity: O(nlogn),(due to sorting and binary search).
    Space Complexity: :O(n), (for storing sorted array).
    */
/*    public static void solution8(List<Integer> arrayList,int target) {
       Integer[] numsArr = Arrays.stream(arrayList).boxed().toArray(Integer[]::new);
       // Custom Comparator: sort by values (ascending)
       Arrays.sort(numsArr, Comparator.naturalOrder());
       int left = 0, right = numsArr.length - 1;
       while (left < right) {
           int sum = numsArr[left] + numsArr[right];
           if (sum == target) {
               System.out.println("Pair found: (" + numsArr[left] + ", " + numsArr[right] + ")");
               left++;
               right--;
           } else if (sum < target) {
               left++;
           } else {
               right--;
           }
       }
   }*/
}
/*
Given an unsorted integer array, find a pair with the given sum in it.
• Each input can have multiple solutions. The output should match with either one of them.
Input : nums[] = [8, 7, 2, 5, 3, 1], target = 10
Output: (8, 2) or (7, 3)
• The solution can return pair in any order. If no pair with the given sum exists, the solution should return null.
Input : nums[] = [5, 2, 6, 8, 1, 9], target = 12
Output: null
*/