CODEWITHSUNDEEP
javascriptalgorithm
Happy Machine
Happy Machine

Reputation: 1163

Codility Leader Algorithm in JavaScript

I am attempting the Codility 'Leader' question in JavaScript.

The question is as follows:

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3    A[1] = 4    A[2] =  3
A[3] = 2    A[4] = 3    A[5] = -1
A[6] = 3    A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in > those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function function solution(A); that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

A[0] = 3    A[1] = 4    A[2] =  3
A[3] = 2    A[4] = 3    A[5] = -1
A[6] = 3    A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000]; and each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

My answer is below:

function solution(A) {
    const length = A.length
    if (length > 100000) return -1
    const counters = new Array(length).fill(0)
    const negativeCounters = new Array(length).fill(0)
    for (i=0; i < length; i++){
        if (A[i] < -2147483648 || A[i] > 2147483647) return -1
        if (A[i] > -1){
            counters[A[i]] = counters[A[i]] + 1
            if (counters[A[i]] > (length / 2)) return i
        } else {
            negativeCounters[A[i] * -1]  =  negativeCounters[A[i] * -1] + 1
            if (negativeCounters[A[i] * -1] > (length / 2)) return i
        }
    }
    return -1
}

This is failing the correctness tests although I have tried a variety of inputs with which it succeeds. The Codility evaluation doesn't list the test input so I can't find input that is breaking the algorithm.

Can anyone spot the problem?

Upvotes: 1

Views: 3703

Answers (3)

Nazariy Vlizlo
Nazariy Vlizlo

Reputation: 977

Swift 100% solution:

public func solution(_ A : inout [Int]) -> Int {
    var result = 0
    var stack = [Int]()

    for element in A {
        if stack.isEmpty || stack.last == element {
            stack.append(element)
        } else if stack.last != element {
            stack.popLast()
        }
    }

    guard let dominator = stack.last else { return -1 }
    var count = 0

    for i in 0..<A.count {
        if dominator == A[i] {
            count += 1
        }
        if count > A.count / 2 {
            return i
        }
    }
    return -1
}

Upvotes: 0

גלעד ברקן
גלעד ברקן

Reputation: 23955

Contrary to some comments and one answer, in fact using an array of counters in JavaScript works fine. This is because arrays in JavaScript are associative objects. One problem with your code is that it fails to initialise to zero counters whose key/index is greater than the initial counters array length.

Here is code that gets 100% on all of Codility's measures:

function solution(A) {
    const arr = []
    for (let i=0; i<A.length; i++){
      if (!arr[A[i]])
        arr[A[i]] = 1
      else
        arr[A[i]]++
      if (arr[A[i]] > A.length/2)
        return i
    }
    return -1
}

Upvotes: 3

maraca
maraca

Reputation: 8743

You shouldn't use an array with that big range of values (the array for the positive values would need a length of 2,147,483,648). You should use a map or in js you can use an object. I hacked something together, not very elegant, but it passes all tests:

function solution(A) {
    const map = {}
    for (let i = 0; i < A.length; i++) {
        const key = '' + A[i]
        map[key] = key in map ? map[key] + 1 : 1
        if (map[key] > A.length / 2)
            return i
    }
    return -1
}

Upvotes: 0

Related Questions