Nitin Raturi
Nitin Raturi's Software Engineering Blog

Follow

Nitin Raturi's Software Engineering Blog

Follow
Remove Duplicates from Sorted Array - Leetcode #26

Photo by Stefan Cosma on Unsplash

Remove Duplicates from Sorted Array - Leetcode #26

Nitin Raturi's photo
Nitin Raturi
ยทMar 31, 2023ยท

3 min read

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.

Example 1:

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

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

Example 2:

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

Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.

It does not matter what you leave beyond the returned k (hence they are underscores).

Read complete problem statement on leetcode.

Solution

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

def f(nums):
    j = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i-1]:
            nums[j] = nums[i]
            j += 1
    return j

print(f(nums))
print(nums)

Explanation

Now, let's look at the code snippet. The function is called f and takes the array nums as an argument. The first line of the function initializes a variable j to 1, which represents the index of the first unique element in the array.

Then the function iterates through the array using a for loop, starting from the second element (index 1) to the end.

For each element nums[i], the function compares it with the previous element nums[i-1]. If they are not equal, it means that nums[i] is a unique element, so the function writes it to the nums[j] position, and increments j by 1 to move to the next index.

If they are equal, it means that nums[i] is a duplicate, so the function skips it and moves on to the next element.

At the end of the loop, the function returns j, which represents the number of unique elements in the array. The array itself is modified in place, with the duplicates removed and the order of the unique elements preserved.

Built in solution

You can use a list comprehension with a conditional statement to filter out the duplicates.

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
unique_nums = [nums[i] for i in range(len(nums)) if i == 0 or nums[i] != nums[i-1]]
print(unique_nums)

Real life example

Imagine you are a librarian, and your job is to organize a collection of books on a shelf. The books are arranged in non-decreasing order of their publication date, and some of them are duplicates.

Your task is to remove the duplicate books and keep the order of the remaining books intact.

You start by looking at the first book on the shelf and writing down its title. Then you look at the next book and compare its title with the previous book.

If the titles are the same, you skip the book and move on to the next one. But if the titles are different, you write down the title of the new book on the next line of your list, and move on to the next book.

You keep doing this until you have gone through all the books on the shelf.

Did you find this article valuable?

Support Nitin Raturi by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
ย 
Share this