Question

Formatted question description: https://leetcode.ca/all/26.html

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

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.

@tag-array

Algorithm

Use fast and slow pointers to record the traversed coordinates. At the beginning, both pointers point to the first number. If the two pointers point to the same number, the fast pointer will move forward. If they are different, both pointers will move forward. One step, so that when the fast pointer goes through the entire array, the current coordinate of the slow pointer plus 1 is the number of different numbers in the array.

Code

Java

// same thing, two pointers
public class Remove_Duplicates_from_Sorted_Array {

	public class Solution {
	    public int removeDuplicates(int[] nums) {
	        if(nums == null || nums.length == 0) {
	            return 0;
	        }

	        int i = 0; // slow pointer
	        int j = 0; // fast pointer

	        while(j < nums.length) {
	            while(j + 1< nums.length && nums[j] == nums[j + 1]) {
	                j++;
	            }

	            nums[i] = nums[j];

	            i++;
	            j++;
	        }

	        return i; // i is incremented, but is index. So same as length
	    }
	}

}

// OJ: https://leetcode.com/problems/remove-duplicates-from-sorted-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int removeDuplicates(vector<int>& A) {
        int j = 0;
        for (int n : A) {
            if (j - 1 < 0 || A[j - 1] != n) A[j++] = n;
        }
        return j;
    }
};

class Solution(object):
  def removeDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) <= 1:
      return len(nums)
    slow = 0
    for i in range(1, len(nums)):
      if nums[i] != nums[slow]:
        slow += 1
        nums[slow] = nums[i]
    return slow + 1

26 - Remove Duplicates from Sorted Array

Question

Algorithm

Code

All Problems

All Solutions