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

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.

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.