Your text is clear and well-structured, but I have made some minor edits for grammar, clarity, and conciseness. Here’s the proofread version:
I have an array of integers and a numeric target, and I need to identify the two indices in the array that point to the integers that sum to the target. For example, if the target is 3 and our input array is [1, 4, 2, 5], the answer would be [0, 2].
Brute Force Approach
The brute force solution involves looping through the array twice: once for the first value and again for the second, to find the two numbers that add to the target. This results in a time complexity of (O(n^2)), since in the worst case, you'd need to loop through the array n times to find both indices.
As a sidebar, (O(n^2)) is expensive and becomes exponentially more costly as the dataset grows. For instance, 100 records require 10,000 operations, while 10,000 records need 100,000,000 operations! This explains why my brute force approaches worked during Advent of Code part 1, but trying the same method would make my laptop sound as if it were trying to take off.
My Initial Solution That Won't Work
When I have an array as input and my expected output is two indices, my first thought is to use the Two Pointer technique, where I maintain two indices and move them around until I find my answer. However, I don't think Two Pointer will work here because the array isn't sorted, and I need to keep the original indices in the results. If the array were sorted, I could work from both ends: moving the left pointer if the sum undershoots the target and moving the right pointer if it overshoots. Unfortunately, starting from a sorted state would have an (O(n)) time complexity and (O(1)) space complexity, as we would only need to traverse the array once without needing additional memory.
Sorting the array to reach a state where this works would take (O(n *log n)), which is inherently more expensive than our optimal (O(n)) solution. Thus, sorting only makes sense if the eventual runtime is (O(n log n)) or more expensive.
What Works Instead
A wise man in a YouTube video I can't remember—sorry, wise creator—once said, "When in doubt, reach for a hash." This proves handy here. At any point in the array, since I'm looking for a sum, I can find the other integer needed to reach the target by subtracting the current value from the target. With this in mind, I can store each value and its index as a pair in a hashmap. If my target is 5 and my first value is 2, the pair is 3. First, I will check if 3 is a key in the hash; if not, I will create a new entry with the key of 2 and my index of 0. The idea is that I will only need to go through the array a maximum of once, resulting in (n) operations, because at each stage, I'll be able to check the hashmap to see if my current value's pair has already been found. Eventually, if my array has a 3 at, say, index 6, I can check my hash for the pair of 2, which I will find, giving me my answer of [0, 6].
This approach has a time complexity of (O(n)) since I'm only traversing the array once, and a space complexity of (O(n)) because my hash grows linearly with each new member of the array.
The Code
const findTwoSum = (inputArray: number\[], target: number) => {
const pairHash: Record\<number, number> = {};
for (let i: number = 0; i < inputArray.length; i++) {
const currentValue = inputArray\[i];
const pair = target - currentValue;
const foundPairIndex = pairHash\[pair];
if (foundPairIndex !== undefined) { // need to explicitly check for undefined, as zero is a valid index
return \[foundPairIndex, i];
}
pairHash\[currentValue] = i;
}
}This worked great on the first try. Once I grasped the concept, the actual coding part was straightforward.
Lessons Learned
• Regardless of sorting, if you can derive the desired pair from each found element, a hash is the perfect data structure. Getting and setting in a hash is (O(1)) time.
• Since sorting is (O(n *log n)), if the array is not already sorted, sorting it is probably not a good first step. Unless time complexity is expected to be above that—like an (O(n^2)) three-sum problem—then maybe you should always start with sorting? I’m not sure; I’m just speculating.
• Figuring out the algorithm beforehand and talking it out makes coding much easier.
Feel free to adjust any part of the text further if needed!