Alice and Bob are opponents in an archery competition. The competition has set the following rules:
numArrows arrows and then Bob shoots numArrows arrows.0 to 11 inclusive.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.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 <= 105aliceArrows.length == bobArrows.length == 120 <= aliceArrows[i], bobArrows[i] <= numArrowssum(aliceArrows[i]) == numArrowsProblem 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.
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.
Python
JavaScript
Time Complexity: O(1), as the scoring sections are fixed in number (12).
Space Complexity: O(1), using constant extra space for arrays.
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.
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.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(1), as the scoring sections are fixed in number (12). |
| Dynamic Programming Approach | Time Complexity: O(n * numArrows), where n is the number of sections (12) and numArrows is the total number of arrows. |
| Binary Enumeration | — |
| Approach | Time | Space | When 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. |
2212. Maximum Points in an Archery Competition || Leetcode Weekly Contest 285 || Leetcode 2212 • Bro Coders • 2,890 views views
Watch 8 more video solutions →Practice Maximum Points in an Archery Competition with our built-in code editor and test cases.
Practice on FleetCode