83. Remove Duplicates from Sorted List - Leetcode Solution

LeetCode problem Solution code

đź’ˇ Step-by-Step Thought Process

  1. Understand the problem: Given a sorted array nums, remove duplicates in-place and return the length of the array with unique elements.
  2. Initialize a pointer j to 1, representing the position to place the next unique element.
  3. Iterate through the array with index i from 1 to n-1 (where n is the length of nums):
    • If nums[i] is not equal to nums[i-1], it’s a new unique element.
    • Assign nums[i] to nums[j] and increment j.
  4. Return j as the length of the array with unique elements.

Code Solution

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head

        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

# Time Complexity: O(n)
# Space Complexity: O(1)

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;

        while (cur != nullptr && cur->next != nullptr) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }

        return head;
    }
};

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;

        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        
        return head;
    }
}

function deleteDuplicates(head) {
    let cur = head;

    while (cur && cur.next) {
        if (cur.val === cur.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }

    return head;
}

Detailed Explanation

Understanding the Problem: Remove Duplicates from Sorted List

The “Remove Duplicates from Sorted List” problem asks us to remove duplicate elements from a sorted array nums in-place, such that each element appears only once. The goal is to return the length of the array after duplicates have been removed.

Although the array may still contain the original values after the new length, only the first part (up to the returned length) will contain unique values.

Example:

  • Input: [0,0,1,1,1,2,2,3,3,4]
  • Output: 5, with the first five elements being [0,1,2,3,4]

Why This Problem Matters

This problem teaches one of the most fundamental patterns in array manipulation — the two-pointer technique. It is also highly relevant for real-world tasks such as cleaning up datasets, optimizing storage, or processing sorted inputs efficiently.

Efficient In-Place Solution Using Two Pointers

Since the input array is sorted, duplicates will always be adjacent. This property allows us to overwrite duplicates as we find them using a slow-runner/fast-runner strategy — often called the two-pointer technique.

Steps:

  1. Initialize a pointer j = 1. This will track the position to place the next unique element.
  2. Loop through the array with index i from 1 to n - 1:
    • If nums[i] != nums[i - 1], it’s a new unique element.
    • Assign nums[j] = nums[i] and increment j.
  3. After the loop, the first j elements of nums are unique. Return j as the new length.

Example Walkthrough

Input: [1, 1, 2]

  • Start with j = 1
  • i = 1: nums[1] == nums[0] → duplicate, skip
  • i = 2: nums[2] != nums[1] → unique, set nums[1] = nums[2] → array becomes [1, 2, 2]

Return value: 2, first 2 elements = [1, 2]

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), because we modify the array in-place and use only a few extra variables.

Edge Cases to Consider

  • Empty array → return 0
  • Array with all duplicates → only one element kept
  • Array with all unique values → no change, return full length

Conclusion

The “Remove Duplicates from Sorted List” problem is an essential pattern for working with arrays efficiently. By using the two-pointer approach, we avoid unnecessary shifting or use of additional data structures, allowing us to modify the input directly and save on memory and time.

NEW!Need help landing software roles? đź’ˇ