Remove Duplicate Items from a Sorted Array

Introdução

Welcome to the Art of Coding’s blog. In today’s edition, we’re tackling a familiar challenge often encountered in technical interviews: removing duplicated items from a sorted array. This task isn’t just a recurring theme in interviews; it’s also an excellent opportunity to hone your skills in array manipulation.

In this article, we’ll be diving into practical examples using two of the most popular programming languages: Java and Python.

Before we delve into the technical specifics, let’s first gain a clear understanding of the problem at hand.

Understanding the Challenge: Efficiently Removing Duplicates in a Sorted Array

In addressing this challenge, two main requirements stand out: the process must be ‘in-place’, meaning that duplicate items should be removed without the need for additional data structures for temporary storage. Secondly, after the duplicates have been taken out, the task is to ‘return’ the length of the new array, which should consist only of unique elements.

Take, for example, a sorted array like [1, 1, 2, 2, 3, 4, 4, 5]. In this case, the numbers 1, 2, and 4 appear more than once. The objective is to transform this array into [1, 2, 3, 4, 5, x, x, x], where ‘x’ in the transformed array could signify an empty space or any value that is irrelevant.

The array’s new size should be 5, reflecting the count of unique elements remaining after the duplicates are removed. This new size of the array is what needs to be returned for this problem.

Java and Python Code Examples

We will now move on to implementing the solution for removing duplicate items from a sorted array, using Java and Python.

public class Solution {
    public static int removeDuplicatedItems(int[] numbers) {
        int newLength = numbers.length;
        int left = 0;
        int right = 1;

        while (right < numbers.length) {
            if (numbers[left] == numbers[right]) {
                newLength--;
            } else {
                numbers[left + 1] = numbers[right];
                left++;
            }
            right++;
        }
        return newLength;
    }

    public static void main(String[] args) {
        int[] numeros = {1, 1, 2, 2, 3, 4, 4, 5};
        System.out.println(removeDuplicatedItems(numeros));

    }
}

def remove_duplicated_items(numbers):
    left = 0

    for right in range(1, len(numbers)):
        if numbers[left] != numbers[right]:
            left += 1
            numbers[left] = numbers[right]

    return left + 1

def main():
    numbers = [1, 1, 2, 2, 3, 4, 4, 5]
    new_length = remove_duplicated_items(numbers)
    print(new_length)
    print(numbers[:new_length])  # Imprime a lista sem os duplicados

if __name__ == "__main__":
    main()

Breaking Down the Code

Imagine you have a line of people, and some of them are twins standing next to each other. Your job is to make sure each person in the line is “unique”, so you need to ask one twin from each pair to step out of the line.

Here’s how the method removeDuplicatedItems does this:

Count Everyone: First, you count how many people are in the line. This is your newLength.
Start Comparing: You stand at the beginning of the line (left) and look at the first and second person (right).
Go Through the Line:
- If the first and second person are twins (the same), you ask one of them to step out. This means you have one less person to worry about, so you reduce your count (newLength).
- If they are not twins, you move one step forward in the line and compare the next pair.
Keep Moving: You keep moving through the line, comparing people until you reach the end.
Final Count: Once you’ve gone through the whole line, you know how many unique people are left. That’s the number you report back (return newLength).

Complexity Analysis

Time Complexity Analysis

The algorithm goes through the list of numbers just once, using two markers: left and right. In each step, one of these markers moves forward. The right marker travels across the entire list, while the left marker moves only under certain conditions. So, the time it takes to complete this process depends directly on the length of the list, N.

This means the time complexity is linear, or in technical terms, O(n).

Space Complexity Analysis

Regarding the space it uses, the algorithm doesn’t need extra space that increases as the size of the input grows. It works with what it has from the start. Therefore, the space complexity is constant—it doesn’t change no matter how big the input is.

In technical terms, this is O(1).

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Conclusion

This algorithm for removing duplicate items from a list has highlighted the importance of understanding and efficiently manipulating arrays, especially through the use of the two-pointer technique. Despite its apparent simplicity, this algorithm can pose a significant challenge for those not accustomed to array manipulation. The key challenge lies in the need to keep track of multiple indices simultaneously and understand how they interact throughout the array.

The two-pointer approach is an intriguing technique and provides an efficient way to solve problems that might seem complex at first glance.

🌟 If you’re eager to sharpen your coding skills and tackle more such interesting challenges, don’t forget to explore and practice more algorithms! Dive in, experiment, and keep learning. 💻🚀

🔗 Want to dive deeper into the world of algorithms? Click here to explore more articles and expand your understanding of different algorithmic concepts!

Happy coding!

References

Cracking the Coding Interview: This book is a renowned best-seller and a personal favorite – an essential book for preparing for technical interviews!
Designing Data-Intensive Applications: ‘ is a go-to reference for creating scalable, robust, and high-performance applications!