C++ interview problem: finding an Island in a 2D grid

Question

I was asked this question from an online coding interview and I have provided my solution that passes all of the test cases. I wanted to see if someone can review my code.

You can find my solution below using BFS. Here's also the link to the question that was asked at Pramp.

Island Count

Given a 2D array binaryMatrix of 0s and 1s, implement a function getNumberOfIslands that returns the number of islands of 1s in binaryMatrix.

An island is defined as a group of adjacent values that are all 1s. A cell in binaryMatrix is considered adjacent to another cell if they are next to each either on the same row or column. Note that two values of 1 are not part of the same island if they’re sharing only a mutual “corner” (i.e. they are diagonally neighbors).

Explain and code the most efficient solution possible and analyze its time and space complexities.

input:  binaryMatrix = [ [0,    1,    0,    1,    0],
                         [0,    0,    1,    1,    1],
                         [1,    0,    0,    1,    0],
                         [0,    1,    1,    0,    0],
                         [1,    0,    1,    0,    1] ]

output: 6 # since this is the number of islands in binaryMatrix.
          # See all 6 islands color-coded below.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

#define AND &&
using namespace std;

int getNumberOfIslands( const vector<vector<int>>& binaryMatrix ) 
{
  int ans=0;
  int n = binaryMatrix.size();
  if (!n) return 0;
  int m = binaryMatrix[0].size();
  unordered_set<int> *used = new unordered_set<int>[n];
  for (int i=0; i<n; i++) used[i].clear();
 //Implementation through Breadth First Search
 // starting origin for my x and y coordinates 
  int dx[] = {-1, 1, 0, 0};
  int dy[] = {0, 0, -1, 1};
  queue< pair<int, int> > q;



  for (int i=0; i<n; i++)
    for (int j=0; j<m; j++){

      if (!used[i].count(j) AND binaryMatrix[i][j]==1){

        ans++;

        q.push(make_pair(i, j));
        used[i].insert(j);
        while (!q.empty()){
          pair<int, int> pos = q.front();
          q.pop();

          for (int k=0; k<4; k++){
            int nx = pos.first+dx[k];
            int ny = pos.second+dy[k];
            if (nx<0 || nx>=n) continue;
            if (ny<0 || ny>=m) continue;
            if (used[nx].count(ny)) continue;
            if (binaryMatrix[nx][ny]!=1) continue;

            used[nx].insert(ny);
            q.push(make_pair(nx, ny));


          }



        }

      }

    }

  return ans;

}  



int main() {
  return 0;
}

My code passes all of the test cases:

Test Case #1
Input: [[0]],Expected: 0,Actual: 0
Test Case #2
Input: [[1]],Expected: 1,Actual: 1
Test Case #3
Input: [[1,0,1,0]],Expected: 2,Actual: 2
Test Case #4
Input: [[1,0,1,0],[0,1,1,1],[0,0,1,0]],Expected: 2,Actual: 2
Test Case #5
Input: [[1,0,1,0],[0,1,1,1],[0,0,1,0],[1,1,0,0],[0,1,0,1]],Expected: 4,Actual: 4
Test Case #6
Input: [[0,1,0,1,0],[0,0,1,1,1],[1,0,0,1,0],[0,1,1,0,0],[1,0,1,0,1]],Expected: 6,Actual: 6
Test Case #7
Input: [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]],Expected: 1,Actual: 1

Answer 1

Don't use using namespace std

It's considered bad practice.

Don't define AND

There is already and as an alternative to &&.

Use std::vector instead of new[]

You have a memory leak at the moment, since you forgot to delete[] the allocated memory. std::vector prevents this kind of error.

Use appropriate data structures

You use an array of unordered_set<int>s where a std::unordered_set< std::pair<int,int> > would be sufficient. Also, clear() isn't necessary. Unless your std::unordered_set implementation is broken, a std::unordered_set starts out empty.

Consider const for variables that shouldn't change

dx, dy, n and m should never change. const makes sure that you don't change them by accident.

Always use braces around blocks

No braces after control structures have led to several bugs that were hard to catch. Always use them. That way you cannot accidentally forget to place them when necessary.

Answer 2

Consider using a std::array where possible, which is whereever you have an array whose size you know in advance. This is essentially a modern c++ wrapper around old c style arrays, so you get all the speed of int[] and the clarity and safety of things like vector.

It's good to have comments, and comments that describe the overarching algorithm and how the different pieces contribute to that are particular gold. That said, I personally found the comment about breadth first search confusing. It could perhaps have done with a few more words about how search fits into the problem. Something like "Breadth First Search to find the boundaries of the island."

More expressive variable names would make things much clearer. Single letter variables can almost always be helpfully replaced with something that says what it's meant to do. There are exceptions, such as if you're implementing a standard bit of mathematics and using the same variables as your reference text, but that's not this case. Even just using width and height instead of n and m would help.

I like the use of the std::pair in your queue. It correctly represents that these are not two different numbers but one coordinate. I would probably define a little class or struct and call it Point to make for slightly more self-documenting code, but that's a minor gain. I would suggest using the same model elsewhere: for example rather than separate dx and dy arrays you could have one array that contains these int pairs (or Points).

I'm uncertain about the use of the array of sets you call "used". It would definitely be better either to just use a set (In which case let it be a set of pairs/Points as above) or just use something like arrays (or Vectors as appropriate). There is one tiny trick available if you go for the vector of vectors option. Start by renaming "used" to "remaining". Initialize it as a copy of your input binaryMatrix, and whenever you check of a point on an island set it to zero. Then you can simultaneously check points for being sea and for having already been visited.

I appreciate your marking your binaryMatrix const. It is worth being aware of the details of how const interacts with containers: if you want to make sure that the function can't change anything about that variable you'd really want const vector<const vector<const int>>. That isn't just repetition for emphasis: it's saying that you're not allowed to mess with binaryMatrix or any of the vectors you get out of binaryMatrix, or any of the integers that you get out of any of those vectors.

Checking against the input array being empty is a very good thing to remember. It's a neat trick that if the array is empty then n will be zero which is false which is not true. However, it would be clearer to write if(n == 0) or even if(binaryMatrix.empty()). The compiler will probably sort out optimising it down to the same thing, so people have the freedom to code in ways that people can read.

Answer 3

Edit: This is probably what I should have said at the outset to make things more clear:

Since your interview question is concerned with performance:

Explain and code the most efficient solution possible and analyze its time and space complexities.

A single simple in-place 2D char matrix is much faster than what you have coded (20x faster in fact).

Thus, it's all about performance. And, the algorithm matters. IMO, it's appropriate to talk about alternatives because yours is not in the ballpark range as to what is possible/required in performance.

It doesn't meet the "most efficient" criterion. In an actual interview situation, this would probably be flagged by the interviewer.

Note that, if you were [much] closer, say within 10%, this wouldn't be an issue [and I wouldn't have posted].

I'm not sure that you can meet the objective without a full refactoring of your code.

Your solution puts an additional strain on the processor's cache and seems to have more complexity than would be needed. It also seems to use more memory than is required as well. And, a number of the STL primitives you are using, by their nature, appear to access the heap a lot (i.e.) they're slow.

I'd say that simply clearing out cells as you traverse would be better than adding the complexity you have [or see below].

Also, for your algorithm, do you have benchmarks on and analysis of how much performance is taken up by each of the STL components you're using. That would probably be required when discussing the time/space tradeoffs. As it is, they are a bit of a black box.

Is there a better alternative to vector<vector<int>> for your matrix? I think it adds an extra [internal] pointer dereference [that the optimizer might be able to elide] for each cell access.

And, for example, I see a better alternative to using a separate unordered_set to keep track of visited nodes. When a node has been visited [used], simply OR it with 2. Eliminate your used altogether. Then, you can replace:

if (!used[i].count(j) AND binaryMatrix[i][j]==1)

With:

if (binaryMatrix[i][j]==1)

And, change all the places where you do (e.g.):

used[i].insert(j);

Into:

binaryMatrix[i][j] |= 2;

If you need your function to be non-destructive of the original matrix, at your function end, to undo this, you could loop on:

binaryMatrix[i][j] &= 1;

This is extra work, but is [probably] still faster overall.

---

Edit: This was my original opening section, which has been getting dinged. I'm leaving it in, for reference, but after rereading it, although it might have been tightened a bit, it does talk about the performance issues

Caveat: This isn't a critique of your code style [as Zeta has already done that], but rather an alternate algorithm that can be 20x faster.

A single simple 2D char matrix can be much faster than using the std::* primitives.

As you were doing a c++ interview question, demonstrating std::* proficiency might be paramount and this might be a moot point.

But, when the performance difference is an order of magnitude faster, that may make the difference. I've had a few related interviews and speed sometimes matters more. Assessing such a tradeoff may, in fact, be part of the requested/desired solution.

To eliminate boundary checks, I've created an oversize matrix that has a border of zeroes on all sides. The actual data matrix is inlaid from [1,1]. This is a technique used in some video/image processing.

By using pointers instead of index variables, this also eliminates a number of multiplies within the loop.

---

Anyway, here's a full program that does comparison benchmarking. Ignore most of it, and compare the mtxcount and zapline functions against your getNumberOfIslands function. They are largely c/c++ agnostic.

The primary intent here is to back up the 20x performance benchmark above, rather than just stating that without proof.

It will also allow, if you so choose, to provide a baseline reference for any recode/tweaks you may wish to do

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <time.h>

#ifndef OPT_XPT
#define OPT_XPT         0
#endif

#ifndef OPT_ZPRT
#define OPT_ZPRT        0
#endif

int opt_xpt;
int opt_v;
int opt_T;
int del_Y = -1;
int del_X = -1;

char xptfmt[20];

int xfidx;
FILE *xfstream[2];

#define sysfault(_fmt...) \
    do { \
        prtf(_fmt); \
        xfdone(); \
        exit(1); \
    } while (0)

int
prtf(const char *fmt,...)
__attribute__((__format__(__printf__,1,2)));

#define zprtok(_lvl) \
    opt_T

#if OPT_ZPRT
#define zprt(_lvl,_fmt...) \
    do { \
        if (zprtok(_lvl)) \
            prtf(_fmt); \
    } while (0)
#else
#define zprt(_lvl,_fmt...)      /**/
#endif

double
tvgetf(void)
{
    struct timespec ts;
    double sec;

    clock_gettime(CLOCK_REALTIME,&ts);

    sec = ts.tv_nsec;
    sec /= 1e9;
    sec += ts.tv_sec;

    return sec;
}

void
xfinit(void)
{

    xfstream[0] = fopen("/tmp/orig.txt","w");
    xfstream[1] = fopen("/tmp/fast.txt","w");
    xfidx = 0;
}

void
xfset(int idx)
{

    xfidx = idx;
}

void
xfdone(void)
{

    fclose(xfstream[0]);
    fclose(xfstream[1]);
}

int
prtf(const char *fmt,...)
{
    FILE *xf;
    va_list ap;
    int len;

    xf = xfstream[xfidx];

    va_start(ap,fmt);
    len = vfprintf(xf,fmt,ap);
    va_end(ap);

    return len;
}

void
banner(void)
{

    prtf("\n");
    for (int col = 1;  col <= 80;  ++col)
        prtf("-");
    prtf("\n");
}

void
rowmark(int ycur,int ymax,int xmax)
{
    int xcur;
    int ylen;
    int xlen;
    char buf[40];

    ylen = sprintf(buf,"%d",ymax);
    ylen = sprintf(buf,"%*d:",ylen,ycur);

    //int xlen = sprintf(buf,"%d",xmax);

    if ((ycur % 10) == 0) {
        for (xcur = 0;  xcur <= ylen;  ++xcur)
            prtf(" ");

        xlen = 0;
        for (xcur = 0;  xcur < xmax;  xcur += 10) {
            xlen += prtf("%d",xcur);
            for (;  (xlen % 20) != 0;  ++xlen)
                prtf(" ");
        }
        prtf("\n");

        for (xcur = 1;  xcur <= ylen;  ++xcur)
            prtf(" ");

        for (xcur = 0;  xcur < xmax;  ++xcur)
            prtf(" %c",((xcur % 10) == 0) ? '|' : ' ');
        prtf("\n");
    }

    prtf("%s",buf);
}
// since this is the number of islands in binaryMatrix.
// See all 6 islands color-coded below.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#define AND &&
using namespace std;

#define bigvector vector< vector<int> >

#if 0
bigvector binaryMatrix = [
    [0, 1, 0, 1, 0],
    [0, 0, 1, 1, 1],
    [1, 0, 0, 1, 0],
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 1]];
#endif

// expected 6
bigvector binaryMatrix = {
    {0, 1, 0, 1, 0},
    {0, 0, 1, 1, 1},
    {1, 0, 0, 1, 0},
    {0, 1, 1, 0, 0},
    {1, 0, 1, 0, 1}};

// expected 0
bigvector test_1 = {
    { 0 }
};

// expected 1
bigvector test_2 = {
    { 1 }
};

// expected 2
bigvector test_3 = {
    { 1, 0, 1, 0 }
};

// expected 2
bigvector test_4 = {
    { 1, 0, 1, 0 },
    { 0, 1, 1, 1 },
    { 0, 0, 1, 0 }
};

// expected 4
bigvector test_5 = {
    {1,0,1,0},
    {0,1,1,1},
    {0,0,1,0},
    {1,1,0,0},
    {0,1,0,1}
};

// expected 6
bigvector test_6 = {
    {0,1,0,1,0},
    {0,0,1,1,1},
    {1,0,0,1,0},
    {0,1,1,0,0},
    {1,0,1,0,1}
};

// expected 6
bigvector test_7 = {
    {1,1,1,1,1},
    {1,1,1,1,1},
    {1,1,1,1,1},
    {1,1,1,1,1},
    {1,1,1,1,1}
};

int
getNumberOfIslands(const vector<vector<int> >&binaryMatrix)
{
    int ans = 0;
    int n = binaryMatrix.size();

    if (!n)
        return 0;
    int m = binaryMatrix[0].size();
    unordered_set<int> *used = new unordered_set<int>[n];

    for (int i = 0; i < n; i++)
        used[i].clear();

    // Implementation through Breadth First Search
    // starting origin for my x and y coordinates
    int dx[] = { -1, 1, 0, 0 };
    int dy[] = { 0, 0, -1, 1 };
    queue< pair<int,int> > q;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            if (!used[i].count(j) AND binaryMatrix[i][j] == 1) {
                if (OPT_XPT && opt_xpt) {
                    prtf("XPT:");
                    prtf(xptfmt,i,j);
                    prtf("\n");
                }

                ans++;

                q.push(make_pair(i, j));
                used[i].insert(j);
                while (!q.empty()) {
                    pair<int,int> pos = q.front();

                    q.pop();

                    for (int k = 0; k < 4; k++) {
                        int nx = pos.first + dx[k];
                        int ny = pos.second + dy[k];

                        if (nx < 0 || nx >= n)
                            continue;
                        if (ny < 0 || ny >= m)
                            continue;
                        if (used[nx].count(ny))
                            continue;
                        if (binaryMatrix[nx][ny] != 1)
                            continue;

                        used[nx].insert(ny);
                        q.push(make_pair(nx, ny));
                    }
                }
            }
        }
    }

    return ans;
}
#define XYDEF(_cur) \
    int ycur = _cur - mtxbase; \
    int xcur = (ycur % stride) - 1; \
    ycur /= stride; \
    ycur -= 1

struct mtxctl {
    char *mtxbase;
    char *mtxzero;
    int ymax;
    int xmax;
    int stride;
    char *vmargin;
    int delstop;

    mtxctl()
    {
        mtxbase = NULL;
    }

    char *
    mtxloc(int ycur,int xcur)
    {

        ycur += 1;
        xcur += 1;

        return &mtxbase[(ycur * stride) + xcur];
    }

    void
    zapone(char *mtxcur)
    {

#ifdef ZAPCHK
        if (del_X >= 0) {
            XYDEF(mtxcur);
            prtf("DEL: %s\n",mtxtag(mtxcur));
            if ((ycur == del_Y) && (xcur == del_X) && delstop)
                sysfault("zapone: fault\n");
            delstop = 1;
        }
#endif

        *mtxcur = 0;
    }

    void
    mtxalloc(int ydim,int xdim);

    void
    mtxfree(void);

    int
    mtxget(int ycur,int xcur);

    void
    mtxset(int ycur,int xcur,int val);

    void
    zapline(char *mtxcur);

    void
    mtxshow(void);

    int
    mtxcount(void);

    char *
    mtxtag(char *mtxcur);
};

void
mtxctl::mtxalloc(int ydim,int xdim)
{
    char buf[20];

    mtxfree();

    mtxbase = (char *) calloc(1,(ydim + 2) * (xdim + 2));
    ymax = ydim;
    xmax = xdim;
    stride = xmax + 2;
    vmargin = mtxloc(ymax,-1);
    mtxzero = mtxloc(0,0);

    ydim = sprintf(buf,"%d",ydim);
    xdim = sprintf(buf,"%d",xdim);
    sprintf(xptfmt,"[%%%d.%dd,%%%d.%dd]",ydim,ydim,xdim,xdim);
}

void
mtxctl::mtxfree(void)
{

    if (mtxbase != NULL)
        free(mtxbase);
    mtxbase = NULL;
}

void
mtxctl::mtxset(int ycur,int xcur,int val)
{
    char *mtxcur;

    mtxcur = mtxloc(ycur,xcur);
    *mtxcur = val;
}

int
mtxctl::mtxget(int ycur,int xcur)
{
    char *mtxcur;
    int val;

    mtxcur = mtxloc(ycur,xcur);
    val = *mtxcur;

    return val;
}

char *
mtxctl::mtxtag(char *mtxcur)
{
    XYDEF(mtxcur);
    static char buf[100];

    sprintf(buf,xptfmt,ycur,xcur);

    return buf;
}

void
mtxctl::mtxshow(void)
{
    int ycur;
    int xcur;

    xfset(1);
    banner();

    for (ycur = 0;  ycur < ymax;  ++ycur) {
        if (opt_v)
            rowmark(ycur,ymax,xmax);
        for (xcur = 0;  xcur < xmax;  ++xcur)
            prtf(" %d",mtxget(ycur,xcur));
        prtf("\n");
    }
}

int
mtxctl::mtxcount(void)
{
    char *mtxlhs;
    char *mtxrhs;
    char *mtxcur;
    int hitflg;
    int count;

    count = 0;

    mtxlhs = mtxzero;

    for (;  mtxlhs < vmargin;  mtxlhs += stride) {
        // point to start and end of row
        mtxcur = mtxlhs;
        mtxrhs = mtxlhs + xmax;

        // scan current row
        while (1) {
            // find next non-zero in row (i.e. an island)
            hitflg = 0;
            for (;  mtxcur < mtxrhs;  ++mtxcur) {
                if (*mtxcur) {
                    hitflg = 1;
                    break;
                }
            }
            if (! hitflg)
                break;

            if (OPT_XPT && opt_xpt)
                prtf("XPT:%s\n",mtxtag(mtxcur));

            count += 1;

            // remove all adjoining ones connected to current island
            delstop = 0;
            zapline(mtxcur);

            // point to rightmost immediate neighbor
            ++mtxcur;
        }
    }

    return count;
}

void
mtxctl::zapline(char *mtxmid)
{
    char *mtxcur;
    char *mtxnxt;

    zprt(ZPXHOWPGM,"zapline: ENTER mtxmid=%s\n",mtxtag(mtxmid));

    // zap from current position rightward
    for (mtxcur = mtxmid;  *mtxcur != 0;  ++mtxcur) {
        zapone(mtxcur);

        // look at neighbor above us
        mtxnxt = mtxcur - stride;
        if (*mtxnxt != 0)
            zapline(mtxnxt);

        // look at neighbor below us
        mtxnxt = mtxcur + stride;
        if (*mtxnxt != 0)
            zapline(mtxnxt);
    }

    // zap from previous position leftward
    for (mtxcur = mtxmid - 1;  *mtxcur != 0;  --mtxcur) {
        zapone(mtxcur);

        // look at neighbor above us
        mtxnxt = mtxcur - stride;
        if (*mtxnxt != 0)
            zapline(mtxnxt);

        // look at neighbor below us
        mtxnxt = mtxcur + stride;
        if (*mtxnxt != 0)
            zapline(mtxnxt);
    }

    zprt(ZPXHOWPGM,"zapline: EXIT mtxmid=%s\n",mtxtag(mtxmid));
}

void
showvec(const bigvector &mtx)
{
    int n = mtx.size();

    xfset(0);
    banner();

    if (!n)
        return;
    int m = mtx[0].size();

    for (int i = 0; i < n; i++) {
        if (opt_v)
            rowmark(i,n,m);
        for (int j = 0; j < m; j++) {
            int val = mtx[i][j];
            prtf(" %d",val);
        }
        prtf("\n");
    }
}

bigvector *
bldvec(void)
{
    bigvector *mtx = new(bigvector);
    int ymax;
    int xmax;
    int val;

    while (1) {
        ymax = rand() % 100;
        if (ymax)
            break;
    }

    while (1) {
        xmax = rand() % 100;
        if (xmax)
            break;
    }

    for (int ycur = 0;  ycur < ymax;  ++ycur) {
        vector<int> row;
        for (int xcur = 0;  xcur < xmax;  ++xcur) {
            val = rand() & 1;
            row.push_back(val);
        }
        mtx->push_back(row);
    }

    return mtx;
}

void
vec2mtx(const bigvector &vec,mtxctl *mtx)
{
    int ymax;
    int xmax;
    int val;

    ymax = vec.size();
    if (! ymax)
        return;

    xmax = vec[0].size();

    mtx->mtxalloc(ymax,xmax);
    for (int ycur = 0;  ycur < ymax;  ++ycur) {
        for (int xcur = 0;  xcur < xmax;  ++xcur) {
            val = vec[ycur][xcur];
            mtx->mtxset(ycur,xcur,val);
        }
    }
}

void
vecall(bigvector *vec)
{
    int who;
    mtxctl mymtx;
    int counts[2];
    double tvbeg;
    double elap[2];
    double ratio;
    const char *tag;

    showvec(*vec);

    vec2mtx(*vec,&mymtx);
    mymtx.mtxshow();

    for (int iter = 0;  iter <= 1;  ++iter) {
#if 0
        who = iter;
#else
        who = ! iter;
#endif

        xfset(who);

        if (opt_v)
            prtf("\n");

        tvbeg = tvgetf();
        switch (who) {
        case 0:
            counts[who] = getNumberOfIslands(*vec);
            break;

        default:
            counts[who] = mymtx.mtxcount();
            break;
        }

        elap[who] = tvgetf() - tvbeg;

        prtf("COUNT: %d\nELAPSED: %.9f\n",counts[who],elap[who]);
    }

    do {
        xfset(1);

        if (elap[0] > elap[1]) {
            if (elap[1] == 0.0)
                break;
            ratio = elap[0] / elap[1];
            tag = "faster";
        }
        else {
            if (elap[0] == 0.0)
                break;
            ratio = elap[1] / elap[0];
            tag = "slower";
        }

        prtf("RATIO: %.3fX %s\n",ratio,tag);
    } while (0);

    mymtx.mtxfree();
}

// main -- main program
int
main(int argc,char **argv)
{
    char *cp;
    bigvector *vec;
    mtxctl mymtx;

    --argc;
    ++argv;

    xfinit();

    for (;  argc > 0;  --argc, ++argv) {
        cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        case 't':
            opt_xpt = 1;
            break;

        case 'v':
            opt_v = 1;
            break;

        case 'D':
            del_Y = strtol(cp + 2,&cp,10);
            del_X = strtol(cp + 1,&cp,10);
            break;

        case 'T':
            opt_T = 1;
            break;

        default:
            break;
        }
    }

#if 1
    vecall(&binaryMatrix);
    vecall(&test_1);
    vecall(&test_2);
    vecall(&test_3);
    vecall(&test_4);
    vecall(&test_5);
    vecall(&test_6);
    vecall(&test_7);
#endif

    vec = bldvec();
    vecall(vec);

    xfdone();

    return 0;
}

---

Here's the difference output between your original code and mine:

9c9,10
< ELAPSED: 0.000009060
---
> ELAPSED: 0.000000477
> RATIO: 19.000X faster
14c15
< ELAPSED: 0.000000238
---
> ELAPSED: 0.000000000
19c20
< ELAPSED: 0.000002861
---
> ELAPSED: 0.000000000
24c25,26
< ELAPSED: 0.000000715
---
> ELAPSED: 0.000000238
> RATIO: 3.000X faster
31c33,34
< ELAPSED: 0.000003099
---
> ELAPSED: 0.000000238
> RATIO: 13.000X faster
40c43,44
< ELAPSED: 0.000003815
---
> ELAPSED: 0.000000238
> RATIO: 16.000X faster
49c53,54
< ELAPSED: 0.000003815
---
> ELAPSED: 0.000000238
> RATIO: 16.000X faster
58c63,64
< ELAPSED: 0.000006199
---
> ELAPSED: 0.000000238
> RATIO: 26.000X faster
145c151,152
< ELAPSED: 0.001625061
---
> ELAPSED: 0.000070095
> RATIO: 23.184X faster