DEV Community

Cover image for Daily Challenge #273 - Remove Duplicates
dev.to staff
dev.to staff

Posted on

Daily Challenge #273 - Remove Duplicates

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
// followed by removing a 4 at index 1
solve([3, 4, 4, 3, 6, 3]); // => [4, 6, 3]

Tests:
solve([3,4,4,3,6,3])
solve([1,2,1,2,1,2,3])
solve([1,1,4,5,1,2,1])
solve([1,2,1,2,1,1,3])

Good luck!


This challenge comes from KenKemau on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (33)

Collapse
 
codeperfectplus profile image
Deepak Raj • 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]
Collapse
 
rafaacioly profile image
Rafael Acioly

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

dev.to/rafaacioly/comment/12l2j

:)

Collapse
 
gwelr profile image
Grégoire Welraeds

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

Collapse
 
maskedman99 profile image
Rohit Prasad

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))

Collapse
 
kallmanation profile image
Nathan Kallman • 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);
Collapse
 
qm3ster profile image
Mihail Malo • 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")
}
Collapse
 
aminnairi profile image
Amin

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

Collapse
 
cipharius profile image
Valts Liepiņš • 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)
Collapse
 
aminnairi profile image
Amin • 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.

Collapse
 
akashkava profile image
Akash Kava

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

Thread Thread
 
cipharius profile image
Valts Liepiņš

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).

Thread Thread
 
akashkava profile image
Akash Kava

Interesting .. I wasn't aware of that.

Collapse
 
saviourcode profile image
Sourabh Choure

In C with O(n2):

#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;
}
Collapse
 
lautarolobo profile image
Lautaro Lobo

Cool!

Collapse
 
saviourcode profile image
Sourabh Choure

Thanks, I am new to Programming.

Collapse
 
vishaalkathiriya profile image
Vishal Kathiriya

In JavaScript (ES6)

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

Collapse
 
qm3ster profile image
Mihail Malo
Collapse
 
jpantunes profile image
JP Antunes • 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;
}
Collapse
 
vinaypai profile image
Vinay Pai

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.

Collapse
 
jpantunes profile image
JP Antunes • 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!

Thread Thread
 
vinaypai profile image
Vinay Pai

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

Collapse
 
mosfa profile image
open

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

Collapse
 
vinaypai profile image
Vinay Pai

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)
Collapse
 
qm3ster profile image
Mihail Malo • 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

Collapse
 
peter279k profile image
peter279k

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);
}
Collapse
 
bb4l profile image
bb4L

Nim:

import sequtils, algorithm

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

Collapse
 
im_dkarthe profile image
Karthick Devaraj • Edited

Here Goes, My Solution

Collapse
 
qm3ster profile image
Mihail Malo
(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.

Collapse
 
gwelr profile image
Grégoire Welraeds

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)

Collapse
 
rafaacioly profile image
Rafael Acioly

Python 🐍

from typing import List

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