26. Remove Duplicates from Sorted Array

Source link: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Design

As the problem stated that the the input array should be modified in-space with O(1) memory, extra space cannot be initiated for storing the data. To solve the problem, the two-pointer pattern can be applied for recording positions.

1. Initialize two pointers i, j at the start of the array.
2. Travel through the array nums leading by the pointer j and record the number preparing to be modified by the pointer i.
3. Start the traverse process, once if the value of nums[j] != nums[i - 1] (the last modified element) or i = 0, modify the value of nums[i] to nums[j] and move the pointer i forward.

Implementation

class Solution {
  public int removeDuplicates(int[] nums) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) &#123;
      if (i == 0 || nums[j] != nums[i - 1]) &#123;
        nums[i++] = nums[j];
      &#125;
    &#125;
    return i;
  &#125;
&#125;

Complexity Analysis

Time: $O(n)$

Space: $O(1)$