Master Remove Duplicates from Sorted Array (LeetCode 26): In-Place O(1) Solution | Day 4 of 180

Master Remove Duplicates from Sorted Array (LeetCode 26): In-Place O(1) Solution | Day 4 of 180

by 

================================================================================
BLOG ARTICLE CONTENT (Markdown / HTML)
================================================================================

# 180-Day DSA Roadmap | Day 4: Remove Duplicates from Sorted Array (LeetCode #26)

* **Topic:** Arrays & Strings  
* **Pattern:** Two Pointers (Slow & Fast / In-Place Filtering)  
* **Difficulty:** Easy / Core Foundation  
* **LeetCode Problem:** LeetCode #26 - Remove Duplicates from Sorted Array  
* **Target Companies:** Microsoft, Amazon, Google, Meta, Bloomberg  

---

## 1. Problem Overview

You are provided an array of integers `nums` ordered non-decreasingly. Your task is to eliminate duplicate entries directly within the original array so that each distinct value appears only once while preserving their relative sequence.

The function should return the total count `k` of distinct items.

### Constraints & Requirements
* 1 <= nums.length <= 3 * 10^4
* -100 <= nums[i] <= 100
* `nums` is sorted in ascending order.
* Memory usage must strictly stay at O(1) auxiliary space (no sets, extra arrays, or hash maps).
* The first `k` slots of `nums` must hold the unique elements; whatever remains beyond index `k - 1` does not matter.

### Example Walkthrough
```text
Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: k = 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Explanation:
The five unique numbers are 0, 1, 2, 3, and 4.
The initial 5 cells contain these elements in order, and the function returns 5.

2. Pattern Recognition: The Slow-Fast Pointer

Why does the two-pointer technique fit this challenge so well?

  1. Monotonic Clustering: Since the array is pre-sorted, duplicate values always sit consecutively. You never need to scan back across previous entries—you only have to compare with the most recently stored unique value.
  2. Safe Overwriting: The write index stays behind or matches the read index (writer <= reader), which guarantees you will never overwrite data before the reading pointer has evaluated it.
  3. Strict Memory Limits: Allocating an additional hash set or dynamic array breaks the O(1) space constraint, making an in-place pointer scan the required solution.

The two pointers take on distinct duties:

  • Writer (Slow): Points to the location where the next unique entry should be placed.
  • Reader (Fast): Moves across the array to uncover values distinct from the current prefix.

3. Algorithmic Approaches

Approach 1: Extra Set / Buffer (Invalid)

  • Insert all values into an ordered set, then transfer the unique elements back into nums.
  • Time Complexity: O(N)
  • Space Complexity: O(N)
  • Verdict: Fails the in-place constraint.

Approach 2: Optimal Slow-Fast Scan (MNC Standard)

  • Because an array of length 1 or more always has its first element in the correct place, start writer = 1 and reader = 1.
  • Step reader forward through each index:
    • Compare nums[reader] with nums[writer - 1] (the most recently secured unique value).
    • If they differ, copy nums[reader] into nums[writer] and advance writer++.
    • If they match, ignore the duplicate and keep advancing reader.
  • When the scan completes, writer equals the count of unique elements k.

Plaintext

Visual Execution Trace:
Input: nums = [1, 1, 2] | Initialize: writer = 1, reader = 1

Step 1 (reader = 1):
  Compare nums[reader] (1) with nums[writer - 1] (nums[0] = 1).
  They match! Skip duplicate. reader moves forward.
  [ 1 , 1 , 2 ]
        ▲
      w & r

Step 2 (reader = 2):
  Compare nums[reader] (2) with nums[writer - 1] (nums[0] = 1).
  They differ! Found a new unique number.
  Write it: nums[writer] = nums[reader] ──► nums[1] = 2
  Increment writer++ ──► writer becomes 2.
  [ 1 , 2 , 2 ]
            ▲
            w (at index 2)

Result: Return writer = 2. The first two positions are [1, 2].

4. Production-Ready Code Implementations

Java Solution

Java

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

        int writer = 1;

        for (int reader = 1; reader < nums.length; reader++) {
            // Compare current element against the last recorded unique value
            if (nums[reader] != nums[writer - 1]) {
                nums[writer] = nums[reader];
                writer++;
            }
        }

        return writer;
    }
}

Python 3 Solution

Python

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        if not nums:
            return 0

        writer = 1

        for reader in range(1, len(nums)):
            # Compare current element against the last recorded unique value
            if nums[reader] != nums[writer - 1]:
                nums[writer] = nums[reader]
                writer += 1

        return writer

C++ Solution

C++

#include <vector>

class Solution {
public:
    int removeDuplicates(std::vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }

        int writer = 1;

        for (size_t reader = 1; reader < nums.size(); ++reader) {
            // Compare current element against the last recorded unique value
            if (nums[reader] != nums[writer - 1]) {
                nums[writer] = nums[reader];
                writer++;
            }
        }

        return writer;
    }
};

5. Complexity Analysis

  • Time Complexity: O(N)
    A single pass scans through the collection. Every iteration executes constant-time comparisons and variable increments.
  • Space Complexity: O(1)
    All modifications occur in-place over the existing buffer, using only scalar pointer variables.

6. Key Takeaways & Interview Follow-Up

  • The writer - 1 Insight: Checking against nums[writer - 1] rather than nums[reader - 1] ensures you always validate against the clean, processed section of the array.
  • Generalizing to K Allowed Duplicates: This exact pattern directly solves LeetCode #80 (Remove Duplicates from Sorted Array II, where elements may appear up to twice). In that variation, simply start at index 2 and compare nums[reader] against nums[writer - 2].

Master Remove Duplicates from Sorted Array (LeetCode 26): In-Place O(1) Solution | Day 4 of 180

META DESCRIPTION:
Solve LeetCode 26 (Remove Duplicates from Sorted Array) in linear time and O(1) space. Master the slow-fast two-pointer pattern with clean Java, Python, and C++ code.


Remove Duplicates Sorted Array LeetCode 26, Slow Fast Two Pointer Array, In Place Array Deduplication, LeetCode 26 Java Python Cpp


leetcode 26, remove duplicates from sorted array, two pointers technique, slow fast pointer, reader writer pattern, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, two pointers pattern, leetcode easy, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, meta coding interview, adobe coding questions, apple interview questions, leetcode 26 java, leetcode 26 python, leetcode 26 cpp, java dsa, python dsa, cpp dsa, time complexity o n, space complexity o 1, array interview questions, inplace deduplication, array compaction, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, software development engineer, sde 1 preparation, array algorithms, single pass algorithm, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap

Follow our YouTube Channels:
Trendy VS Vlogs: https://youtube.com/@trendyvsvlogs?si=Xd3L31p5zPXggomY
WhatsApp Channel: https://whatsapp.com/channel/0029Vb9H4vC545v2HaoKk735

Leave a Comment