algorithms – Two-Sum Design – Pre-sort, Range Allowance, Many Sums

I would love feedback on the pseudocode design objectives outlined below.

  • Pre-Sort: Optimize a two-sum solution that has a pre-sorted input.
  • Range Allowance: Find a two-sum solution within a range plus/minus the given capacity.
  • Many Sums: Convert a two-sum item solution to have as many items as possible based on a given capacity.

Two-Sum: Determine whether there are two items whose length will equal the total length while ensuring the same item cannot be used twice. This optimizes for runtime over memory.

  • Time complexity: $O(n)$
  • Space complexity: $O(n)$

Samples

Input: (4, 5, 2, 6)

  • Total length: 10
  • Expect: true

Input: (4, 5, 2, 5)

  • Total length: 10
  • Expect: true

Input: (4, 5, 2, 7)

  • Total length: 10
  • Expect: false

Code

fun isLengthMatch(totalLength: Int, lengths: IntArray): Boolean {
    handleErrors(totalLength, lengths)
    val searchSet = hashSetOf<Int>()
    for (length in lengths) {
        val targetLength = totalLength - length
        if (searchSet.contains(targetLength)) return true
        else searchSet.add(length)
    }
    return false
}

fun handleErrors(totalLength: Int, lengths: IntArray) {
    if (totalLength <= 0) throw IllegalArgumentException(""totalLength" must be greater than 0.")
    if (lengths.size < 2) throw IllegalArgumentException(""lengths" cannot be less than two items.")
}

Pre-Sort

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

i.e.

Input: (6,2,1,0)

Iterations

  1. targetLength = 9 - 6, lastTargetLength = 3
  2. Return false because the length of 2 < lastTargetLength of 3.

Range Allowance

  1. Generate a targetLengthsArray +/- the totalLength and the given range allowance.

  2. Check if the searchSet contains any of the values in the targetLengthsArray.

Many Sums

Find the items that will produce the optimum sum with the given capacity.

  1. Create a 2D array
    • Rows: Items, ascending in capacity
    • Columns: Capacity, ascending to max capacity
  2. For each item, find the max value based on the capacity
    • a. If the item capacity > current capacity: Choose the previous capacity value.
    • b. Else: Choose the max of i and ii.
      • i. Item value + Item value at (current capacity – item capacity)
      • ii. Previous capacity value
      • iii. If i == ii: Choose the previous item value.
  3. Find the max value items.
    • a. Check previous item at the same capacity until capacity == 0
      • i. If current value == previous capacity value: Add the previous capacity value.
      • ii. Else: Add the current item and look at the last item at (current capacity – item capacity).

See: 0/1 Knapsack Problem Dynamic Programming by Tushar Roy – Coding Made Simple