Skip to main content

Leetcode 26: Remove Duplicates from Sorted Array

 

1. Problem Statement (Simple Explanation):


You are given an integer array nums that is sorted in non-decreasing order.

You must:

  • Remove duplicates in-place so that each unique element appears only once.

  • Keep the relative order of unique elements.

  • Return k, the number of unique elements.

After your function:

  • The first k elements of nums should contain the unique elements in sorted order.

  • Anything beyond index k - 1 can be ignored.

You must use only constant extra space O(1).


2. Examples:


Example 1:


Input: nums = [1,1,2]

Unique elements are [1,2].

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

(Underscore means “don’t care” beyond k.)


Example 2:


Input: nums = [0,0,1,1,1,2,2,3,3,4]

Unique elements: [0,1,2,3,4].

Output: k = 5, nums = [0,1,2,3,4,_,_,_,_,_]


Constraints:


  • 1 <= nums.length <= 3 x 104

  • -100 <= nums[i] <= 100

  • nums is sorted in non-decreasing order.


3. Approach – Two Pointers (Slow/Fast) In-Place:


Because the array is sorted, duplicates are grouped together. We can use two pointers:

  • i (slow pointer): position of last unique element.

  • j (fast pointer): current position we’re scanning.


Intuition:


  • Start with the first element as unique.

  • Traverse from left to right:

    • If nums[j] != nums[i], we found a new unique element:

      • Move i one step to the right.

      • Copy nums[j] to nums[i].

    • If nums[j] == nums[i], it’s a duplicate, skip it.

At the end:

  • The first i + 1 elements of nums are the unique values.

  • Return i + 1 as k.


Algorithm (Step-by-Step):


  1. If nums.length == 0 (not needed per constraints, but safe), return 0.

  2. Initialize:

    • i = 0 (index of last unique element).

  3. For j from 1 to n - 1:

    • If nums[j] != nums[i]:

      • i++

      • nums[i] = nums[j].

  4. After the loop, the number of unique elements is i + 1.

  5. Return i + 1.


Pseudo-code:



Complexity:


Let n = len(nums):

  • Time: O(n)

Each element is visited once.

  • Space: O(1)

In-place, only a few extra variables.


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more