package com.freetymekiyan.algorithms.level.easy;

/**
 * Given a sorted array, remove the duplicates in place such that each element appear only once and return the new
 * length.
 * <p>
 * Do not allocate extra space for another array, you must do this in place with constant memory.
 * <p>
 * For example,
 * Given input array nums = [1,1,2],
 * <p>
 * Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't
 * matter what you leave beyond the new length.
 * <p>
 * Company Tags: Microsoft, Bloomberg, Facebook
 * Tags: Array, Two Pointers
 * Similar Problems: (E) Remove Element
 */
public class RemoveDuplicatesFromSortedArray {

    /**
     * Two Pointers.
     * Use the length to be returned as a pointer to the next position to be filled.
     * For each number n in nums:
     * | If length is 0 or n > nums[length - 1]:
     * |   Update nums[length] to n. Increment length by 1.
     * Return length.
     */
    public static int removeDupB(int[] nums) {
        int len = 0;
        for (int n : nums) {
            if (len < 1 || n > nums[len - 1]) {
                nums[len++] = n;
            }
        }
        return len;
    }
}

@@ -47,16 +47,66 @@
 y;%0A%0A/**%0A
+ * 26. Remove Duplicates from Sorted Array%0A * %3Cp%3E%0A
  * Given
@@ -792,22 +792,32 @@
 gth 
-to be returned
+of the distinct elements
  as 
@@ -924,17 +924,18 @@
  0 or n 
-%3E
+!=
  nums%5Ble
@@ -1050,15 +1050,8 @@
 lic 
-static 
 int 
@@ -1059,17 +1059,23 @@
 emoveDup
-B
+licates
 (int%5B%5D n
@@ -1155,18 +1155,20 @@
 len 
-%3C 1
+== 0
  %7C%7C n 
-%3E
+!=
  num
@@ -1264,10 +1264,381 @@
 ;%0A    %7D%0A
-%7D
 %0A
+    public int removeDuplicates2(int%5B%5D nums) %7B%0A        int len = 1;%0A        for (int i = 1, j = i; i %3C nums.length; i = j) %7B%0A            while (j %3C nums.length && nums%5Bj%5D == nums%5Blen - 1%5D) %7B%0A                j++;%0A            %7D%0A            if (j %3C nums.length) %7B%0A                nums%5Blen%5D = nums%5Bj%5D;%0A                len++;%0A            %7D%0A        %7D%0A        return len;%0A    %7D%0A%7D

update 26. Remove Duplicates from Sorted Array