26. Remove Duplicates from Sorted Array

Two Pointers (my solution)

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        int n = nums.length;
        if (n < 2) return n;
        int pos1 = 0;
        int pos2 = 0;
        int last = Integer.MIN_VALUE;
        while (pos2 < n) {
            int current = nums[pos2];
            if (current <= last) {
                pos2++;
            } else {
                nums[pos1] = nums[pos2];
                last = nums[pos1];
                k++;
                pos1++;
                pos2++;
            }
        }
        return k;
    }
}

Remarks:

1. TC: $O(n)$, SC: $O(1)$

Swap

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        int n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1]; // replace with the last element in the array
                n--; // check the new element again
            } else {
                i++;
            }
        }
        return n;
    }
}

Remarks:

1. TC: $O(n)$, SC: $O(1)$

2. Only runs when the sequence does not matter:

   the OJ provides the dudging method:

   int[] nums = [...]; // Input array
   int val = ...; // Value to remove
   int[] expectedNums = [...]; // The expected answer with correct length.
                               // It is sorted with no values equaling val.
   
   int k = removeElement(nums, val); // Calls your implementation
   
   assert k == expectedNums.length;
   sort(nums, 0, k); // Sort the first k elements of nums
   for (int i = 0; i < actualLength; i++) {
       assert nums[i] == expectedNums[i];
   }

   where the list is being sorted again, so sequence does not matter.

Simplified

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 2) return nums.length;

        int pos1 = 1; // the place that next element should be placed at

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[pos1 - 1]) {
                nums[pos1] = nums[i];
                pos1++;
            }
        }

        return pos1;
    }
}