Two-Sum - Range Allowance Algorithm Design

Question

🧩 What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity?

• Optimize for runtime over memory complexity.

• The same item cannot be selected twice.

Inputs

• An Int representing the total capacity
• An Int representing the range above and below the total capacity sums are allowed to be within.
• An Array of Int's representing items' individual capacities.

Output: A Boolean representing whether it is possible for two of the items to equal the total capacity plus and minus the given range.

Samples

1.

• Input: [4, 5, 2, 6]
• Total capacity: 10
• Range Allowance: 0
• Expect: true because 4 + 6 equal 10.

2.

• Input: [4, 5, 2, 5]
• Total capacity: 12
• Range Allowance: 2
• Expect: true even though there are no two numbers that equal 12 directly, there are two numbers that sum to 10 which is within the range allowance provided.

3.

• Input: [4, 5, 2, 7]
• Total capacity: 14
• Range Allowance: 1
• Expect: false

• Jake: Does this answer your question? Two-Sum - Pre-sort Optimization Algorithm Design
• adamhurwitz.eth: @D.W., I've refactored the terminology for the sake of clarity: "Determine whether there are two items whose individual capacity will perfectly equal the total capacity..." An input and output for the original question have also been included.
• adamhurwitz.eth: @D.W., Good to know in terms of providing pseudocode instead of actual code. Thanks for providing the posts as context. I've removed the code portion.
• D.W.: The "best way" is ambiguous, because it is not clear which criteria are most important to you. Instead of asking about the "best" way, it is usually better to specify your criteria or requirements. Do you care primarily about asymptotic running time? About ease of programming? Something else?

Answer 1

This can be solved in $O(n \log n)$ time, much like the ordinary two-sum problem. Sort the items by increasing capacity. Let $t$ denote the desired target (the total capacity), $t$ the amount you can go up or down, so our desired target range is $[t-u,t+u]$, and $A$ the array of elements. We will do a linear scan over the items, left-to-right.

Suppose our linear scan is pointing at the $i$th item, with capacity $A[i]$. We'll ensure that the indices $j,k$ are chosen so that $A[j]$ is the largest value in the array that is $< t-u-A[i]$, and $A[k]$ is the smallest value in the array that is $> t+u-A[i]$. Notice that if $k \ge j+2$, then we have found a solution to the problem. (You'll need to handle the special case where $i=j+1,k=i+1$ specially.) Also, each time you increment $i$ by one, it is easy to update $j$ and $k$, by moving $j$ and $k$ to the left as much as needed. Since $i$ only increases and $j,k$ only decrease, it follows that the linear scan does only $O(n)$ work. So, the total running time is dominated by the time to sort the algorithm.

• adamhurwitz.eth: To make sure I understand, for each iteration of i, search for A[j], the lower bound range allowance t - u, and A[k], the upper bound range allowance t + u. Then, increment/decrement j and k's search until their indices are one apart and continue iterating i repeating the j and k range search.

Answer 2

1. Create a Set searchSet to store the item's that have already been examined.

2. Iterate through the input Array of item capacities.

   2a. Find the targetCapacity for the current item: totalCapacity - itemCapacity.

   2b. Generate a targetCapacitiesArray plus and minus the totalCapacity and the range allowance provided.

   2c. For each capacity in targetCapacitiesArray, see if each number is contained in the searchSet, and return true if found.

   2d. Else, add the itemCapacity to the searchSet.

3. Return false if the entire input is iterated through without finding a match.