Predict the Winner

MediumDynamic Programminginterval dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Two players face an array nums. Player 1 moves first; on each turn the current player takes either the leftmost or the rightmost remaining number and adds it to their own score. The game ends when the array is empty. Both players play optimally to maximize their own score. Return true if player 1 finishes with a score **greater than or equal to** player 2's score (a tie counts as a win for player 1), otherwise false.

Examples

Input: nums = [1,5,2]
Output: false
If player 1 takes 1, player 2 takes 5; if player 1 takes 2, player 2 takes 5. Player 1 ends with at most 3 against 5.
Input: nums = [1,5,233,7]
Output: true
Player 1 takes 1; whichever end player 2 takes, player 1 can then take 233.

Constraints

  • `1 <= nums.length <= 20`
  • `0 <= nums[i] <= 10^7`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More interval dp problems