Merge 2 Sorted Array | A15.java

A15.java

// Problem Link: https://www.naukri.com/code360/problems/sorted-array_6613259

// Brute Force Approch

// Thought Process
// First, I'm collecting both the array elements into one new array which costs me O(n+m) time complexity and O(n+m)
// space complexity.
// Next, I'm sorting the array in-place which cost me arround O(klogk) where k = n+m
// Next, I'm removing any duplicates from sorted array, cost O(n+m) time complexity.

// Total TC-> O(k + klogk + k)
// SC -> O(k)
// where k = n+m

public static List< Integer > sortedArray(int []a, int []b) {
  List<Integer> list = new ArrayList<Integer>();

  int n = a.length;
  int m = b.length;

  for (int i = 0; i < n; i++) {
      list.add(a[i]);
  }

  for (int i = 0; i < m; i++) {
      list.add(b[i]);
  }

  Collections.sort(list);

  int i = 0;

  while (i <= list.size() - 2) {
      if (list.get(i) == list.get(i + 1)) {
          list.remove(i + 1);
      }
      else {
          i += 1;
      }
  }

  return list;
}  


// Using TreeSet in Java.

// Time Complexity => O(n + m) if we exclude the conversion into ArrayList.
// else TC will be => O(n + m + (n+m)log(n+m))
// SC=> O(n + m) if we exclude the conversion into ArrayList.

public static List< Integer > sortedArray(int []a, int []b) {

    SortedSet<Integer> unioIntegers = new TreeSet<>();

    int n = a.length, m = b.length;

    for (int i = 0; i < n; i++) {
        unioIntegers.add(a[i]);
    }

    for (int i = 0; i < m; i++) {
        unioIntegers.add(b[i]);
    }

    return new ArrayList<>(unioIntegers);
}
    
// Optimal Approch !!

// TC -> O(n+m)
// SC -> O(n+m)

// Thought Process ( Two Pointer Approch )
// Put pointers on the first element of both arrays.
// Compare the elements if one of them is smaller, then consider that elemenet.
// Check if this element is not the last element of our new array, then add it to the new array.
// Pick the remaining elements of array by using loops.

public static List< Integer > sortedArray(int []a, int []b) {

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

  int n = a.length, m = b.length, 
      i = 0, j = 0;

  while (i < n && j < m) {

      int ele;

      if (a[i] > b[j]) {
          ele = b[j];
          j++;
      }
      else {
          ele = a[i];
          i++;
      }

      if (list.size() == 0 || list.get(list.size() - 1) != ele) {
          list.add(ele);
      }
  }

  int last = list.get(list.size() - 1);

  if (i != n) {
      for (int k = i; k < n; k++) {
          if (last != a[k]) {
              list.add(a[k]);
              last = a[k];
          }
      }
  }
  else if (j != m) {
      for(int k = j; k < m; k++) {
          if (last != b[k]) {
              list.add(b[k]);
              last = b[k];
          }
      }
  }

  return list;
}