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;
}