26. Remove Duplicates from Sorted Array

Hello, reader 👋🏽 ! Welcome to day 41 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 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.
• Since it is impossible to change the length of the array in some languages, place the result in the first part of the array nums.
• More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result.

• Return k after placing the final result in the first k slots of nums. This must be done in-place without using extra space.

• E.g.:

  • nums = [1,1,2] => 2
  • nums = [0,0,1,1,1,2,2,3,3,4] => 5

💬 Thought Process - 2 Pointers

• We can use the two pointers technique to keep track of the indices of numbers in the original array and the indices of the numbers that keeps track of the k non duplicates.
• The iteration starts with index = 1 and k = 0. There would be two cases:
  1. nums[k] == nums[index] => we don't include nums[index]. We only increment index.
  2. nums[k] != nums[index] => we includes nums[index] to nums[k+1]. Increment k and index.
• We keep repeating this process until the end of the array.
• Since we need the length and k is 0-based index, we'll have to increment k and return.

👩🏽‍💻 Solution - 2 Pointers

• Below is the code for the two pointers approach.

  class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
  
        int n = nums.length;
        int k = 0;
        int i = 1;
        while(i < n) {
            if(nums[i] != nums[k]) {
                nums[++k] = nums[i++];
            } 
            else {
                i++;
            }
        }
  
        return k+1;
    }
  }
  

  Time Complexity: O(n)
  - n = length of array
  Space Complexity: O(1)
  

You can find the link to the GitHub repo for this question here: 26. Remove Duplicates from Sorted Array.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!