LeetCode: Bag of Tokens

// https://code.dennyzhang.com/bag-of-tokens
// Basic Ideas: greedy + two pointer
//
// get as many power points as possible with cheap price
// trade one points with high token
//
// Notice: When to stop power -> token?
//
// Complexity: Time O(n*log(n)), Space O(1)
import "sort"
func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

func bagOfTokensScore(tokens []int, P int) int {
    res := 0
    power, token := 0, P
    sort.Ints(tokens)
    left, right := 0, len(tokens)-1

    // fmt.Println(tokens)
    // token >= tokens[left] || power>0: can make a deal
    for left <= right && (token >= tokens[left] || power>0) {
        // get as many power points as possible with cheap price
        for left <= right && token >= tokens[left] {
            token -= tokens[left]
            power++
            left++
            res = max(res, power)
        }
        // trade one points with high token
        if left<=right && power>0 {
            token += tokens[right]
            power--
            right--
        }
        // fmt.Println(res, power, token, left, right)
    }
    return res
}