26. Remove Duplicates from Sorted Array

26. Remove Duplicates from Sorted Array

Tags

C#

Leetcode

Coding

Competitive programming

Problem solving

Published

April 8, 2024

Author

Deegii

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.

Constraints:

The input array nums is sorted in non-decreasing order.

You must do this by modifying the input array in-place with O(1) extra memory.

Intuition:

Since the array is already sorted, duplicates will be adjacent to each other. We need to iterate through the array, keeping track of the last element encountered. If the current element is different from the last one, it is unique and should be kept. By maintaining an index pointing to the next position where a unique element should be placed, we can modify the array in-place.

Approach:

Initialize index to 0, which will track the position where unique elements will be placed.

Initialize last to an arbitrary large number to ensure it's not equal to any number in nums.

Iterate through the elements of nums.

If the current element (i) is different from the last element encountered, copy it to nums[index] and increment index.

Update last to the current element i.

Finally, return index, which represents the count of unique elements.

Complexity Analysis:

Time Complexity: Since we iterate through the array once, the time complexity is O(n), where n is the length of the input array nums.

Space Complexity: The algorithm operates in-place, using only a constant amount of extra space, hence the space complexity is O(1).

Code Implementation:


public class Solution {
    public int RemoveDuplicates(int[] nums) {
        int index = 0;
        int last = 1000; // An arbitrary large number
        foreach(int i in nums) {
            if(last != i) {
                nums[index] = i;
                index++;
            }
            last = i;
        }
        return index;
    }
}

Blog Posts

Went on business trip to China

Went on business trip to China

A Note on a business trip to China. Meeting several Chinese biggest refrigerator, freezer manufacturing companies

Thought Experiments

Creating a Barcode Detector Using the Browser BarcodeDetector API

Creating a Barcode Detector Using the Browser BarcodeDetector API

In this tutorial, we'll create a simple barcode detector web application using the Browser BarcodeDetector API. The app will access the user's webcam, display the video stream, and detect barcodes in real-time.

Computer Science

Software Development

Thought Experiments

27. Remove Element

27. Remove Element

Leetcode (Remove Element) problem solution using two pointers.

Problem solving

Competitive programming

Computer Science

Building your portfolio website backed by Notion as CMS

Building your portfolio website backed by Notion as CMS

Publish your portfolio notion page to the web under 30 minutes using Next.js.

Problem solving

45. Jump Game II

45. Jump Game II

Solve leetcode 45. Jump Game II using greedy approach.

Problem solving

Competitive programming

Greedy Algorithm

122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

Solve leetcode 122. Best Time to Buy and Sell Stock II using greedy algorithm

Problem solving

Competitive programming

121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

Solve leetcode 121. Best Time to Buy and Sell Stock using simple greedy algorithm.

Problem solving

Competitive programming

169. Majority Element

169. Majority Element

Solve leetcode 169. Majority Element with sorting method.

Problem solving

Competitive programming

80. Remove Duplicates from Sorted Array II

80. Remove Duplicates from Sorted Array II

Intuition and algorithm to solve 80. Remove Duplicates from Sorted Array II

Problem solving

1768. Merge strings Alternately (Beats 96.66%)

1768. Merge strings Alternately (Beats 96.66%)

2 pointer approach for solving a problem that merges two strings alternately.

Computer Science

Problem solving

Empowering legacy KonvaJS in React projects

Building visual editor tools with Konva and React.

Problem solving