💬 Discord
Sign In
NeetCode #184LC-26EasyTwo PointersNC 250
← Back to All Problems

#184 · #26 · Remove Duplicates from Sorted Array(删除有序数组中的重复项)

📌 Problem Statement & Constraints

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place so each element appears once, and return the new length k. The first k slots must hold the unique values in order. Constraints: 1 <= nums.length <= 3 * 10^4, -100 <= nums[i] <= 100.

💡 Core Algorithmic Approaches

  1. Because the array is sorted, duplicates are adjacent, so a single write pointer suffices.
  2. Keep k as the number of unique elements written so far. The first element is always kept.
  3. For each subsequent element, write it to nums[k] only if it differs from nums[k-1], then increment k.
  4. The comparison is against the last written element, not the previous read element -- the distinction matters when runs are longer than two.

💻 Benchmark Python3 Implementation

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        k = 1                          # first element is always kept
        for i in range(1, len(nums)):
            if nums[i] != nums[k - 1]:  # compare against the last written value
                nums[k] = nums[i]
                k += 1
        return k

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): in place.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing with nums[i-1]: this fails when the write pointer lags, because nums[i-1] may be a value that was already overwritten or skipped. Compare with nums[k-1] instead.
  • Building a new list: the problem requires in-place modification.
  • Initialising k to 0: the first element is always unique, so k starts at 1 (and the loop starts at index 1).
  • Assuming the array is unsorted: sortedness is what makes the adjacent-comparison approach valid.