0

I've recently started going through some of Codility coding tests and so far I'am getting 0% on my code performace almost every time.

This one https://codility.com/programmers/lessons/6-sorting/distinct/ is very simple code of finding number of distinct integers in an array.

My code is syntactically correct and works properly but what can i do to optimize the performance ?

This is my code:

function solution(A) {


    var res = []
    var len = A.length
    for(var i=len;i--;){
        if(!res.includes(A[i])){
            res.push(A[i])
            }
        }
        return res.length
}

The performance errors i'm getting from codility

M.C
  • 90
  • 7

2 Answers2

2

Thanks to @Slai and @le_m for the additional pointers.

SET: O(n) space complexity and O(n*log(n)) time complexity from a data structure standpoint. But seems like V8 does it in a different way Set insertion comes down to O(1) making the time complexity O(n).

MAP: O(N) space complexity but I think the time complexity will be a little lesser compared to others and could be O(N) because each key look up takes O(1)

More on Javascript collection complexities

Javascript ES6 computational/time complexity of collections

es6 Map and Set complexity, v8 implementation

// USING ES6 SET

// ONE LINER
// console.log((new Set(arr)).length)

// BREAKDOWN
const arr = [1, 2, 3, 2, 1, 4, 1];

var setArr = new Set();

arr.forEach(number => setArr.add(number))

console.log([...setArr])

// USING ES6 MAP
let map = new Map();

arr.forEach(number => map.set(number, "PRESENT"))

console.log([...map.keys()])
Nandu Kalidindi
  • 6,075
  • 1
  • 23
  • 36
  • Oh I see, it's only to get the number of elements. That's a great one liner. Let me add that to the snippet. – Nandu Kalidindi Dec 03 '17 at 01:51
  • thanks very much @Nandu Kalidindi , Although i had to return the size but your code is perfect. thx again – M.C Dec 03 '17 at 01:52
  • Each insertion of element into a Set takes O(log(N)) so, N element insertion takes O(N*log(N)). Again please confirm it by looking at how Set works by yourself. – Nandu Kalidindi Dec 03 '17 at 01:55
  • @le_m I was wondering the same but seems like the spec doesn't require the implementation to be O(1) add/remove/has https://stackoverflow.com/questions/31091772/javascript-es6-computational-time-complexity-of-collections. @NanduKalidindi I guess you haven't seen the `[...new Set(arr)]` https://stackoverflow.com/a/33121880/1383168 – Slai Dec 03 '17 at 01:59
  • AFAIK both Set and Map are in O(1) amortized time complexity for insertion - e.g. for V8 see see https://stackoverflow.com/questions/33611509/es6-map-and-set-complexity-v8-implementation - the spec doesn't require this though. – le_m Dec 03 '17 at 02:00
  • 1
    @Slai Yeah, I do, I just added that to give a breakdown of the answer, one liners are not that self explanatory. Sorry, I added the NlogN from a usual C data structure point of view. If V8 implements it internally using a Map then it will be O(1). Please add as many findings to the answer. Thank you. – Nandu Kalidindi Dec 03 '17 at 02:04
0

The time complexity of your code is O(n^2) You have an outer for loop O(n) and you are using includes method which transverse the array O(n) times

you can simply do this

function unique(A) {
   let newSet = new Set(A)
    return newSet.size
}

time complexity: O(N*log(N)) or O(N)

Johnson Chinonso
  • 347
  • 2
  • 4