CODEWITHSUNDEEP
javascriptalgorithm
Happy Machine
Happy Machine

Reputation: 1163

Codility nested algorithm test performance

I'm attempting the Codility 'Nested' test in Javascript.

The test is as below:

A string S consisting of N characters is called properly nested if:

S is empty;
S has the form "(U)" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

function solution(S);

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..1,000,000];
string S consists only of the characters "(" and/or ")".

My solution is the following:

function solution(S) {
    const elements = S.split('')
    const stack = []
    if (elements.length > 1000000) return 0
    if (elements[0] == ')') return 0
    if (elements[0] == '(') stack.push('(')
    for (i=0; i < elements.length; i++){
        const currentElement = elements[i]
        if (currentElement !== '(' && currentElement !== ')') return 0
        if (i>0){
            if (stack[stack.length-1] == '(' && currentElement == ')') stack.pop()
            else stack.push(currentElement)
        }
    }
        if (stack.length) return 0
        else return 1
}

This is correct but returns only 75% on performance, i can't see how to further improve the efficiency, does anyone have any suggestions?

Upvotes: 0

Views: 1736

Answers (6)

Nazariy Vlizlo
Nazariy Vlizlo

Reputation: 977

Swift 100% solution:

public func solution(_ S : inout String) -> Int {
    guard !S.isEmpty else { return 1 }

    var stack = [Character]()

    for character in S {
        if stack.isEmpty && character == ")" { 
            return 0
        }

        guard !stack.isEmpty, (stack.last! == "(" && character == ")") else {
            stack.append(character)
            continue
        }
        stack.popLast()
    }

    return stack.isEmpty ? 1 : 0
}

Upvotes: 0

Mohamad Abu Kharoub
Mohamad Abu Kharoub

Reputation: 1

100% on Codility

const nesting = (s) => {
if (!s.length) {
    return 1;
}

if (s.indexOf('(') === -1 && s.indexOf(')') === -1) {
    return 1;
}

const arr = [];
const map = {
    '(': ')'
};

for (let i = 0; i < s.length; i++) {
    if (s[i] === '(' || s[i] === ')') {
        if (!arr.length || map[arr[arr.length - 1]] !== s[i]) {
            arr.push(s[i]);
            continue;
        }

        if (map[arr[arr.length - 1]] === s[i]) arr.pop();
    }
}

return arr.length > 0 ? 0 : 1;
}

Upvotes: 0

Damini Garg
Damini Garg

Reputation: 11

function solution(S) {
  let stack=[];
  if(!S){
   return 1;
  }
 for(let i=0;i<S.length;i++){
    if(S[i]==='('){
     stack.push(S[i]);
   }else if(stack.length){
     stack.pop();
    }else{
    return 0;
  }
 }
return stack.length ? 0: 1;
}

Upvotes: 0

Halil Azyikmis
Halil Azyikmis

Reputation: 149

There are too many "if"s in your solution. Try to understand maraca's answer. Or, check my solution below (99% same)

function solution(S) {
    let stack = 0;
    for (let i=0; i<S.length; i++) {
        S[i] === '(' ? stack++ : stack--; 
    
        if (S[i] === '(') {
            stack++
        } else {
            stack--;
            if (stack < 0) return 0;
        }
    }
    return stack === 0 ? 1 : 0;
}

Upvotes: 0

maraca
maraca

Reputation: 8743

I think you are doing this way too complicated. Split isn't necessairy. Also the problem statement says the string only contains ( and ). So the solution can be as simple as this (passes all tests):

function solution(S) {
    let count = 0
    for (const c of S) {
        if (c == '(')
            count++
        else if (--count < 0)
            return 0
    }
    return count == 0 ? 1 : 0
}

Btw. this statement in your code is wrong:

if (currentElement == ')' && openCount > 0)  openCount = openCount - 1
else openCount = openCount + 1

If the count would become negative because there are too many ) you will increase the counter. So maybe it isn't a performance problem after all. Same for the solution with the stack: if the stack is empty you look for stack[-1] and this is undefined so you push the next element (although there it doesn't fail because you will push ) and this will never be consumed). Also it would make more sense to push the index of the opening braces on the stack so that you could (if you wanted to) show the pairings of the braces, which ( belongs to which ). If you just push ( on the stack you can as well use a counter.

Upvotes: 3

Happy Machine
Happy Machine

Reputation: 1163

Following suggestions in the comments, i tried using a counter.

This still fails on efficiency though, being penalised on broad tree with deep paths.

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    const elements = S.split('')
    let openCount = 0
    if (elements.length > 1000000) return 0
    if (elements[0] == ')') return 0
    if (elements[0] == '(') openCount = 1
    for (i=0; i < elements.length; i++){
        const currentElement = elements[i]
        if (currentElement !== '(' && currentElement !== ')') return 0
        if (i>0){
            if (currentElement == ')' && openCount > 0)  openCount = openCount - 1
            else openCount = openCount + 1
        }
    }
        if (openCount !== 0) return 0
        else return 1
}

Upvotes: 0

Related Questions