Remove Duplicates from Sorted Array Two Pointer in DSA Java - Build from Scratch

Remove Duplicates from Sorted Array Using Two Pointers

📖 Scenario: You have a sorted list of numbers representing daily temperatures recorded over several days. Some temperatures repeat because the weather was the same on consecutive days. You want to clean this list by removing extra repeated temperatures, but you want to keep at most two occurrences of the same temperature to keep some record of repetition.

🎯 Goal: Build a Java program that removes extra duplicates from a sorted array of integers, allowing at most two occurrences of each number. Use the two-pointer technique to do this efficiently.

📋 What You'll Learn

Create an integer array called temperatures with the exact values: {10, 10, 10, 12, 12, 15, 15, 15, 15, 20}

Create an integer variable called maxAllowed and set it to 2

Use two pointers named writeIndex and readIndex to iterate and modify the temperatures array to remove extra duplicates beyond maxAllowed

Print the modified temperatures array up to the new length after removing extra duplicates

💡 Why This Matters

🌍 Real World

Cleaning and compressing sorted data lists to reduce storage or improve processing speed, such as temperature logs or sensor readings.

💼 Career

This technique is useful for software engineers working with data processing, optimization, and memory management.

1

Create the sorted array of temperatures

Create an integer array called temperatures with these exact values: {10, 10, 10, 12, 12, 15, 15, 15, 15, 20}

DSA Java

// Create the temperatures array with given values
// Your code here

Hint

Use int[] temperatures = { ... }; to create the array with the exact numbers.

2

Set the maximum allowed duplicates

Create an integer variable called maxAllowed and set it to 2

DSA Java

int[] temperatures = {10, 10, 10, 12, 12, 15, 15, 15, 15, 20};
// Create maxAllowed variable and set it to 2
// Your code here

Hint

Use int maxAllowed = 2; to set the limit for duplicates.

3

Use two pointers to remove extra duplicates

Use two integer pointers called writeIndex and readIndex to iterate over temperatures and keep at most maxAllowed duplicates. Update temperatures in place to remove extra duplicates.

DSA Java

int[] temperatures = {10, 10, 10, 12, 12, 15, 15, 15, 15, 20};
int maxAllowed = 2;
// Use two pointers to remove extra duplicates
// Your code here

Hint

Use a for loop with readIndex and a writeIndex to overwrite extra duplicates. Check if the current number is allowed by comparing with the number maxAllowed positions before.

4

Print the cleaned temperatures array

Print the elements of temperatures from index 0 to writeIndex - 1 separated by spaces on one line.

DSA Java

int[] temperatures = {10, 10, 10, 12, 12, 15, 15, 15, 15, 20};
int maxAllowed = 2;

int writeIndex = 0;
for (int readIndex = 0; readIndex < temperatures.length; readIndex++) {
    if (writeIndex < maxAllowed || temperatures[readIndex] != temperatures[writeIndex - maxAllowed]) {
        temperatures[writeIndex] = temperatures[readIndex];
        writeIndex++;
    }
}
// Print the cleaned temperatures array
// Your code here

Hint

Use a for loop from 0 to writeIndex - 1 and print each element followed by a space.

Practice

1. What is the main purpose of using two pointers in the Remove Duplicates from Sorted Array problem?

easy

A. To sort the array before removing duplicates

B. To count the total number of duplicates in the array

C. To create a new array with unique elements

D. To efficiently track unique elements and overwrite duplicates in-place

Solution

1. Step 1: Understand the two-pointer approach

   One pointer tracks the position to place the next unique element, the other scans the array.

2. Step 2: Purpose of pointers in-place

   This method avoids extra space by overwriting duplicates, keeping unique elements at the start.

3. Final Answer:

   To efficiently track unique elements and overwrite duplicates in-place -> Option D

4. Quick Check:

   Two pointers help remove duplicates without extra space [OK]

Hint: Two pointers move to keep unique elements compact [OK]

Common Mistakes:

• Thinking two pointers sort the array
• Assuming a new array is created
• Confusing counting duplicates with removing them

2. Which of the following is the correct syntax to initialize the two pointers i and j for the problem in Java?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

C. int i = 0; int j = 0;

D. int i = 1; int j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i starts at 0 to track unique elements, j starts at 1 to scan ahead.

2. Step 2: Check initialization correctness

   Initializing i = 0 and j = 1 allows scanning from second element while i marks last unique.

3. Final Answer:

   int i = 0, j = 1; -> Option A

4. Quick Check:

   Start i at 0, j at 1 to scan array [OK]

Hint: Start i at 0 and j at 1 to compare neighbors [OK]

Common Mistakes:

• Starting both pointers at 0
• Swapping i and j initialization
• Starting both pointers at 1

3. What will be the output length after removing duplicates using two pointers on the sorted array [1, 1, 2, 2, 3]?

medium

A. 2

B. 3

C. 5

D. 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1; compare elements and overwrite duplicates: unique elements are 1, 2, 3.

2. Step 2: Count unique elements

   After processing, unique elements count is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Unique elements count = 3 [OK]

Hint: Count unique elements after skipping duplicates [OK]

Common Mistakes:

• Counting duplicates instead of unique
• Assuming length stays same
• Miscounting when duplicates are consecutive

4. Identify the error in the following Java code snippet for removing duplicates from a sorted array:

int i = 0, j = 1;
while (j < nums.length) {
  if (nums[i] != nums[j]) {
    i++;
    nums[i] = nums[j];
  }
  j++;
}
return i;

medium

A. Pointers initialized incorrectly

B. Incorrect comparison operator used

C. Returns i instead of i + 1 as new length

D. Does not increment j inside the loop

Solution

1. Step 1: Analyze return value

   The variable i tracks last unique index, so length is i + 1.

2. Step 2: Identify mistake in return

   Returning i misses counting the first element, causing length off by one.

3. Final Answer:

   Returns i instead of i + 1 as new length -> Option C

4. Quick Check:

   Length = last index + 1 [OK]

Hint: Return i + 1 for length, not i [OK]

Common Mistakes:

• Returning i instead of i + 1
• Forgetting to increment j
• Using wrong comparison operator

5. Given a sorted array nums = [0,0,1,1,1,2,2,3,3,4], what will be the array state after applying the two-pointer method to remove duplicates?

hard

A. [0, 1, 2, 3, 4, _, _, _, _, _]

B. [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

C. [0, 1, 1, 2, 3, 4, _, _, _, _]

D. [0, 1, 2, 3, 4, 5, _, _, _, _]

Solution

1. Step 1: Apply two-pointer overwrite

   Start with i=0, j=1; overwrite duplicates by moving unique elements forward: unique elements are 0,1,2,3,4.

2. Step 2: Final array state

   First five positions hold unique elements [0,1,2,3,4], rest remain unchanged or ignored.

3. Final Answer:

   [0, 1, 2, 3, 4, _, _, _, _, _] -> Option A

4. Quick Check:

   Unique elements compacted at start [OK]

Hint: Unique elements fill front, duplicates ignored after [OK]

Common Mistakes:

• Assuming duplicates remain in place
• Misplacing unique elements
• Counting extra elements beyond unique count