JS delete duplicated items from array without higher order functions

Question

I know it's a stupid question, but I only learning programming 3 months now.

How would you solve this problem, if you can't use higher order functions and built-in methods, like filter or indexOf?

Create a function that takes a list of numbers and returns a new list where all the duplicate values are removed

I got this so far, but I think It's a dead end...

const array = [1, 2, 3, 3, 1];

const removeDuplicate = () => {
    let shortArray = [];
    let index = 0;
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length; j++) {
            if (i != j) {
                if (array[i] == array[j]) {
                    shortArray[index] += array[i]
                    console.log(array[i]);
                }
            }
        }
    }
    return shortArray;
}

console.log(removeDuplicate());

return this:

1
3
3
1
[ NaN ]

thanks!

That's inefficient - O(n^2). For O(n) runtime, hash each unique value, and store the hashes. — frozen, Jul 09 '17 at 18:26
`new Set(array).values()` - done. Or even better: `[...new Set(array)]` — Fuzzyma, Jul 09 '17 at 18:34
If you're using [lodash](https://lodash.com), you can use `_.compact`. — Marko Gresak, Jul 09 '17 at 18:35
Possible duplicate of [Remove Duplicates from JavaScript Array](https://stackoverflow.com/questions/9229645/remove-duplicates-from-javascript-array) — Marko Gresak, Jul 09 '17 at 18:35

Ori Drori · Accepted Answer · 2017-07-09T18:55:26.903

6

Use an object as a helper. If a value appears in the helper, it's not unique and can be ignored. If it's not in the helper it's unique, push it into the result array, and add it to the helper object.

const array = [1, 2, 3, 3, 1];

const removeDuplicate = (arr) => {
  const helperMap = {};
  const result = [];

  for (let i = 0; i < arr.length; i++) {
    const item = arr[i];

    if (!helperMap[item]) {
      result[result.length] = item;

      helperMap[item] = true;
    }
  }

  return result;
};

console.log(removeDuplicate(array));

edited Jul 09 '17 at 18:55

answered Jul 09 '17 at 18:29

Ori Drori

183,571
29
224
209

Thanks, this worked for me. I only changed the push method – Zsolt Makrai Jul 09 '17 at 18:51
@ZsoltMakrai - what have you changed it to? – Ori Drori Jul 09 '17 at 18:52
I introduced a new variable, index and than: result[index] = item; index++ – Zsolt Makrai Jul 09 '17 at 18:53
@ZsoltMakrai - you don't need another variable, if you want to avoid push. You can use `result[result.length] = item` instead. I've updated the answer. – Ori Drori Jul 09 '17 at 18:56

score 1 · Answer 2 · answered Jul 09 '17 at 18:34

1

function unique(arr) {
  var obj = {};

  for (var i = 0; i < arr.length; i++) {
    var value = arr[i];
    obj[value] = true; // set as key
  }

  return Object.keys(obj); //return all keys
}

answered Jul 09 '17 at 18:34

rossoneri

443
5
17

That's nice, but it doesn't preserve the order of the original array. – Mark Jul 09 '17 at 18:38
@MarkM yeah, agree, depends on requirements – rossoneri Jul 09 '17 at 18:39
this doesn't satisfy the question, as Object.keys is a higher order function. – thejohnbackes Jul 09 '17 at 18:41
2

@thejohnbackes Aren't higher order functions defined as either taking a function as an argument or returning a function (or both). Object.keys takes an object and returns an array. Why is it a higher-order function? – Mark Jul 09 '17 at 18:48
Mark, you're right. Sorry, I was thinking of avoiding using built-in methods, not higher-order functions. But that was also part of the original request. I should have said, "this doesn't satisfy the question, as Object.keys is a built-in function." – thejohnbackes Jul 09 '17 at 22:03

rishikesh tadaka · Answer 3 · 2017-07-09T18:44:49.880

0

Use below function:

    function RemoveDuplicate(array){
    let shortArray = [];
    let index = 0;
    for (let i = 0; i < array.length; i++) {
        let exist=false;
        for(let j=0;j<shortArray.length;j++){
            if(array[i]==shortArray[j]){
                exist=true;
                break;
            }

        }
        if(!exist){
            shortArray[shortArray.length]=array[i];
        }
    }
    return shortArray;
}

edited Jul 09 '17 at 18:44

answered Jul 09 '17 at 18:37

rishikesh tadaka

483
1
6
18

this function is stateful: array should be passed in as a parameter. The complexity is O(n^2). Use shortArray.push(array[i]) instead of what you're doing. Also, remove debugger from your code. – thejohnbackes Jul 09 '17 at 18:42
the nested loop still creates unnecessary computational complexity. Imagine a very very long array, you will have to loop through the entire array at every level. That means if you have 1,000,000 elements, eventually you are looping through 1,000,000 elements every time you advance the index (in the worst case scenario). That is why you should consider using a hash table (which has a constant lookup time), rather than looping through shortArray. – thejohnbackes Jul 09 '17 at 22:00

JS delete duplicated items from array without higher order functions

3 Answers3