DEV Community

Daily Challenge #273 - Remove Duplicates

dev.to staff on July 27, 2020

In this challenge, you will remove the left-most duplicates from a list of integers and return the result. // Remove the 3's at indices 0 and 3 /...

Read full post

Deepak Raj • Jul 27 '20 • Edited

This solution is in python

def Remove(duplicate): 
    final_list = [] 
    for num in duplicate: 
        if num not in final_list: 
            final_list.append(num) 
    return final_list

print(Remove([3, 4, 4, 3, 6, 3]))

output

[3, 4, 6]

Rafael Acioly • Jul 27 '20

Hi, you could have use the set method, like this:

dev.to/rafaacioly/comment/12l2j

Grégoire Welraeds • Jul 28 '20

is
[3, 4, 6]
not
[4, 6, 3]
which is the expected answer

Rohit Prasad • Aug 6 '20

Fixed it

def Remove(duplicate):
    final = []

    for i in range(len(duplicate)):
        if duplicate[i] not in duplicate[i+1:]:
            final.append(duplicate[i])

    return final

x = input("Enter the integers: ")
x = x.split()

print(Remove(x))

Nathan Kallman • Jul 27 '20 • Edited

Javascript in O(n) (more specifically 3n, looping three times on the length of the input, two identical reduce es and one filter):

const identity = (i) => i || i === 0;
const radixPush = (array, radix, value) => {
  array[radix] = value;
  return array;
};

const solve = (array) => array.reduce(radixPush, []).reduce(radixPush, []).filter(identity);

Mihail Malo • Jul 28 '20 • Edited

Epic, but also this relies on the array being sparse in the first reduce (so, a map really), since new Array(Number.MAX_SAFE_INTEGER) is an error.

I'd express that as

const solve = arr => {
  const vals = new Map(function * () {for (let i=0; i < arr.length; i++) yield [arr[i], i]} ())
  const out = new Array(arr.length)
  for (const [v, i] of vals) out[i] = v
  return out.filter(x => typeof x !== "undefined")
}

which is just a funny version of

const solve = arr => {
  const vals = new Map() // tfw no Map::with_capacity
  for (let i=0; i < arr.length; i++) vals.set(arr[i], i)
  const out = new Array(arr.length)
  for (const [v, i] of vals) out[i] = v
  return out.filter(x => typeof x !== "undefined")
}

Amin • Jul 27 '20

Haskell

module Main where


deduplicate :: [Int] -> [Int]
deduplicate [] = []
deduplicate (x:xs)
    | elem x xs = deduplicate xs
    | otherwise = x : deduplicate xs


main :: IO ()
main = do
    print $ deduplicate [3, 4, 4, 3, 6, 3]      -- [4, 6, 3]
    print $ deduplicate [3, 4, 4, 3, 6, 3]      -- [4, 6, 3]
    print $ deduplicate [1, 2, 1, 2, 1, 2, 3]   -- [1, 2, 3]
    print $ deduplicate [1, 1, 4, 5, 1, 2, 1]   -- [4, 5, 2, 1]
    print $ deduplicate [1, 2, 1, 2, 1, 1, 3]   -- [2, 1, 3]

Test

Valts Liepiņš • Jul 28 '20 • Edited

Wouldn't this have O(n^2) time complexity? This could be done in O(n), using a IntMap.

EDIT:

This is my attempt at writing a similar function but with O(n) time complexity (O(n*m) when m <= 64, where m is amount of elements in IntSet):

import Data.Foldable (foldl')
import Data.IntSet   (empty, insert, notMember)

deduplicate :: [Int] -> [Int]
deduplicate = fst . foldl' takeUniq ([], empty) . reverse
  where
    takeUniq (xs, set) x
      | notMember x set = (x:xs, insert x set)
      | otherwise       = (xs, set)

Amin • Jul 28 '20 • Edited

Hi and thanks for your reply. This looks like a very good solution.

Wouldn't this have O(n^2) time complexity?

Indeed this algorithm would have an O(n²) time complexity if the xs list would remain the same. I believe the time complexity is O(n log n) since we are decreasing the xs list each time in the solution I proposed. But I'm bad at time complexity so I wouldn't know.

I didn't know about Data.IntSet I'll look into that. Thanks for sharing.

Akash Kava • Jul 29 '20

You are forgetting OLog(n) steps used by IntMap internally, it is never O(n),

Valts Liepiņš • Jul 29 '20

Perhaps you're mistaking IntMap for Map?

Here, in Map documentation most lookup and insertion operations are indeed O(log n):
hackage.haskell.org/package/contai...

But in IntMap documentation, you can see that the actual complexity is O(min(n, W)), where W is size of integer type (32 or 64):
hackage.haskell.org/package/contai...

This effectively means that after IntMap contains more than 64 elements, the time complexity is constant O(W) or O(1).

Akash Kava • Jul 29 '20

Interesting .. I wasn't aware of that.

Sourabh Choure • Jul 27 '20

In C with O(n²):

#include <stdio.h>

int solve(int* nums,int* newnums, int numsSize){
    if(numsSize==0){
        return 0;
    }

    int count = 0;

    for(int i=0;i<numsSize;i++){
        int flag = 0;
        for(int j=0;j<count;j++){
            if(nums[i]==newnums[j]){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            newnums[count++] = nums[i];
        }
    }

    return count;
}

int main(void)
{
    int ar[] = {1,2,1,2,1,1,3};
    int n = sizeof(ar)/sizeof(ar[0]);
    int newar[n];
    int len = solve(ar,newar,n);

    for(int i=0;i<len;i++){
        printf("%d ",newar[i]);
    }
    printf("\n");
    return 0;
}

Lautaro Lobo • Jul 29 '20

Cool!

Sourabh Choure • Jul 29 '20

Thanks, I am new to Programming.

Vishal Kathiriya • Jul 27 '20

In JavaScript (ES6)

const originalArray = [3,4,4,3,6,3]; const distinctArray = [...new Set(originalArray)];

Mihail Malo • Jul 28 '20

Nope

JP Antunes • Jul 28 '20 • Edited

Simple JS O(n) solution (I think... 2n?) that will remove the left-most duplicates from a list of integers and return the result in the right order.

const solve  = arr => {
    let seen = [];
    for (let i = arr.length - 1;  i > 0; i--) {
        seen.includes(arr[i]) ? _ : seen.unshift(arr[i])
    }
    return seen;
}

Vinay Pai • Jul 28 '20

This is not O(n) because you're iterating over "seen" at every iteration of your for loop, so it's O(n^2) except in the degenerate case where all the elements are duplicates. Also, it isn't specified but unshift itself is also most likely an O(n) operation in most implementations.

JP Antunes • Jul 29 '20 • Edited

I had my doubts, but it seems the JS implementation uses a linear search algorithm.

FWIW, I also had to check if Sets keep insertion ordering since in principle they shouldn't... but in JS they do!

Vinay Pai • Jul 29 '20

Good to know, I didn't know that was actual documented behavior of the Set.

open • Jul 27 '20


function solve(list) {
  return list.filter((a, b) => array.indexOf(a) == b)
};

Vinay Pai • Jul 28 '20

Here's my python solution O(n). The idea is to iterate over the input and keep track of the index of the last time you saw a given number. If you see a number, replace the old value with None, and do a second pass at the end to remove all the Nones.

The two-phase approach is necessary to keep it O(n). If we remove items as we find them it could end up costing O(n^2).

def solve(arr):
    last_seen = {}
    res = []

    for val in arr:
        if val in last_seen:
            res[last_seen[val]] = None
        last_seen[val] = len(res)
        res.append(val)

    return list(v for v in res if v is not None)

Mihail Malo • Jul 28 '20 • Edited

javascript

const solve = arr => {
  const vals = new Map()
  for (let i=0; i < arr.length; i++) vals.set(arr[i], i)
  const sparse = new Array(arr.length)
  for (const [v, i] of vals) sparse[i] = v
  const out = new Array(vals.length)
  let o = 0;
  for (const i in sparse) out[o++] = sparse[i]
  return out
}

The question remains, does the for in kill the man what if it sorts lexically and not numerically? Should I have just for (const x of sparse) if (typeof x !== "undefined") out[o++] = x?

Maybe

function * isDef(it) {
  for (const x of it) if (typeof x !== "undefined") yield x
}
const solve = arr => {
  const vals = new Map() // tfw no Map::with_capacity
  for (let i=0; i < arr.length; i++) vals.set(arr[i], i)
  const sparse = new Array(arr.length)
  for (const [v, i] of vals) sparse[i] = v
  const out = new Array(vals.length)
  const search = isDef(sparse)
  for (let i = 0; i < vals.length; i++) out[i++] = search.next()
  return out
}

ayy lmao

peter279k • Jul 28 '20

Here is the simple solution with PHP:

function solve($arr) {
  $ansArr = [];

  $index = count($arr)-1;
  for(; $index >= 0; $index--) {
    if (in_array($arr[$index], $ansArr) == false) {
      $ansArr[] = $arr[$index];
    }
  }

  return array_reverse($ansArr);
}

bb4L • Jul 27 '20

Nim:

import sequtils, algorithm

proc solve*(data: seq[int]): seq[int] =
    return data.reversed().deduplicate().reversed()

Karthick Devaraj • Jul 27 '20 • Edited

Here Goes, My Solution

Mihail Malo • Jul 28 '20

(a => [...new Set(a)])([3, 4, 4, 3, 6, 3])

is
[3, 4, 6]
not
[4, 6, 3]

To get the correct result you'd have to do

[...new Set(a.reverse())].reverse()

which is... quite a lot.

Grégoire Welraeds • Jul 28 '20

pprint(solved)
set([3, 4, 6])
is not
[4,6,3]
which is the expected answer (you only keep the last occurrence of each duplicates, not the first)

Rafael Acioly • Jul 27 '20

Python 🐍

from typing import List

def solve(nums: List[int]): List[int]:
    return list(set(nums))