remove duplicates and sort an array with single loop in javascript

Question

I want to write an algorithm to remove duplicates and sort an array with single loop in javascript. I want to do it with algorithms not declarative methods. I can sort it with single loop but can't remove duplicates. I will be glad if someone help me.

Number of elements in array is 10^6, each element is equal to or greater than 0, less than 300

This is my sorting algorithm:

var a = [2, 7, 5, 1, 3, 2, 7];

for (let i = 0; i < a.length - 1; i++) {
  if (a[i] > a[i + 1]) {
    let temp = a[i]
    a[i] = a[i + 1]
    a[i + 1] = temp
    i = -1
  }
}

console.log(a)

`const output = Array.from(new Set(input)).sort((a,b) => a - b)` — mplungjan, Jan 05 '22 at 12:20
@mplungjan I want to do it with algorithms not declarative methods. — , Jan 05 '22 at 12:26
@TylerDurden number of elements is 10^6, each element is equal to or greater than 0, less than 300 — , Jan 05 '22 at 12:31
Since the number of keys is limited to 300, you can create a simple array (hash) of length 301 -> iterate over original array and increment the count for each element -> iterate over the hash and if count is greater than 1, then insert the element into result array. It will amount to 2 loops, but the time complexity remains `O(n) + O(300) i.e. O(n)` — Tyler Durden, Jan 05 '22 at 12:39
@TylerDurden this was interview question and asked me to do it with just 1 loop. i wonder if there a way to do it — , Jan 05 '22 at 12:51
@lukas You can write any algorithm with a single loop by putting a state machine inside that loop. Doesn't make it good code though. Or just write it without a "loop" altogether but use recursion! The interview task just doesn't make sense. Ignore the requirements and *discuss* the possible solutions with the interviewer, that's what they really care about. — Bergi, Jan 05 '22 at 13:07

Rickard Elimää · Accepted Answer · 2022-01-07T06:15:13.003

It's honorable that you was curious enough to try to find a solution, even after the interview. A good sign for a programmer.

I would use an object to keep track of any duplicates.
Also loop from the end, mostly because it feels right, not messing up the index.
Change position in a if current < previous
Else add to the object.
Check if object has previous index, or
Check if current is the same as previous (ex. 8, 8 at the end of the array)
then splice the previous index.
Added numberOfLoops just because it's fun to know.

var a = [2, 2, -1, 8, 5, 1, 3, 3, 13, 2, 8, 8];
var temp = {};  // 1
var result = [];
var current, previous;
var numberOfLoops = 0;

for (let i = a.length - 1; i > 0 ; i--) {  // 2
  current = a[i];
  previous = a[i - 1];
  numberOfLoops++;  // 8

  if (temp.hasOwnProperty(previous) ||   // 5
      current == previous) {             // 6
    a.splice(i - 1, 1);                  // 7
    // i++;
  } else if (current < previous) {  // 3
    a[i - 1] = current;
    a[i] = previous;
    i += 2;
    delete temp[current];
  } else {                          // 4
    temp[current] = current;
  }
}

console.log({numberOfLoops});  // 23
console.log(a);  // [-1, 1, 2, 3, 5, 8, 13]

remove duplicates and sort an array with single loop in javascript

1 Answers1