[Leetcode] 948. Bag of Tokens explained

Problem

948. Bag of Tokens

Approach

Sort the tokens array in ascending order.
Keep left and right indices, which denotes allowed tokens available with initialPower.

left \(\leftarrow\) 0
right \(\leftarrow\) n-1

While left <= right:

1. Find maximum score we can make with tokens in [left, right] and update maximumScore.
2. Subtract tokens[l] from initialPower and add tokens[r] to initialPower.
3. Increment left by 1, and decrement right by 1.

Return maxScore value in the end.

Sorting apparently takes \(O(n{\log}n)\).
The indices left and right covers all n tokens, and each time there is a computation with n-complexity.
Thie makes time complexity \(O(n^2)\).

Code

class Solution {
    public int bagOfTokensScore(int[] tokens, int initialPower) {
        Arrays.sort(tokens);
        int n= tokens.length, l= 0, r= n-1;
        int maxScore= 0;
        while (l <= r) {
            if (tokens[l] > initialPower) break;
            int idx= l, score= 0, power= initialPower;
            while (idx <= r && tokens[idx] <= power) {
                power -= tokens[idx++];
                ++score;
            }
            maxScore= Math.max(maxScore, score);

            initialPower += (tokens[r]-tokens[l]);
            ++l; --r;
        }
        return maxScore;
    }
}

Complexity

• Time: \(O(n{\log}n + n^2)\)
• Space: \(O(1)\)