DEV Community

Sachin Yadav
Sachin Yadav

Posted on

Bag of Tokens (Greedy Two Pointer Technique)

The approach I used here is greedy I always want my score to increase so I will always go with the first condition that is if the power is greater than the current token then increment the count also if there is need or my power is less than the current token then I will always want to increase my power with the biggest token number. Therefore this gives the intuition that we need to sort the array of tokens in the ascending order so that when I am increasing my score then I pick from the left because it will be less than my power and if I want to increase my power then I will always choose from the right

/**
 * @param {number[]} tokens
 * @param {number} power
 * @return {number}
 */
var bagOfTokensScore = function (tokens, power) {
    tokens.sort((a, b) => a - b)
    let score = 0
    let maxScore = 0
    let i = 0
    let j = tokens.length - 1
    while (i <= j) {
        if (power >= tokens[i]) {
            power -= tokens[i]
            score++
            i++
            maxScore = Math.max(score, maxScore)
        } else if (score >= 1) {
            power = power + tokens[j]
            j--
            score--
        } else {
            return maxScore
        }
    }
    return maxScore
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)