algoadvance

Leetcode 26. Remove Duplicates from Sorted Array

Problem Statement:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the length of the array part with unique elements as k, where the first k elements of nums should hold the unique elements in order, with no concern about the elements in the remaining part of the array.

Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.

Example:

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

Explanation: Your function should return k = 2, and the first two elements of nums are 1 and 2. It does not matter what you leave beyond the returned k (hence they are underscores).

Clarifying Questions:

  1. Can the array be empty?
    • Yes, it can be. In this case, the output should be 0.
  2. Is the array always sorted in non-decreasing order?
    • Yes, that’s a given condition in the problem statement.
  3. How should duplicated elements at the end be handled?
    • We simply ensure the first k elements are unique, with no constraints on the elements beyond this point.

Strategy

  1. Initialize lastUniqueIndex to 0 (this will track the index of the last unique element).
  2. Iterate through the array starting from the second element.
  3. If the current element is different from nums[lastUniqueIndex], increment lastUniqueIndex and update nums[lastUniqueIndex] to the current element.
  4. Return lastUniqueIndex + 1 as the count of unique elements.

Code

#include <vector>

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

    int lastUniqueIndex = 0;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] != nums[lastUniqueIndex]) {
            lastUniqueIndex++;
            nums[lastUniqueIndex] = nums[i];
        }
    }
    return lastUniqueIndex + 1;
}

Time Complexity

This approach ensures that only unique elements are kept in the first part of the array, maintaining the original order, and fulfilling the problem’s constraints.

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