Delete and Freeze Game
Updated
Problem statement
You are given an integer array a of length n. Alice and Bob play a game on it, taking turns, and Alice moves first.
- On Alice's turn, she deletes exactly one element that is not frozen.
- On Bob's turn, he freezes exactly one element that is neither deleted nor frozen. A frozen element can never be deleted.
The game ends as soon as every element that is still in the array is frozen. The frozen elements keep their original order and form the final array b.
The score of the game is the largest value of b[j] - b[i] over all pairs of indices i < j in b. The score can be negative. If b has fewer than two elements, the score is 0.
Alice plays to make the score as small as possible, and Bob plays to make it as large as possible. Return the score when both play optimally.
Function
finalScore(a: int[]) → intExamples
Example 1
a = [1,2,3,4]return = 1Bob freezes two elements in this game. Alice first deletes 4. From [1, 2, 3], Bob freezes some element, and Alice then deletes the partner that would give Bob the bigger score. For every choice Bob makes, what is left gives a score of 1. For example, Bob freezes 1, Alice deletes 3, and Bob freezes 2, so b = [1, 2].
If Alice first deleted 2 instead, Bob could freeze 1, whose partners 3 and 4 both give at least 2. If she first deleted 3, Bob could freeze 4, whose partners 1 and 2 both give at least 2. If she first deleted 1, then from [2, 3, 4] every element Bob freezes again leaves him a score of 1. No first move holds Bob below 1, so the answer is 1.
Example 2
a = [1,5,2]return = 0Alice deletes one element, Bob freezes one, and Alice deletes the last unfrozen one. Only one element stays, so the score is 0.
Example 3
a = [5,4,3,2,1]return = -2Every pair gives a negative difference, and two elements closer together in the array give a less negative one. Alice first deletes 3.
Call two elements neighbors when they were next to each other in the original array. A pair of neighbors gives -1, the best score possible here. After 3 is gone, no element has a neighbor on both sides. Whatever Bob freezes, Alice deletes its one remaining neighbor, so the best Bob can do is two elements two places apart in the original array, such as b = [4, 2] with score 2 - 4 = -2.
If Alice deleted any other element first, Bob could freeze an element with a neighbor on each side, and keep one of them for a score of -1. So the answer is -2.
Constraints
3 <= n <= 10^51 <= a[i] <= 10^9
More Rubrik Online Assessment questions
- Delete K Subsets for Maximum ScoreOA · Seen Nov 2026
- Distribute Elements Into Two Arrays IIOA · Seen Nov 2026
- Minimum Replacements to Sort the ArrayOA · Seen Nov 2026
- Minimum Swaps To Binary PalindromeOA · Seen Apr 2026
- Get Minimum OperationsOA · Seen Nov 2024
- Horizontal Pod AutoscalerOA · Seen Nov 2024
- Stock PricesOA · Seen Nov 2024
- StarlightOA · Seen Oct 2024
- Energy CrisisOA · Seen Sep 2024
- Mike and GemsOA · Seen Sep 2024
Similar questions at other companies
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Maximum Three-Server Difficulty ScoreVisa · OAVisa interview questions
- Minimum Fuel Car AlignmentFivetran · PHONE SCREENFivetran interview questions
- Maximize K-Element AND with an Increment BudgetAmazon · OA
- Most Segments That Sort the ArrayRippling · OARippling interview questions
- Most Items Within Budget from a Start IndexHudson River Trading · OAHudson River Trading interview questions
- Luna and the Colorful SocksPhonePe · OAPhonePe interview questions
- Minimum Starting Coins to Buy All ProductsMicrosoft · OAMicrosoft interview questions
- Lock CodeGoldman Sachs · OAGoldman Sachs interview questions
- Power Update After K-th Largest InsertionGoogle · OAGoogle interview questions