You have an initial power P, an initial score of 0 points, and a bag of tokens.
Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.

Return the largest number of points we can have after playing any number of tokens.
 



Example 1:
Input: tokens = [100], P = 50
Output: 0


Example 2:
Input: tokens = [100,200], P = 150
Output: 1


Example 3:
Input: tokens = [100,200,300,400], P = 200
Output: 2

 
Note:

tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis

Greedy algorithms

Starter code: class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        

Solutions:
class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		tokens = sorted(tokens)
		left = 0
		right = len(tokens) - 1
		points = 0
		if len(tokens) == 1:
			if tokens[0] <= P:
				return 1
		if len(tokens) == 0:
			return 0
		while left < right:
			if tokens[left] <= P:
				P -= tokens[left]
				left += 1
				points += 1
			elif tokens[left] > P and points > 0:
				P += tokens[right]
				points -= 1
				right -= 1
			elif points == 0 and tokens[left] > P:
				break
		if P >= tokens[left]:
			points += 1
		return points


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		tokens.sort()
		max_points = 0
		points = 0
		i = 0
		j = len(tokens) - 1
		while i <= j:
			if P >= tokens[i]:
				points += 1
				P -= tokens[i]
				max_points = max(points, max_points)
				i += 1
			elif points > 0:
				points -= 1
				P += tokens[j]
				j -= 1
			else:
				return max_points
		return max_points


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		(max_points, points) = (0, 0)
		tokens.sort()
		(i, j) = (0, len(tokens) - 1)
		while i <= j:
			if P < tokens[i]:
				if i == j or points == 0:
					break
				P += tokens[j]
				points -= 1
				j -= 1
			points += 1
			P -= tokens[i]
			i += 1
			max_points = max(max_points, points)
		return max(max_points, points)


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		tokens.sort()
		if not tokens or P < tokens[0]:
			return 0
		(l, r) = (0, len(tokens) - 1)
		points = 0
		while l <= r:
			if P >= tokens[l]:
				points += 1
				P -= tokens[l]
				l += 1
			elif r - l > 1:
				points -= 1
				P += tokens[r]
				r -= 1
			else:
				break
		return points


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		if not tokens:
			return 0
		tokens.sort()
		point = 0
		while tokens:
			if P < tokens[0]:
				if point and len(tokens) > 1:
					P += tokens.pop()
					point -= 1
				else:
					break
			else:
				P -= tokens.pop(0)
				point += 1
		return point


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		tokens.sort()
		maxPoints = 0
		points = 0
		(left, right) = (0, len(tokens) - 1)
		while left <= right and P >= 0:
			if P - tokens[left] >= 0:
				P -= tokens[left]
				points += 1
				maxPoints = max(maxPoints, points)
				left += 1
			elif points > 0:
				P += tokens[right]
				points -= 1
				right -= 1
			else:
				break
		return max(maxPoints, points)


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		tokens.sort()
		left = 0
		right = len(tokens) - 1
		ans = 0
		curr = 0
		while not left > right:
			if P >= tokens[left]:
				curr += 1
				ans = max(ans, curr)
				P -= tokens[left]
				left += 1
			elif curr > 0:
				P += tokens[right]
				curr -= 1
				right -= 1
			else:
				break
		return ans


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		n = len(tokens)
		tokens.sort()
		i = 0
		j = n - 1
		points = 0
		result = 0
		while i <= j:
			if tokens[i] <= P:
				points += 1
				result = max(result, points)
				P -= tokens[i]
				i += 1
			else:
				if points == 0:
					break
				P += tokens[j]
				points -= 1
				j -= 1
		return result


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		startIndex = 0
		endIndex = len(tokens) - 1
		points = 0
		tokens.sort()
		while True:
			print(startIndex, endIndex, P)
			if startIndex > endIndex or endIndex < startIndex:
				return points
			if P >= tokens[startIndex]:
				points += 1
				P -= tokens[startIndex]
				startIndex += 1
			elif points == 0:
				return points
			elif startIndex == endIndex:
				return points
			else:
				P += tokens[endIndex]
				endIndex -= 1
				points -= 1


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		tokens.sort()
		(buyer, seller) = (0, len(tokens) - 1)
		max_items = current_items = 0
		while buyer <= seller:
			if P >= tokens[buyer]:
				P -= tokens[buyer]
				current_items += 1
				buyer += 1
			elif current_items == 0:
				break
			else:
				P += tokens[seller]
				current_items -= 1
				seller -= 1
			max_items = max(max_items, current_items)
		return max_items


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		if not len(tokens):
			return 0
		tokens.sort()
		res = 0
		deque = collections.deque(tokens)
		while len(deque) > 1 and (P >= deque[0] or res):
			while deque and P > deque[0]:
				res += 1
				P -= deque.popleft()
			if len(deque) > 1 and res:
				P += deque.pop()
				res -= 1
		if deque and P >= deque[0]:
			res += 1
		return res


class Solution:

	def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
		tokens.sort()

		def twoPointer(tokens, P):
			i = 0
			j = len(tokens) - 1
			score = 0
			maxScore = 0
			while i <= j:
				flag = False
				while i < len(tokens) and P >= tokens[i]:
					score += 1
					P -= tokens[i]
					i += 1
					flag = True
				if flag:
					maxScore = max(score, maxScore)
					continue
				if score > 0:
					score -= 1
					P += tokens[j]
					j -= 1
				elif P < tokens[i]:
					return score
			return maxScore

		def helper(tokens, P, score):
			maxVal = score
			if score > 0 and len(tokens) > 0:
				maxVal = max(helper(tokens[:len(tokens) - 1], P + tokens[len(tokens) - 1], score - 1), maxVal)
			for i in range(len(tokens) - 1, -1, -1):
				if P >= tokens[i]:
					maxVal = max(helper(tokens[:i] + tokens[i + 1:], P - tokens[i], score + 1), maxVal)
			return maxVal
		return twoPointer(tokens, P)