Remove Duplicates - Two Pointers / Same Direction

Problems
1

https://algo.monster/problems/remove_duplicates

4

This was a very helpful problem and helps to understand the two pointer system.

5

Explained this way, the problem looks now so easy. Thanks.

6

Why do we return slow + 1

7

Here is a C# solution:

public static int RemoveDuplicates(List arr)
{
int slow = 0;
for (int fast = 0; fast < arr.Count; fast++)
{
if (arr[fast] != arr[slow])
{
slow++;
arr[slow] = arr[fast];
Console.WriteLine(arr[slow]);
}
}
return slow + 1;
}

8

left pointer points to the last unique element. +1 to return the length of array of unique elements.

9

For C# you need to add the following code to the Main function to get the tests to pass,

string result = “”;
for(int i = 0; i< res; i++)
{
result += arr[i].ToString()+" ";
}
Console.WriteLine(result.Trim());

10

LC: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

11

The fast pointer can start from position 1 instead of 0. This will save one less comparison in the for/if loop.

13

C# version needs the output fix

14

Here is the fix offer:
var output = string.Join(" ", new ArraySegment(arr.ToArray(), 0, res));
Console.WriteLine(output);

15

Structured Programming JS Solution:

function removeDuplicates(arr) {
    let rightIndex = arr.length - 1;
    
    for (let leftIndex = arr.length - 2; leftIndex >= 0; leftIndex--) {
        if (arr[leftIndex] === arr[rightIndex]) {
            arr.splice(rightIndex, 1)
        }
        
        rightIndex = leftIndex;
    }
    
    return arr.length;
}
16

C#
using System;
using System.Collections.Generic;
using System.Linq;

class Solution
{
public static int RemoveDuplicates(List arr)
{
int slowPtr = 0;
for (int fastPtr = 0; fastPtr < arr.Count; fastPtr++)
{
if (arr[fastPtr] != arr[slowPtr])
{
slowPtr++;
arr[slowPtr] = arr[fastPtr];
}
}
return slowPtr + 1;
}

public static List<string> SplitWords(string s)
{
  return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
}

public static void Main()
{
    List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
    int res = RemoveDuplicates(arr);
    string result = ""; for(int i = 0; i< res; i++) { result += arr[i].ToString()+" "; } Console.WriteLine(result.Trim());
}

}

17

Your function should modify the list in place

The suggested python solution does not modify the list in place, and therefore would not meet appropriate acceptance criteria.

18

I agree, it’s a misleading question.

19

This is the solution I came up with. It works in my browser, but in the editor here it marked Testcases 1 and 2 wrong.

function removeDuplicates(arr) {
    // WRITE YOUR BRILLIANT CODE HERE
    let left = 0;
    let right = 1;

    while(arr.length -1 >= right) {
    
        if(arr[left] === arr[right]) {
            arr.splice(left, 1)
        } else {
            left++
            right++
        }
    }
    return arr;
}
20

The left pointer starts from the zero index, the same as arrays: the first item starts from the zero index.
The problem asks to return the number of unique items.
That means if the left pointer equals 1, that actually means the number of unique items from 0 to 1 which equals 2.

21

Java Code for Remove Duplicates:

public static int removeDuplicates(int inputArray)
{
int slowPointer =0;
for(int fastPointer =1; fastPointer <inputArray.length; fastPointer ++)
{
if(inputArray[fastPointer ] != inputArray[fastPointer -1])
{
slowPointer ++;
inputArray[slowPointer ]=inputArray[fastPointer];
}
}
return slowPointer +1;