As we begin down the road to looking at the Swift compiler one of the big problems to address is the language it is built upon: C++. In this post I’m going to cover a couple of ways you could solve the common ‘Two Number Sum’ algorithm and then compare/investigate some of the similarities and differences between a Swift implementation and a C++ one.

Firstly I work on my algorithms on algoexpert.io. It is a fantastic resource and you should check it out if you want to practice working on algorithms in general. They’re like musical scales that musicians practice only for developers and they help stretch the mind and diagnose weaknesses in ability.

Let us begin with something we often take for granted when working in Swift: the import statement. Usually we’ll import Foundation, but seeing as we’re working with C++ we don’t have that necessarily. The Foundation library contains many great tools for computations, logging and is pretty huge. When you declare an import like this, when you build your application the compiler will do it’s first pass and scan for macro statements and imports and will literally copy in the library you need into your file before going on to compile your code. Think of this as including any dependencies you require in order to run your code. How do we do this in C++ though? #include <vector>.

If you’re familiar with Objective-C you’ll be used to the angled brackets but essentially it is the same here: includes will paste in any libraries required to run your code. Includes with angle brackets are library imports and those in quotations such as #include "yourLibrary/helpers.h" are your own internal libraries.

Now we get access to the standard library in C++ with an abbreviated std namespace like so: using namespace std;. Namespaces allow us to automatically look up and implementation for a function without having to define how to access it explicitly like so std::cout << "Hello World!"; and instead we could do this cout << "Hello World!".

This is going to give you the same result as print("Hello World!") in Swift. Using namespaces though can get messy if you have multiple methods with the same signature, but I wanted to cover it so when you saw it you’d feel comfortable with the concept.

So What is a Vector? 🤔

When you make array in C++ the size has to be fixed. When we want to create something that we can ‘push’ and ‘pop’ to and from, we can import a similar data structure: the Vector type. As an aside you literally will see includes to import String in C++ which might catch you by surprise as well!

We’re going to need our Vector to work with integers and, like Swift, we need to declare its type upfront. A Vector is capable of taking differing types of objects so let’s declare the return type to our method now:

vector<int> twoNumberSum(vector<int> array, int targetSum)

You’re probably used to seeing generic types with the angled brackets but if not, it’s simply specifying the type of objects our Vector will hold: Integers. (C++ uses templates, not generics but the concept is similar and I’ll come back to this another time).

We declare our return type vector<int> upfront then the name of the function twoNumberSum. Next we specify the parameters: the first will be a Vector if Ints called array and the target: an Int.
It’s not that different from Swift except we don’t have the luxury of naming the parameters. I am literally typing this into algoexpert.io, however if you use C-Lion it will actually insert parameters in your editor which is nice!

Implementation One – Not the Best

Let’s look at a simple implementation for now and I’ll explain why it isn’t ideal later. Here’s a sample array of Integers:

array = [-2, -1, 0, 4, 9, 15];
targetSum = 13;

First we’ll loop over each element in the array using a for loop:

for(int i=0; i<array.size(); i++) {
// This will go -2, -1, 0... and so on

This will loop over each element using the array’s size (count in Swift) which is actually a method here. Next, for each element in the array at the current index, lets go over each subsequent element:

for(int i=0; i<array.size(); i++) {
// Begins at -2
   for(int j=i+1; j<array.size(); j++) {
// Then goes -1, 0, 4, 9, 15

What we really want is [-2, 15] here. So we need to basically compare if adding the two elements together equals our target and if so return it.

if (array[i] + array[j] == targetSum) {

Next lets just gather the elements at their indexes:

if (array[i] + array[j] == targetSum) {
   const int originNumber = array[i];
   const int comparativeNumber = array[j];
   return vector<int>{originNumber, comparativeNumber}; 

You’ll notice we’re using the const keyword here which guarantees we’re not going to change the value (similar to let in Swift). Similarly we can see a constructed Vector using the curly brace syntax: this would simply be return [originNumber, comparativeNumber] in Swift.

Great so this works, but it is very, very slow. Worst-case scenario we need to loop over every element in the array, and multiply that by every element again! If our dataset was to grow this could be a crippling solution. But we’re learning so its all gooooood!

Second Solution – Dictionaries and Hashing

Let’s now store the already-looked-up numbers in a hash map – a Swift Dictionary, or in our case a map. Each time we inspect an element in our vector we’re going to cache its value so that we already know if we’ve seen it before or not.

// C++
map<int, bool> mappedNumbers{};
// Swift
var mappedNumbers: [Int, Bool] = [:]

We’re just storing a bool to say it’s been looked up but what really matters is the integer value itself. Now I know what you’re thinking: in Swift you can lookup an item in a dictionary using a subscript: mappedNumbers[2] right? Not quite that easy in our case.

Maps are looked up using their find method and that uses an iterator under the hood.

// C++
if (mappedNumbers.find(2) != mappedNumbers.end())
// Swift
if mappedNumbers[2] {

This will basically check if the map has a key of 2 by making sure it hasn’t hit the end of the map.

Let’s continue with the solution and its good practice for writing loops over Vectors!

for (int i = 0; i < array.size(); i++) {
   int thisNumber = array[i];
   int difference = targetSum - thisNumber;

Here we loop over each element in the array only once, we check the difference between our target number and the current number and then we’ll decide what to do with it next. Now that we’re armed to the teeth with how to check if a value exists in a hash map let’s finish this beast!

if (mappedNumbers.find(difference) != mappedNumbers.end()) {
    return vector<int>{thisNumber, difference};
} else {
    mappedNumbers[thisNumber] = true;
}

Now we just check if its already in our map, then return the Vector with those values, else we cache it and continue through the loop. The great news is this is exponentially faster (I’ll cover Big-O notation later for measuring the effectiveness of algorithms).

One last Tip – Sorting

Sometimes you just have to sort a vector before working on a solution and there are a million ways you could solve this algorithm using sorting so I thought I would show you how that is done:

// C++
sort(array.begin(), array.end());
// Siwft
array.sorted()

Well Done!

Nice work – you’ve began working with C++, discovered maps, vectors, how to write methods and declare variables and you solved the 2 number sum problem 2 times over! How did you find the difference between the two languages?


Complete solution one

vector<int> twoNumberSum(vector<int> array, int targetSum) {
	
   for(int i=0; i<array.size(); i++) {
      for(int j=i+1; j<array.size(); j++) {
      if (array[i] + array[j] == targetSum) {
         const int originNumber = array[i];
         const int comparativeNumber = array[j];
         return vector<int>{originNumber, comparativeNumber}; 
         }
      }
   }
	
  return {};
}

Better solution:

vector twoNumberSum(vector array, int targetSum) {
   map<int, bool> mappedNumbers{};

   for (int i = 0; i < array.size(); i++) {
       int thisNumber = array[i];
       int difference = targetSum - thisNumber;

       if (mappedNumbers.find(difference) != mappedNumbers.end()) {
          return vector<int>{thisNumber, difference};
       } else {
          mappedNumbers[thisNumber] = true;
       }
   }

   return {};
}
code-disciple

Author code-disciple

More posts by code-disciple

Leave a Reply