0
$\begingroup$

🧩 Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order?

🚀 Original Two-Sum

Determine whether there are two items whose individual capacity will perfectly equal the total capacity while ensuring the same item cannot be selected twice.

  • Input: An Int representing the total capacity and 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.
  • Time complexity: Linear growth, $O(n)$
  • Space complexity: Linear growth, $O(n)$

Samples

Input: [4, 5, 2, 6]

  • Total capacity: 10
  • Expect: true

Input: [4, 5, 2, 5]

  • Total capacity: 10
  • Expect: true

Input: [4, 5, 2, 7]

  • Total capacity: 10
  • Expect: false

Pseudocode

  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. If searchSet contains the targetCapacity, return true.

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

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

🏗️ Pre-Sort

  1. Save a new var lastTargetCapacity
  2. If the current itemCapacity < lastTargetCapacity, there are no possible two-sums and return false.

i.e.

Input: [6,2,1,0]

  • Total capacity: 9

Iterations

  1. targetCapacity = 9 - 6, lastTargetCapacity = 3
  2. Return false because the itemCapacity of 2 < lastTargetCapacity of 3.
$\endgroup$
9
  • $\begingroup$ @YuvalFilmus, I appreciate the suggestion. According to the Help center post for the Computer Science community, What topics can I ask about here?, this community includes posts regarding algorithm design, correctness, and complexity. This question is a good fit as it relates to algorithm design expressed via pseudocode. $\endgroup$ Nov 23 '20 at 17:32
  • $\begingroup$ I don't know whether it is suitable here. My opinions: I can't tell what the question is. "I would love feedback on the design objectives" is not a question and seems too open-ended to me. Our site is for focused technical questions. Code is off-topic here so I'm a bit put off by the code in the question. Reviewing your pseudocode, in the spirit of Code Review but applied to your pseudocode instead of your code, doesn't seem like a good fit here to me, but maybe others have other views. So I can't give a definitive answer whether this is in-scope; that'd be up to the community. $\endgroup$
    – D.W.
    Nov 23 '20 at 20:12
  • $\begingroup$ @D.W., I defined specific questions in the post above by providing the algorithmic design under defined conditions, 1. Pre-Sort 2. Range Allowance 3. Many Sums, and asking the community whether the strategy outlined for each is correct. This seems to be on-topic per the Help Center's What topics can I ask about here? post. $\endgroup$ Nov 23 '20 at 21:07
  • $\begingroup$ Pre-sorted, whatever that means is ok (standard algorithm, standard approach). There are no questions (there are no “?” marks in your text, so I am pretty sure), yet, but I can suggest two, perhaps separate questions: “How could we optimize two-sum given range, is iteration by hash tables by range the best we could do?” What if range is from min to max? Second question, does many “sums algorithm” you have proposed is valid, but there is no proof, could you try to prove it and ask about obstacles, if any? Could you invent a different algorithm, not based on hash tables? $\endgroup$
    – Evil
    Nov 24 '20 at 10:45
  • $\begingroup$ Great feedback @Evil! I've refactored the design objectives into questions per your advice. $\endgroup$ Nov 26 '20 at 15:13
0
$\begingroup$

The Two Sum solution can be optimized for runtime performance given the input Array is pre-sorted in ascending or descending order.

If Binary Search is used to find the targetCapacity above, it will run in logarithmic, $O(logn)$, average runtime. This is faster than the pseudocode above that runs in linear, $O(n)$, runtime using iteration and hashing.

If sorting was not provided in the input then it would not be possible to sort and search faster than $O(n)$. The best that could be done would be $O(nlogn)$ with a strategy such as Quicksort and Binary Search.

See: Stanford - Two Sum Explanation

$\endgroup$
0
$\begingroup$

Yes, you can solve the two-sum problem in $O(n)$ time, if the numbers are presented in sorted order. See my other answer for how to do it; it involves a linear scan. This is asymptotically optimal, as it already takes $O(n)$ time even to read the input, and solving the problem may require reading the entire input, so there can no further asymptotic improvement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.