1

I want to count the unique values in a given array without altering the original array but the solution has to be within the time complexity of O(n). so far all of the solutions I've seen, have a time complexity of O(n^2) like here. I can't find the error in my solution's logic. I'm new to Data Structure & Algorithms and would like a simple solution.

MY CODE -

const countUniqueValues = (arr) =>{
    if(arr.length === 0){
        return console.log(arr.length);
    }else if(arr.length === 1){
        return console.log(arr.length);
    }

    const unique = [];
    let i = 0;
    for( let j = 1; j < arr.length; j++){
        if(arr[i] !== arr[j]){
            i ++;
            unique.push(arr[i]);
        }
    }
    return console.log(unique);
}

//test cases
countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4

Wrong Output -

[ 1 ]
[
  2, 3, 4,  4,
  4, 7, 7, 12
]
0
[ -1, -1, 0 ]
Arka
  • 957
  • 1
  • 8
  • 18

3 Answers3

5

Turn the array into a Set (O(n)) and count the set's size:

const countUniqueValues = arr => new Set(arr).size;
CertainPerformance
  • 356,069
  • 52
  • 309
  • 320
  • your solution though right, It will not be useful for me for interview purposes. but thanks for showing me a short solution. – Arka Dec 18 '20 at 05:06
  • 2
    If the interviewer rejects this, the shortest and most easily understandable solution, I would not want to work at such a company. Good, professional, maintainable code is **short**, **simple**, and easy to understand at a glance; it's not over-engineered just for the heck of it. – CertainPerformance Dec 18 '20 at 05:14
  • the only thing that "bothers" me about the Set is that the question was for O(n) - if the Array is unsorted the Set will have to iterate through the collection , and that won't be O(n) - so this might seem like the shortest written solution, BUT it uses a more complex algorithm behind the scenes, not making it O(n) - it MIGHT if the Arrays is sorted .. just make sure what the interviewer asks .. –  Dec 18 '20 at 05:15
  • 1
    Iterating through the collection *is* `O(n)`, since there isn't any sorting or nested loops involved - regardless of whether the input array is sorted or unsorted. – CertainPerformance Dec 18 '20 at 05:17
  • @CertainPerformance it depends on the implementation of a set. Most sets have an insertion time complexity of logN, making it NlogN – Abhinav Mathur Dec 18 '20 at 05:18
  • 1
    @AbhinavMathur See [here](https://stackoverflow.com/a/31092145) and [here](https://stackoverflow.com/q/33611509) - `O(1)` can be assumed for a decent implementation. – CertainPerformance Dec 18 '20 at 05:22
  • 1
    @CertainPerformance yes, hashmap based implementations have O(1) performance in most cases. And while your answer is the smart way of doing it, you can't really use it in an interview where they want to test your DSA skills – Abhinav Mathur Dec 18 '20 at 05:27
  • Is that so, @AbhinavMathur? Depending on the scenario, but certainly more often than not, would I pick the candidate that appears to know how to ship stable solutions into production during their first week on the job over the one that would rather argue Big-O with the earlier type candidate than to open a PR and to close and pick up a new ticket. How many low latency hot paths is a junior JS engineer expected to optimize? How many UI widgets of reasonable quality to deliver? I'd rather hire the dev who can consistently do the latter, while avoiding classic `for` loops and the `var` keyword. – Johannes Pille Dec 18 '20 at 05:45
  • @CertainPerformance you're right from your point of view, but most of the indian companies will consider this as cheating and think you don't have the logical capability. as a avg. fresher in a country like india, one doesn't have the luxury of nitpicking over companies. – Arka Dec 18 '20 at 06:35
  • @JohannesPille the candidate selection process is broken in most firms for a reason. They'll test your DSA skills before they inquire about your actual skillset and experience in most cases. – Abhinav Mathur Dec 18 '20 at 06:49
3

NB - very important - the arrays must be sorted for this to work:

This should do the trick:

 var prevValue = "";

const countUniqueValues = (arr) =>{
    if(arr.length === 0){
        return console.log(arr.length);
    }else if(arr.length === 1){
        return console.log(arr.length);
    }
    
    prevValue = arr[0];

    let i = 1;
    for( let j = 1; j < arr.length; ++j){
        if(arr[j] != prevValue){
            ++i;
            prevValue = arr[j];
        }
    }
    console.log(i);
   return i;
}
0
const makeUniqueAndCount = arr => {
  const uniqueKeysObject = {};

  arr.forEach(number => {
    uniqueKeysObject[number] = true;
  });

  return Object.keys(uniqueKeysObject).length;
};

This solution uses objects in javascript. The keys for a javascript object are always unique. You can then use the keys method of the javascript object prototype to turn it into an array to get its length. This solution will work for an unsorted array as well.

Mueez Javaid Hashmi
  • 11
  • 2