K-Complementary Pairs with JavaScript

I recently had the opportunity to take a code challenge for a company that I really admire, and would like to work with one day. I was grateful, excited, and even more so anxious because there were a lot of unknowns going into the code challenge. The reality is that there’s only so much you could do to prepare:

• Build Projects
• Study Algorithms
• Grind Problems: LeetCode, HackerRank, CodeSignal

However, the only way to figure out whether or not you are ready is to jump into the deep end to see if you could float. So I did, and I learned so much more than I ever had before, and because of that I wanted to share it.

The Problem Set

At the start of the assignment I was faced with three tasks to complete. I’ll be focusing on only 1 of these in this blog — K-Complementary Pairs.

The Goal

• You are given Target Integer and an Array full of positive Integers
• You need to find and locate the complement to the Target Integer — which means the value of one index and another index MUST equal the Target
• Return the count of the pairs at the end

numberArray[2] + numberArray[3] = 7

The above would be a valid pair since these two values equal the target.

First Approach

When I first approached this issue, I went after it in a brute force manner. I thought that I could use nested loops to check for the complementary pairs, and hey, I was right! It actually worked:

Solution #1 — Nested Loops

How does it work?

• You loop over the initial array’s elements.
• You then loop over it in unison to vet whether or not it equals the Target through each pass.
• If the Target is a match then the count is incremented.

While it works, and I did receive an accurate count of the complementary pairs given a target, it wasn’t ideal. The reality is that nested loops are slow, and can grow exponentially given larger arrays of elements. The time complexity for it is O(N²).

Second Approach — Optimization

So I went back to the drawing board. After some research and consideration, I found that I could store the values in an object — {key: value}.

Now, this was still very tricky, especially since I’ve never written something so complex before. I was treading into new territory, but I was excited because I was actually able to optimize my former algorithm to O(N):

Solution #2 — Storing Values in an Object

So how does it work?

• Vet that numberArray or the Length is existent.
• We run through the numberArray first to create key/value pairs in the located_pairs object. Throughout this process it will check for uniqueness and duplicates.
• We then run over the keys of the located object and vet for whether or not it makes with the target. If it does, the pairs count is incremented.