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 [e-mail] with your suggestions!

Comments

[open]

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

[Deepak Raj]

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]

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

dev.to/rafaacioly/comment/12l2j

:)

[bb4L]

Nim:

import sequtils, algorithm

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

[Sourabh Choure]

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]

Cool!

[Sourabh Choure]

Thanks, I am new to Programming.

[Vishal Kathiriya]

In JavaScript (ES6)

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

[Mihail Malo]

Nope

[Karthick Devaraj]

Here Goes, My Solution

[Nathan Kallman]

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]

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

[Rafael Acioly]

Python 🐍

from typing import List

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

[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

[Valts Liepiņš]

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]

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]

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

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

[Akash Kava]

Interesting .. I wasn't aware of that.

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