Removing duplicate elements from a sorted array is a common Java programming interview question. The goal is to keep only one occurrence of each distinct value while modifying the original array.
For example, consider the sorted array {1, 1, 2, 2, 3, 4, 4, 5}. After removing duplicates, the unique elements are {1, 2, 3, 4, 5}.
The important requirement is to perform this operation in place. This means the program should not create another array to store the unique values. Instead, it should rearrange the elements inside the existing array.
Because the array is already sorted, duplicate values appear next to each other. This makes the problem easier to solve using the two-pointer technique. The algorithm processes the array in a single traversal and uses constant extra space.
In this tutorial, I will explain how to remove duplicates from a sorted array in Java using two pointers. I will show the complete program, walk through each iteration, explain important edge cases, and discuss the time and space complexity.
Understanding the Problem
Suppose you have the following sorted integer array:
int[] numbers = {1, 1, 2, 2, 3, 4, 4, 5};The array contains eight elements, but only five distinct values.
The expected unique elements are:
[1, 2, 3, 4, 5]The program should rearrange the existing array so that the unique elements occupy its first five positions.
It should also return the number of unique elements, which is 5.
Important: The Array Length Does Not Change
Java arrays have a fixed length. You cannot reduce the length of an existing array after it has been created.
Therefore, removing duplicates in place does not physically shrink the array.
Instead, the method returns a new logical length. The first part of the array contains the unique values, while the remaining positions are no longer part of the result.
For example:
Original array:
[1, 1, 2, 2, 3, 4, 4, 5]
Unique elements:
[1, 2, 3, 4, 5]
Number of unique elements:
5The values beyond index 4 are ignored because they are outside the logical result.
Java Program to Remove Duplicates from a Sorted Array In Place
The most efficient solution uses two pointers named read and write.
readexamines each element in the array.writeidentifies the position where the next unique value should be stored.
Whenever the current element differs from the last unique element, the program copies it to the next available position.
Since the array is sorted, equal values appear together. There is no need to compare the current element with every previous element.
Complete Java Program
Create a Java class named RemoveDuplicatesSortedArray and add the following code:
import java.util.Arrays;
import java.util.Objects;
public class RemoveDuplicatesSortedArray {
public static void main(String[] args) {
int[] numbers = {1, 1, 2, 2, 3, 4, 4, 5};
System.out.println("Original array: "
+ Arrays.toString(numbers));
// Remove duplicates and get the number of unique elements.
int uniqueCount = removeDuplicates(numbers);
System.out.println("Number of unique elements: "
+ uniqueCount);
System.out.println("Array after removing duplicates: "
+ Arrays.toString(
Arrays.copyOf(numbers, uniqueCount)
));
}
/**
* Removes duplicate values from a sorted array in place.
*
* The first returned-length positions contain the unique
* elements in their original sorted order.
*
* @param numbers a sorted integer array
* @return the number of distinct elements
* @throws NullPointerException if the array is null
*/
public static int removeDuplicates(int[] numbers) {
Objects.requireNonNull(numbers, "Array must not be null");
// An empty array contains no unique elements.
if (numbers.length == 0) {
return 0;
}
// The first element is always unique.
int write = 1;
// Read each remaining element.
for (int read = 1; read < numbers.length; read++) {
// Compare with the last unique element.
if (numbers[read] != numbers[write - 1]) {
// Store the next distinct value.
numbers[write] = numbers[read];
write++;
}
}
// Return the logical length of the deduplicated array.
return write;
}
}Output
Original array: [1, 1, 2, 2, 3, 4, 4, 5]
Number of unique elements: 5
Array after removing duplicates: [1, 2, 3, 4, 5]Note: The removeDuplicates() method does not create a new array. It modifies the input array directly. The Arrays.copyOf() call in main() is used only to display the valid part of the result as a separate array.
How Does the Two-Pointer Algorithm Work?
The algorithm maintains a position for the next unique element and scans the array from left to right.
Step 1: Handle an Empty Array
The method first checks whether the array is empty.
if (numbers.length == 0) {
return 0;
}An empty array has no elements to process, so the method returns zero.
Step 2: Initialize the Write Pointer
The first element of a non-empty sorted array is always the first unique value.
Therefore, the next unique element should be written at index 1.
int write = 1;The write variable also represents the number of unique elements found so far.
Step 3: Traverse the Array
The read pointer starts at index 1.
for (int read = 1; read < numbers.length; read++)There is no need to process index 0 again because its value is already part of the result.
Step 4: Identify the Next Unique Element
The program compares the current value with the last unique value:
if (numbers[read] != numbers[write - 1])If the values are different, the current element is a new distinct value.
The program copies it to the position identified by write and then increments the pointer.
numbers[write] = numbers[read];
write++;If the values are equal, the program skips the duplicate.
Step 5: Return the Number of Unique Elements
Once all elements have been processed, the method returns write.
This value tells the caller how many elements at the beginning of the array belong to the deduplicated result.
Step-by-Step Dry Run
Consider the following sorted array:
[1, 1, 2, 2, 3]Initially, write = 1.
The first element, 1, is already considered unique.
| Read Index | Current Value | Action | Write After Step |
|---|---|---|---|
| 1 | 1 | Skip duplicate | 1 |
| 2 | 2 | Write 2 at index 1 | 2 |
| 3 | 2 | Skip duplicate | 2 |
| 4 | 3 | Write 3 at index 2 | 3 |
After processing all elements, the first three positions contain:
[1, 2, 3]The method returns 3.
The physical array still has five positions. Only the first three positions contain the logical result.
How to Print Unique Elements Without Creating Another Array
In the complete program, Arrays.copyOf() creates a new array for display purposes.
If you want to avoid creating another array entirely, print only the first uniqueCount elements using a loop.
Java Program
public class RemoveDuplicatesWithoutExtraArray {
public static void main(String[] args) {
int[] numbers = {1, 1, 2, 2, 3, 3, 4};
int uniqueCount = removeDuplicates(numbers);
System.out.println("Number of unique elements: "
+ uniqueCount);
System.out.print("Unique elements: ");
// Print only the valid portion of the original array.
for (int i = 0; i < uniqueCount; i++) {
System.out.print(numbers[i] + " ");
}
System.out.println();
}
/**
* Removes duplicates from a sorted integer array in place.
*
* @param numbers a sorted array
* @return the number of unique elements
*/
public static int removeDuplicates(int[] numbers) {
if (numbers == null) {
throw new IllegalArgumentException(
"Array must not be null"
);
}
if (numbers.length == 0) {
return 0;
}
int write = 1;
for (int read = 1; read < numbers.length; read++) {
if (numbers[read] != numbers[write - 1]) {
numbers[write] = numbers[read];
write++;
}
}
return write;
}
}Output
Number of unique elements: 4
Unique elements: 1 2 3 4 This version performs the complete operation without allocating another array.
It uses only a few integer variables, so its additional space complexity is constant.
Does the Original Array Change?
Yes. The algorithm modifies the original array by overwriting duplicate positions with distinct values.
Consider this array:
[1, 1, 2, 2, 3]After calling the method, the physical array may contain:
[1, 2, 3, 2, 3]The method returns 3.
Only these values belong to the valid result:
[1, 2, 3]The values remaining after index 2 are not part of the deduplicated result. Their contents should be ignored.
This behavior is important because in-place removal does not change the physical length of a Java array.
How to Run the Java Programs
You can run these examples using IntelliJ IDEA, Eclipse, Visual Studio Code, or the command line.
To run the first program:
- Install a Java Development Kit (JDK).
- Create a file named
RemoveDuplicatesSortedArray.java. - Copy the complete code from the first example into the file.
- Open a terminal in the folder containing the file.
- Compile and run the program using the following commands:
javac RemoveDuplicatesSortedArray.java
java RemoveDuplicatesSortedArrayThe program prints the original array, the number of distinct values, and the deduplicated result.
Important Edge Cases
A correct implementation should handle empty arrays, single-element arrays, negative numbers, and arrays containing only duplicate values.
| Input Array | Unique Elements | Returned Length |
|---|---|---|
| {1, 1, 2, 2, 3} | [1, 2, 3] | 3 |
| {5, 5, 5, 5} | [5] | 1 |
| {10, 20, 30} | [10, 20, 30] | 3 |
| {-3, -3, -1, 0, 0} | [-3, -1, 0] | 3 |
| {7} | [7] | 1 |
| {} | [] | 0 |
Time and Space Complexity
Let n represent the number of elements in the input array.
Time Complexity: O(n)
The algorithm traverses the array once using the read pointer.
Each iteration performs a comparison and, when required, an assignment.
Therefore, the time complexity is O(n).
Space Complexity: O(1)
The algorithm uses only two integer variables:
readwrite
No additional array or collection is required to remove duplicates.
Therefore, the extra space complexity is O(1).
Creating a separate array with Arrays.copyOf() for display requires additional space, but it is not part of the in-place removal algorithm.
Why Does the Algorithm Require a Sorted Array?
The two-pointer solution relies on the fact that duplicate values appear next to each other in a sorted array.
For example:
[1, 1, 2, 2, 3, 3]Every duplicate is located next to another occurrence of the same value.
This allows the algorithm to identify duplicates by comparing the current element with the last unique element.
However, consider an unsorted array:
[1, 2, 1, 3, 2]Duplicate values are no longer adjacent.
The same two-pointer logic would not remove all duplicates correctly because it only compares the current element with the last accepted value.
For an unsorted array, you can use a HashSet to track previously encountered values or sort the array first if changing its order is acceptable.
Important: The method in this tutorial assumes the input is already sorted in ascending order. It does not check whether the array is sorted.
Common Mistakes When Removing Duplicates from a Sorted Array
1. Assuming the Array Becomes Shorter
Java arrays have a fixed length. The algorithm cannot reduce the original array's length.
Instead, it returns the number of unique elements. Only the first returned-length positions should be used.
2. Printing the Entire Array After Removal
After removing duplicates in place, the remaining positions may still contain old values.
Printing the entire physical array can make it appear as though duplicates were not removed.
Print only the first uniqueCount elements.
3. Starting the Write Pointer at Zero
For a non-empty array, the first value is already unique.
Therefore, the write pointer should start at index 1:
int write = 1;4. Ignoring Empty Arrays
An empty array contains no unique elements.
The method should return zero before attempting to access the first array element.
5. Applying the Algorithm to an Unsorted Array
The algorithm assumes duplicate values are adjacent.
Using it with an unsorted array can produce incorrect results.
Ensure the input is sorted before applying this technique.
Frequently Asked Questions
How do you remove duplicates from a sorted array in Java?
Use two pointers. One pointer reads the elements, while the other tracks where the next distinct value should be stored. The method returns the number of unique elements.
Can I remove duplicates without using another array?
Yes. The two-pointer approach modifies the existing array directly and uses O(1) extra space.
Does removing duplicates change the length of the Java array?
No. Java arrays have a fixed length. The method returns a logical length representing the number of unique elements.
What is the time complexity of removing duplicates from a sorted array?
The two-pointer approach takes O(n) time because it examines each array element once.
Can the two-pointer approach handle negative numbers?
Yes. It compares integer values directly, so it works with negative numbers, zero, and positive numbers as long as the array is sorted.
Does this algorithm work for unsorted arrays?
No. It depends on duplicate values being adjacent. For an unsorted array, use a different approach, such as tracking encountered values with a set.
Why is the two-pointer approach useful in coding interviews?
It demonstrates how to process an array efficiently without allocating additional storage. The same technique is useful in several other array problems.
Conclusion
In this tutorial, you learned how to remove duplicates from a sorted array in Java using the two-pointer technique.
The algorithm maintains a read pointer to examine each element and a write pointer to store distinct values. Because the input array is sorted, duplicate elements can be identified through a simple comparison.
The method modifies the original array, returns the number of unique elements, and uses constant extra space. Its time complexity is O(n), making it an efficient solution for this problem.
For Java coding interviews, I recommend practicing this approach until you understand how the read and write pointers interact. Once you are comfortable with it, try related problems such as removing specific values from an array, moving zeros to the end, and removing duplicates while allowing at most two occurrences.
Official Java Documentation
For more information about Java arrays and the APIs used in this tutorial, refer to the following official Oracle documentation:
- Java Language Specification: Arrays — Explains array creation, indexing, and fixed array length.
- Java Arrays Class — Documentation for Arrays.toString(), Arrays.copyOf(), and other array utility methods.
- Java Objects Class — Documentation for Objects.requireNonNull().
- Java HashSet Class — Useful for tracking distinct values when working with unsorted arrays.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment