Sort the Array and move all the repeated Elements to End

Question

I have encountered this question in my recent interview.

An array is given, I need to sort the array and all the duplicate elements should be at the end.

Example: input: {7,4,2,3,3,5,3,11,9,2}

Since 2 & 3 are repeated elements they should occur at the end of Array.

Output: {4,5,7,9,11,2,2,3,3,3}

I am free to use any other data structure. No constraints.

Answer 1

CREATE_ARRAY repeated, unique
SORT inputArray
ADD MINIMAL_POSSIBLE_VALUE TO inputArray
TRAVERSE inputArray i=index (from 2nd element to last):
   IF inputArray[i-1] == inputArray[i]:
      2X: ADD inputArray[i] TO repeated
      i++
      WHILE i < LENGTH(inputArray) - 1 and inputArray[i-1] == inputArray[i]:
         ADD inputArray[i] TO repeated
         i++
   ELSE:   
      ADD inputArray[i-1] TO unique
PRINT MERGED(unique, repeated)

You will be sorting your array so duplicate values form patches. You will then distribute the array to unique values array and repeated values array and print them both.

The third line ADD MINIMAL_POSSIBLE_VALUE TO inputArray just adds a dummy element to the array that will never get printed but saves you some IF statements.

// algorithm
function algorithm(input) {
  input.sort(function(a, b) { return a - b });
  input.push(Number.MIN_VAL);
  var repeated = [], unique = [];
  for (var i = 1; i < input.length; i++) {
    if (input[i - 1] == input[i]) {
      repeated.push(input[i], input[i]);
      i++;
      while (i < input.length - 1 && input[i - 1] == input[i]) {
        repeated.push(input[i]);
        i++;
      }
    } else {
      unique.push(input[i - 1]);
    }
  }
  return unique.concat(repeated);
}

// driver
inputBox = document.getElementById('input-box');
outputBox = document.getElementById("output-box");
inputBox.addEventListener("keyup", function() {
  outputBox.innerHTML = algorithm(inputBox.value.split(/[\s,]+/).map(Number));
});

<input id="input-box">
<div id="output-box"></div>

Answer 2

I will use Swift 3 (beta 3) to describe an high level implementation for your problem.

let list = [7,4,2,3,3,5,3,11,9,2]
let countedSet = NSCountedSet(array: list)
let singles = list.filter { countedSet.count(for: $0) == 1 }
let duplicates = list.filter { countedSet.count(for: $0) > 1 }
let res = singles.sorted() + duplicates.sorted()

Line #2

This class creates an index, it associate to each value it number of occurrencies.

Lines #3 and #4

Here I am filtering the original array. I am putting into singles the values with only 1 occurrences and into duplicates the values that appear more then once.

Line #5

Finally I sort singles and duplicates and I concatenate them

Answer 3

Solution using a map data structure, not a very efficient solution but it works nonetheless:

1> Traverse through the vector counting frequency of numbers in a map
2> Iterate over the map (elements will be in sorted order) pushing unique elements in a vector and repeated elements in another vector
3> Push repeated elements in the sorted array

Code in C++

vector<int> sortUnique(const vector<int> & nums) {

// Step 1
map<int, int> numFreq;
for (auto it : nums) {
    if (numFreq.count(it) == 0) {
        numFreq[it] = 1;
    }
    else {
        numFreq[it]++;
    }
}

// Step 2
vector<int> sorted;
sorted.reserve(nums.size());
vector<int> repeated;
repeated.reserve(nums.size());
for (auto it : numFreq) {
    if (it.second == 1) {
        sorted.push_back(it.first);
    }
    else {
        for (int i = 0; i < it.second; i++) {
            repeated.push_back(it.first);
        }
    }
}
// Push repeated elements at the end
for (auto it : repeated) {
    sorted.push_back(it);
}
return sorted;
}

Answer 4

Solution with C# using the sort method of List

        static void Main(string[] args)
    {
        List<int> list = new List<int> { 7, 4, 2, 3, 3, 5, 3, 11, 9, 2, 5 };

        List<int> tmp = new List<int> { };
        List<int> rep = new List<int> {};

        //sorting the list
        list.Sort();

        for (var i = 0; i < list.Count(); i++) 
        {
            int cantidad = list.LastIndexOf(list[i]) - list.IndexOf(list[i]);
            if ( cantidad != 0)
            {
                //found repetitions
                rep.AddRange(list.GetRange(list.IndexOf(list[i]), cantidad + 1));
                i += cantidad;
            }
            else tmp.Add(list[i]);
        }
        tmp.AddRange(rep);

        foreach (int data in tmp)
            Console.WriteLine(data);

        Console.ReadLine();
    }

Solution with C# sorting out manually

        static void Main(string[] args)
    {
        List<int> list = new List<int> { 7, 4, 2, 3, 3, 5, 3, 11, 9, 2 };

        List<int> tmp = new List<int> {};
        List<int> rep = new List<int> {};

        foreach (int data in list)
        {
            if (tmp.Count() > 0)
            {
                int posicion = -1;
                bool bandera = false;
                for (var i=0; i < tmp.Count(); i++)
                {
                    //searching a repetition
                    if (tmp[i] == data)
                    {
                        tmp.RemoveAt(i);
                        //adding to the repeated list at the end or in a determined position
                        for (var j = 0; j < rep.Count(); i++)
                        {
                            if (rep[j] > data)
                            {
                                bandera = true;
                                rep.Insert(j, data); //the one that was deleted
                                rep.Insert(j, data); //the one at the original list
                                break;
                            }
                        }
                        if (!bandera)
                        {
                            bandera = true;
                            rep.Add(data); //the one that was deleted
                            rep.Add(data); //the one at the original list
                        }
                        break;
                    }
                    //saving the position to be inserted
                    if (tmp[i] > data)
                    {
                        posicion = i;
                        break;
                    }
                }
                //was not a repetition
                if (!bandera)
                {
                    bool banderaRep = false;
                    //searching in the repeated list
                    for (var i = 0; i < rep.Count(); i++)
                    {
                        if (rep[i] == data)
                        {
                            banderaRep = true;
                            rep.Insert(i, data);
                            break;
                        }
                    }
                    //was not in the repeated list
                    if (!banderaRep)
                    {
                        if (posicion == -1)
                            tmp.Add(data);
                        else
                            tmp.Insert(posicion, data);
                    }
                }
            }
            else
                tmp.Add(data);
        }
        //join
        tmp.AddRange(rep);

        foreach (int data in tmp)
            Console.WriteLine(data);

        Console.ReadLine();
    }