algoadvance

Leetcode 26. Remove Duplicates from Sorted Array

Problem Statement

You are given a sorted array nums of integers. Your task is to remove the duplicates in-place such that each element appears only once and returns the new length of the array. The relative order of the elements should be kept the same.

You must implement the solution with O(1) extra memory.

Example:

Input: nums = [1, 1, 2]
Output: 2, nums = [1, 2, _]

(Note: “_” represents an irrelevant element beyond the returned length)

Clarifying Questions

1. Q: Can the input array be empty? A: Yes, the input array can be empty.

2. Q: What values can the elements in the array take? A: The elements in the array are integers and can be positive, negative, or zero.

3. Q: Should the solution alter the input array in any particular way regarding the unused elements? A: No specific values are required for the elements beyond the returned length. They can remain as they are or be replaced by any value.

Strategy

1. We will use a two-pointer technique to solve the problem.
2. One pointer (j) will iterate over the array, while the other pointer (i) will track the position of the unique elements.
3. Initially, both pointers will start at the beginning of the array. Pointer i will only increment when a new unique element is found by the j pointer.
4. Elements from the j pointer will be copied to the i position when a unique element is encountered.
5. Finally, the value of i + 1 will give us the length of the unique elements.

This approach maintains the O(1) extra space constraint.

Code

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the input array. This is because we iterate through the array once with the j pointer.
• Space Complexity: O(1), since we only use a constant amount of extra space for the pointers i and j.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?