Flip Game II - Solution & Explanation

Q: Is Flip Game II easy or hard?

Flip Game II is generally considered a medium difficulty problem. The recursion logic is straightforward, but recognizing the need for memoization and reasoning about winning versus losing states requires familiarity with backtracking and game theory patterns.

Q: Flip Game II Python/Java solution

In Python or Java, implement a recursive DFS that scans the string for "++" pairs. Replace them with "--", call the function for the opponent’s turn, then restore the string. Use a hash map keyed by the string state to memoize results and avoid recomputation.

Q: How to solve Flip Game II in O(n)?

An exact O(n) general solution is not typically used for this problem because the state space depends on all possible game configurations. The common interview solution uses backtracking with memoization and runs in roughly O(n * 2^n). More advanced theoretical solutions use combinatorial game theory, but they are rarely required in interviews.

Q: What is the best approach for Flip Game II?

Backtracking with memoization is the most effective approach. The algorithm tries every possible "++" flip and recursively checks if the opponent loses from the resulting state. A hash map caches previously evaluated board configurations so each state is computed once. This reduces repeated work across the game tree.

Q: Is Flip Game II asked at Google/Amazon/Meta?

Flip Game II represents a classic game‑theory recursion problem and has appeared in interview preparation sets associated with companies like Google, Amazon, and Meta. Interviewers use it to evaluate reasoning about winning states, recursion, and memoization.

Q: What data structure is used in Flip Game II?

A hash map (or dictionary) is used for memoization to store previously evaluated board states. Recursion explores possible moves, while the map quickly returns results for repeated configurations. Strings or character arrays represent the board state.

Q: What is the time complexity of Flip Game II?

The typical memoized DFS solution runs in O(n * 2^n) time in the worst case. Each unique board configuration may be explored once, and generating next states requires scanning the string for "++" pairs. Space complexity is O(2^n) for recursion and memo storage.

MediumPremiumFree on FleetCodeMath Dynamic Programming Backtracking Memoization5 min readAsked at: Google, Tiktok

Practice this problem

Problem Statement

You are playing a Flip Game with your friend.

You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return true if the starting player can guarantee a win, and false otherwise.

Example 1:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Example 2:

Input: currentState = "+"
Output: false

Constraints:

1 <= currentState.length <= 60
currentState[i] is either '+' or '-'.
There cannot be more than 20 consecutive '+'.

Follow up: Derive your algorithm's runtime complexity.

Approach Overview

Problem Overview: You receive a string containing '+' and '-'. A move flips any consecutive "++" into "--". Players alternate turns. If a player cannot make a move, they lose. The task is to determine whether the starting player has a guaranteed winning strategy.

Approach 1: Pure Backtracking (Game Simulation) (Time: O(n * 2^n), Space: O(2^n))

Simulate the game directly. Iterate through the string and look for every "++". For each occurrence, flip it to "--" and recursively check if the opponent can win from the resulting state. If any move leads to a position where the opponent loses, the current player wins. This explores the entire game tree, which grows exponentially because each state can branch into several new states.

The key insight is standard two-player game reasoning: if you can move to a state where the opponent has no winning move, your current state is winning. Without caching, the same board configuration may be recomputed many times, making this approach impractical for longer strings.

Approach 2: Backtracking with Memoization (Optimal) (Time: O(n * 2^n), Space: O(2^n))

Store previously computed states in a hash map so the same configuration is evaluated only once. Each recursive call checks whether the current string already exists in the memo table. If it does, return the stored result immediately. Otherwise iterate through the string, flip each "++", and recursively evaluate the opponent’s position.

If any generated state returns false (opponent loses), mark the current state as true and store it in the memo map. This pruning drastically reduces repeated computation across the game tree. The approach is essentially a depth‑first search over possible states combined with caching, a common pattern in backtracking and memoization problems.

Conceptually, the problem is also related to impartial combinatorial games where positions are classified as winning or losing states. Instead of computing full Grundy numbers from game theory, the memoized DFS simply checks if a losing child state exists.

Recommended for interviews: Backtracking with memoization is the expected solution. Starting with brute force shows you understand the game simulation, but adding memoization demonstrates awareness of overlapping subproblems and converts the search into an efficient dynamic exploration of states, similar to techniques used in dynamic programming.

Solution

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Pure Backtracking (Game Tree Exploration)	O(n * 2^n)	O(2^n)	Useful for understanding the game logic and recursive state exploration
Backtracking with Memoization	O(n * 2^n)	O(2^n)	Best practical solution; avoids recomputing previously evaluated board states

Video Solution

Flip Game II • Kevin Naughton Jr. • 9,525 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Flip Game II easy or hard?

Flip Game II is generally considered a medium difficulty problem. The recursion logic is straightforward, but recognizing the need for memoization and reasoning about winning versus losing states requires familiarity with backtracking and game theory patterns.

Flip Game II Python/Java solution

In Python or Java, implement a recursive DFS that scans the string for "++" pairs. Replace them with "--", call the function for the opponent’s turn, then restore the string. Use a hash map keyed by the string state to memoize results and avoid recomputation.

How to solve Flip Game II in O(n)?

An exact O(n) general solution is not typically used for this problem because the state space depends on all possible game configurations. The common interview solution uses backtracking with memoization and runs in roughly O(n * 2^n). More advanced theoretical solutions use combinatorial game theory, but they are rarely required in interviews.

What is the best approach for Flip Game II?

Backtracking with memoization is the most effective approach. The algorithm tries every possible "++" flip and recursively checks if the opponent loses from the resulting state. A hash map caches previously evaluated board configurations so each state is computed once. This reduces repeated work across the game tree.

Is Flip Game II asked at Google/Amazon/Meta?

Flip Game II represents a classic game‑theory recursion problem and has appeared in interview preparation sets associated with companies like Google, Amazon, and Meta. Interviewers use it to evaluate reasoning about winning states, recursion, and memoization.

What data structure is used in Flip Game II?

A hash map (or dictionary) is used for memoization to store previously evaluated board states. Recursion explores possible moves, while the map quickly returns results for repeated configurations. Strings or character arrays represent the board state.

What is the time complexity of Flip Game II?

The typical memoized DFS solution runs in O(n * 2^n) time in the worst case. Each unique board configuration may be explored once, and generating next states requires scanning the string for "++" pairs. Space complexity is O(2^n) for recursion and memo storage.

Ready to solve this problem?

Practice Flip Game II with our built-in code editor and test cases.

Practice on FleetCode

Can I Win

Flip Game

Problem Info

DifficultyMedium

Acceptance52.2%

Approaches1

Reading time5 min

Asked at

Google Tiktok