Fish eat fish

We have a bunch of fishes (there could be up to 100,000) in a very narrow river, each of them with a different weight (represented by a non negative integer up to one billion). Any single fish move upstream or downstream (0 means up, 1 down). If two fishes meet (one moving up, the other moving down) the smaller one is eaten by the bigger. How many fishes are going to survive?

You can find this problem in the Codility train page, under the Stacks and Queues section, nickname Fish.

To better think about a solution, I have taken the one proposed in the problem description and converted it to a GoogleTest for C++, then adding the ones that looked interesting to me. Here is a selection of them:

int solution(std::vector<int>& sizes, std::vector<int>& directions);

TEST(Fish, Given) // 1
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);

    int b[] = { 0, 1, 0, 0, 0 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(2, solution(sizes, directions));
}

TEST(Fish, SameDirection) // 2
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);

    std::vector<int> directions(5);

    ASSERT_EQ(5, solution(sizes, directions));
}

TEST(Fish, Mixed) // 3
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);
    int b[] = { 0, 1, 0, 1, 0 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(2, solution(sizes, directions));
}

TEST(Fish, NoMeeting) // 4
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);
    int b[] = { 0, 0, 0, 1, 1 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(5, solution(sizes, directions));
}

TEST(Fish, Pilot) // 5
{
    int a[] = { 1, 5, 3, 4, 2 };
    std::vector<int> sizes(a, a + 5);
    int b[] = { 1, 1, 0, 0, 0 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(2, solution(sizes, directions));
}

1. All the fish is going upstream but the second one, that weights 3. It is going to eat the third and forth, but it is going to be eaten by the fifth. In the end just two fishes are going to survive, the first and the last one.
2. The fish is compactly moving upstream, all of them should survive.
3. Mixed situation, only two fishes are going to survive.
4. The school is parted in two groups that are not meant to cross.
5. This is the one I found most interesting. The first two fishes are moving downwards, against the other three ones. The first one is so thin that would usually have no chance to survive, but it has just after it a big brother that is going to shield it to any attack. So, against all odds, it survives too.

Then I have written my first solution, based on the idea of checking each element against any other fish it is going to meet, keep track of their status in a vector of boolean and then sum up all the surviving fishes.

int solution(std::vector<int>& sizes, std::vector<int>& directions)
{
    std::vector<bool> alive(sizes.size(), true); // 1

    for (unsigned i = 0; i < sizes.size(); ++i) // 2
    {
        if (directions[i] == 0) // 3
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (directions[j] == 1)
                    alive[sizes[i] < sizes[j] ? i : j] = false;
                if (sizes[i] < sizes[j])
                    break;
            }
        }
        else // 4
        {
            for (unsigned j = i + 1; j < sizes.size(); ++j)
            {
                if (directions[j] == 0)
                    alive[sizes[i] < sizes[j] ? i : j] = false;
                if (sizes[i] < sizes[j])
                    break;
            }
        }
    }

    return std::accumulate(alive.begin(), alive.end(), 0); // 5
}

1. Initially, are the fishes are alive.
2. I am checking any fish against the ones that are upwards or downwards, accordingly to its moving direction.
3. My current fish is moving upstream. Let's compare it against each fish on its left, starting from the closest one. I break the loop in case it gets eaten by a bigger fish.
4. Same as above, but the current fish has to fight against all the other guys downstream.
5. Finally it is just a matter of counting how many of them are still alive.

Normally this solution works fine, however in the worst case scenario the internal loop involves a number of fish in the order of the collection size, leading to an O(N**2) time complexity that makes this algorithm unacceptably slow.

Think for instance to this innocuous-looking test case:

TEST(Fish, Big)
{
    std::vector<int> sizes(100000);
    for(unsigned i = 0; i < sizes.size(); ++i)
        sizes[i] = i + 1;
    std::vector<int> directions(100000);

    ASSERT_EQ(100000, solution(sizes, directions));
}

One hundred thousand fishes, all of them going in the same direction. A human being could give the answer in the blink of an eye. The above solution, however, painfully check all the right elements to any fish in the school.

Can we do better than this? Yes. As you would see in the next post, it is just a matter of adding a bit of intelligence to the algorithm to get, even in the worst cases, a linear(ish) time complexity.