Skip to main content
Talentd

Maximum Points in an Archery Competition - Solution & Explanation

MediumArrayBacktrackingBit ManipulationEnumeration16 min readAsked at: Kakao
Practice this problem

Problem Statement

Alice and Bob are opponents in an archery competition. The competition has set the following rules:

  1. Alice first shoots numArrows arrows and then Bob shoots numArrows arrows.
  2. The points are then calculated as follows:
    1. The target has integer scoring sections ranging from 0 to 11 inclusive.
    2. For each section of the target with score k (in between 0 to 11), say Alice and Bob have shot ak and bk arrows on that section respectively. If ak >= bk, then Alice takes k points. If ak < bk, then Bob takes k points.
    3. However, if ak == bk == 0, then nobody takes k points.

  • For example, if Alice and Bob both shot 2 arrows on the section with score 11, then Alice takes 11 points. On the other hand, if Alice shot 0 arrows on the section with score 11 and Bob shot 2 arrows on that same section, then Bob takes 11 points.

You are given the integer numArrows and an integer array aliceArrows of size 12, which represents the number of arrows Alice shot on each scoring section from 0 to 11. Now, Bob wants to maximize the total number of points he can obtain.

Return the array bobArrows which represents the number of arrows Bob shot on each scoring section from 0 to 11. The sum of the values in bobArrows should equal numArrows.

If there are multiple ways for Bob to earn the maximum total points, return any one of them.

 

Example 1:

Input: numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
Output: [0,0,0,0,1,1,0,0,1,2,3,1]
Explanation: The table above shows how the competition is scored. 
Bob earns a total point of 4 + 5 + 8 + 9 + 10 + 11 = 47.
It can be shown that Bob cannot obtain a score higher than 47 points.

Example 2:

Input: numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
Output: [0,0,0,0,0,0,0,0,1,1,1,0]
Explanation: The table above shows how the competition is scored.
Bob earns a total point of 8 + 9 + 10 = 27.
It can be shown that Bob cannot obtain a score higher than 27 points.

 

Constraints:

  • 1 <= numArrows <= 105
  • aliceArrows.length == bobArrows.length == 12
  • 0 <= aliceArrows[i], bobArrows[i] <= numArrows
  • sum(aliceArrows[i]) == numArrows

Approach Overview

Problem Overview: Bob and Alice shoot arrows at 12 scoring sections (0–11). Alice’s arrow counts are known. Bob has numArrows and earns i points only if he shoots aliceArrows[i] + 1 arrows in section i. The task is to distribute Bob’s arrows to maximize total points and return the arrow allocation.

Approach 1: Greedy Subset Enumeration (Bitmask) (Time: O(2^12), Space: O(1))

There are only 12 scoring sections, which makes full enumeration feasible. Treat each section as a binary decision: either Bob wins it by spending aliceArrows[i] + 1 arrows or skips it. Use a bitmask from 0 to 2^12 - 1 to represent every subset of sections Bob tries to win. For each mask, iterate through the bits, compute arrows required, and accumulate the score if the cost fits within numArrows. Track the configuration with the highest score and assign remaining arrows to section 0. This works well because the search space is tiny (4096 states). The method relies heavily on Bit Manipulation and simple iteration over an Array.

Approach 2: Dynamic Programming (0/1 Knapsack) (Time: O(12 * numArrows), Space: O(12 * numArrows))

This problem maps directly to a 0/1 knapsack formulation. Each section i is an item with value i (points gained) and weight aliceArrows[i] + 1 (arrows required to win). Build a DP table where dp[i][j] represents the maximum points achievable using the first i sections with j arrows. For each section, decide whether to skip it or spend the required arrows to win it. After filling the table, backtrack through the decisions to reconstruct Bob’s arrow distribution. This approach demonstrates classic Dynamic Programming thinking and generalizes well when the number of sections grows.

Recommended for interviews: Subset enumeration using bitmasks is typically the fastest to implement because the state space is fixed at 2^12. It clearly shows you recognized the constraint that makes brute force viable. The DP approach demonstrates stronger algorithmic modeling by converting the scoring system into a knapsack problem, which interviewers often appreciate for its clarity and scalability.

Approach 1: Greedy Approach

This approach focuses on maximizing the points Bob can obtain by checking from the highest scoring section to the lowest. For each scoring section, Bob will only decide to shoot if he can win that section; specifically, Bob must shoot more arrows than Alice in that section. This is done by iterating from the highest to the lowest score sections.

This Python function first initializes Bob's arrows array and calculates how many arrows are remaining. Then, it iterates from section 11 to 0, checking if Bob has enough arrows to win the section. If Bob can win, he shoots enough arrows to exceed Alice's count by one. Any remaining arrows are finally placed in the lowest scoring section.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(1), as the scoring sections are fixed in number (12).
Space Complexity: O(1), using constant extra space for arrays.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach utilizes dynamic programming to calculate the maximum score Bob can achieve by distributing his arrows over different scoring sections optimally. It works by considering previously calculated optimum scores at earlier sections and updating based on whether Bob wins or loses each section.

This Java solution uses a dynamic programming table to explore how each arrow placement impacts Bob's score. By maintaining a table of maximum scores that can be achieved with a given number of arrows for each section, the function updates the result array accordingly. If Bob can win a section with the remaining arrows, he attempts to do so.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n * numArrows), where n is the number of sections (12) and numArrows is the total number of arrows.
Space Complexity: O(n * numArrows), for the DP table.

Try this approach in the editor →

Approach 3: Binary Enumeration

Since there are only 12 regions, we use binary enumeration to determine in which regions Bob scores. We use a variable st to represent the scheme in which Bob obtains the maximum score, and mx to represent the maximum score Bob obtains.

We enumerate Bob's scoring schemes in the range [1, 2^m), where m is the length of aliceArrows. For each scheme, we calculate Bob's score s and the number of arrows cnt. If cnt leq numArrows and s > mx, we update mx and st.

Then, we calculate Bob's scoring scheme based on st. If there are any remaining arrows, we allocate the remaining arrows to the first region, which is the region with index 0.

The time complexity is O(2^m times m), where m is the length of aliceArrows. Ignoring the space consumption of the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(1), as the scoring sections are fixed in number (12).
Space Complexity: O(1), using constant extra space for arrays.

Dynamic Programming Approach

Time Complexity: O(n * numArrows), where n is the number of sections (12) and numArrows is the total number of arrows.
Space Complexity: O(n * numArrows), for the DP table.

Binary Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Subset Enumeration (Bitmask)O(2^12)O(1)Best when the number of scoring sections is small and fixed. Fast to implement and easy to reason about.
Dynamic Programming (0/1 Knapsack)O(12 * numArrows)O(12 * numArrows)Useful when modeling the problem formally as a resource allocation problem or when the number of sections could scale.

Video Solution

2212. Maximum Points in an Archery Competition || Leetcode Weekly Contest 285 || Leetcode 2212 • Bro Coders • 2,911 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Points in an Archery Competition easy or hard?
The problem is rated Medium because the brute-force search space is small but the optimal modeling is not immediately obvious. Recognizing that each section is a binary decision and that only 12 sections exist is the key insight that simplifies the solution.
Maximum Points in an Archery Competition Python/Java solution
Python solutions commonly use bitmask enumeration because it is concise and efficient for 12 sections. Java and C++ implementations often demonstrate the dynamic programming (0/1 knapsack) approach, which builds a DP table and reconstructs the arrow allocation.
How to solve Maximum Points in an Archery Competition in O(2^12)?
Represent each subset of scoring sections using a 12-bit mask. For each mask, calculate how many arrows Bob must spend to beat Alice in the selected sections (aliceArrows[i] + 1). If the total arrows used does not exceed numArrows, compute the score and keep the best configuration.
What is the best approach for Maximum Points in an Archery Competition?
Bitmask subset enumeration is the most practical approach. Since there are only 12 scoring sections, you can iterate through all 2^12 possible subsets and compute the arrows required to win each set of sections. This yields the optimal score in O(2^12) time and constant extra space.
Is Maximum Points in an Archery Competition asked at Google/Amazon/Meta?
Problems involving subset enumeration, knapsack modeling, and bitmask optimization frequently appear in interviews at companies like Amazon, Google, and Meta. This question tests the ability to recognize small state spaces and convert resource allocation problems into DP or bitmask solutions.
What data structure is used in Maximum Points in an Archery Competition?
The core data structure is an array representing Alice’s arrow counts across 12 sections. Solutions often use bitmasks for subset enumeration or a 2D DP table for the knapsack formulation. Both rely on iterating through the array to compute costs and scores.
What is the time complexity of Maximum Points in an Archery Competition?
The common optimal solution runs in O(2^12) time by enumerating all subsets of scoring sections. Because 2^12 equals 4096, the search space is very small. A dynamic programming alternative runs in O(12 * numArrows) time using a knapsack-style DP table.

Ready to solve this problem?

Practice Maximum Points in an Archery Competition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Product of the Length of Two Palindromic Subsequences