Problem / Examples

After reading the problem description, some items may need more investigation, or even clarification from the interviewer:

1. Will the input array always contain only integers? Could it include invalid values like null, strings, or floating-point numbers? In this case, the array will only contain integers.

2. Is the array sorted? From the test cases it's obvious that the array is unsorted.

3. What should the function return if the input array is empty? The problem doesn't specify behavior for empty input. Knowing the expected output for an empty array helps define the function's behavior. In this case, it should return null.

4. What if there are multiple pairs that add up to 10? Another great question to ask is about handling multiple pairs. In this problem, we're guaranteed only to have one satisfying pair or none. We can appreciate, however, that without being certain of this constraint on the inputs, we would need to know how to handle multiple pairs that add to ten. How would we determine the "first" pair? In the array [3, 4, 6, 7], is [3, 7] the first pair, or is it [4, 6]? Both options could be valid, so the interviewer would need to clarify this.

5. Can I include the same number twice? From the third test case, we see that even though the number 5 is in the array, we don't have a solution. This implies that we cannot use the same number twice. However, you should clarify with the interviewer what would happen if we had two '5's in the array (e.g., [1, 2, 5, 5, 6]). In this case, a valid solution would be [5, 5].

6. Does the order of the elements in the result array matter? The test cases suggest that order matters, but this is something to verify with the interviewer. In this problem, the order does matter. The element appearing first in the original array should also be first in the result array. This means that in the first test case, [3, 7] is a valid solution, but [7, 3] is not.

7. Can the numbers in the input array be negative or zero? Similar to our previous question, we can deduce this information from our test cases. Two of them include negative numbers in the input array, the second of which contains this negative number in the solution pair, [-5, 15]. We may still wish to ask about 0 being a possibility, but at least we know that it's possible for a number greater than 10 to make up a pair that adds to 10.

Let's write down all of the information we've acquired throughout our exploration of the problem, including inputs, outputs, explicit requirements, and implicit requirements.

Problem:

• Input: An array of numbers.
• Output:
  • An array containing two numbers from the input array that add up to the target number, 10.
  • null if no suitable pair is found.

• Rules:

  • Explicit requirements:
    • Find two numbers that sum to 10.
    • If no such numbers exist, return null.
    • There will be exactly one pair that sums to 10, or none.
  • Implicit requirements:
    • The input array will only contain integers.
    • The input array is unsorted.
    • We can't include the same number twice, unless it appears twice.
    • The order of elements in the result array should follow the order of these elements in the original array.
    • Numbers may be negative.

---

Data Structure / Algorithm

What data structure could we use to solve this problem? It should be an array since that's the desired output.

Now, we come to the algorithm part.

Algorithm:

• Use nested loops.

• The outer loop will iterate over indices of the first number in the array.

  • Within each outer loop iteration, a second loop will iterate over the indices of the second number.
    • Sum the current first and second numbers.
    • If the sum equals 10, return an array containing the pair. The first number should be the first element in the array, and the second number should be the second element.

• If the outer loop completes without finding a correct pair, return null.

---

While this algorithm might look complete, it still lacks precision. What does it mean when we say we'll iterate over indices of the first number? In this case, it means iterating from 0 until the second to last index of our input array, or the length of our input minus two. This ensures the second-to-last number in the nums array can still be the first number in a potential result pair.

The inner loop is trickier. Where should it start? Starting from 0 could lead to the index of the first number being greater than the index of the second number, violating the order requirement. For example, in the array [1, 3], if the first index is 1 and the second is 0, the pair would be [3, 1], which is invalid.

We also can't start the inner loop at the same index as the outer loop because we might include the same number twice. For example, in the array [2, 3], if both indices start at 0, we could potentially get the pair [2, 2], which is also invalid.

Therefore, the index of the second number needs to start one position greater than the index of the first number (firstIdx + 1) and iterate until the end of the array, or the length of our input minus one. As the index we use for our outer loop increases, the inner loop will iterate over a smaller set of indices.

Here's a more precise algorithm that encompases these details we've discussed:

Algorithm:

• Create a loop to iterate from 0 up to the length of the input array, nums, minus two (The second to last index). This is our firstIdx.

  • Initialize a variable firstNum to the element of nums at firstIdx.
  • Create a loop to iterate from firstIdx + 1 up to the length of nums minus one. This is our secondIdx.
    • Initialize a variable secondNum to the element of nums at secondIdx.
    • If firstNum plus secondNum is equal to 10, return these numbers in an array, with firstNum first and secondNum second.

• Return null.

---

Walkthrough I

Let's go through the example array [6, 3, 8, 7]. The target sum is 10 per the problem description.

The First Outer Loop Iteration

Beginning with the first number of the array at index 0, 6, we first find all possible pairs that can be created with this number as the first number. As you can see, we're showing the inner loop at work here. The inner loop, in this case, starts with an index of 1 and ends with an index of 3.

• First, we get a pair of numbers at indices 0 and 1. The sum of these numbers (6 and 3) is not equal to 10, so we continue.

• The first number remains the same, but we increment the secondIdx to 2. The sum of numbers at indices 0 and 2, once again, is not equal to 10.

• In the last inner iteration, the secondIdx is 3, the second number is 7, and the sum of the first and second numbers is still not 10.

• Our secondIdx would now be 4, but as our algorithm stated, our inner loop will only iterate up the length of our input minus one. [6, 3, 8, 7].length - 1 is 3. As such, our inner loop has finished for this iteration of our outer loop, where our firstIdx is 0.

---

The Second Outer Loop Iteration

Next, we need to check the pairs of numbers where the first number starts at index 1. The inner loop, in this case, starts with an index of 2 and ends with an index of 3.

• First, we get a pair of numbers at indices 1 and 2. The sum of these numbers (3 and 8) is not equal to 10 so we continue.

• Finally, we get a pair of numbers at indices 1 and 3. The sum of these numbers (3 and 7) is 10 so we return this pair as the result array.

---

Walkthrough II

Let's see another example where we don't find a solution pair, with the array [1, 2, 5, 6].

The First Outer Loop Iteration

Beginning with the first number of the array at index 0, 1, we first find all possible pairs that can be created with this number as the first number. Again, our diagram shows the inner loop's progression. Since our array is the same length as the previous example, this inner loop will again iterate from index 1 up to index 3.

• First, we get a pair of numbers at indices 0 and 1. The sum of these numbers (1 and 2) is not equal to 10 so we continue.

• The first number remains the same, but we increment the secondIdx to 2. The sum of numbers at indices 0 and 2, once again, is not equal to 10.

• In the last inner iteration, the secondIdx is 3, the second number is 6, and the sum of the first and second number is still not 10.

---

The Second Outer Loop Iteration

Next, we need to check the pairs of numbers where the first number starts at index 1. Now that our firstIdx in our outer loop has increased by 1, our secondIdx within The inner loop will start with a value of 2 and end with a value of 3.

• First, we get a pair of numbers at indices 1 and 2. The sum of these numbers (2 and 5) is not equal to 10 so we continue.

• Next, we get a pair of numbers at indices 1 and 3. The sum of these numbers (2 and 6) is 8, so we continue.

---

The Third Outer Loop Iteration

Finally, we need to check the pairs of numbers where the first number starts at index 2. Remember that the inner loop will start at the firstIdx plus one, up to the last index of the input. Here, that means we're iterating from 3 to 3. In practical terms, this means our inner loop is only going to iterate a single time.

• In our single iteration the pair of numbers is 5 and 6. Their sum is not equal to 10.

• Our outer loop has reached its end without us finding a matching pair, and so we return null.

function findPair(nums) {
  for (let firstIdx = 0; firstIdx <= nums.length - 2; firstIdx++) {
    let firstNum = nums[firstIdx];
    for (let secondIdx = firstIdx + 1; secondIdx <= nums.length - 1; secondIdx++) {
      let secondNum = nums[secondIdx];
      if (firstNum + secondNum === 10) return [firstNum, secondNum];
    }
  }
  return null;
}