C# Codility question number of castles how to solve it?

Question

I'm a beginner, this was my assessment question on Codility and I'm looking for solutions. I tried but couldn't get the required output. I've spent days trying to crack this but I'm unable to do so. Any solution that can help me understand what I am supposed to do would be helpful. Click here to view question on Number of Castles (part 1) (part 2)

In my solution I'm comparing two values at a time but as the given example suggests heights can be same and we have to compare with the next available value which is not same. I have no idea how to do this.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodilityPractice
{
    class Castle2
    {
        static void Main(string[] args)
        {
            int[] A = { 2, 2, 3, 4, 3, 3, 2, 2, 1, 1, 2, 5 };
            Console.WriteLine(solution(A));

            Console.Read();
        }

        static int solution(int[] A)
        {
            int hills = 0;
            int valley = 0;

            int Q = 0;
            for (int P = 0; P < A.Length; P++)
            {
                Q = P + 1;
                if(P==0)
                {
                    if (A[P + 1] > A[P])
                        valley++;
                    continue;
                }
                if(Q==A.Length-1)
                {
                    if (A[Q - 1] < A[Q])
                        hills++;

                }
                if (P > 0 && Q < A.Length-1)
                {
                    if (A[P - 1] < A[P] && A[Q + 1] < A[Q])
                    { hills++; }
                    else if (A[P - 1] > A[P] && A[Q + 1] > A[Q])
                    { valley++; }
                }

            }
            return hills + valley;

        }
    }
}

Answer 1

The way I understand the question, we are looking for a working solution, and for an explanation of the intuition behind it. In that sense, the following code should solve the problem in O(N) and O(1) time and space complexity, respectively.

    public static int calculateCastles(int[] A) {
        int N = A.length;
        if (N == 0) return 0;
        int count = 0;
        int prevValue = A[0];
        for(int idx = 1; idx < N - 1; idx++) {
            if(((A[idx] - prevValue) * (A[idx + 1] - A[idx])) < 0) {
                count++;
                prevValue = A[idx];
            }
        }
        if(count == 0){
            if(A[0] == A[N-1]) return 1;
            return 2;
        }
        return count + 2;
    }

To solve this problem, it is useful to be aware of math property that states that when you have a stationary point in a function, i.e., either a maximum or a minimum, the sign of the derivative switches at that point. In other words, if the function was increasing (decreasing) right before reaching the point and then starts decreasing (increasing) right after it, then you have a maximum/peak (minimum/valley) at the point.

My solution basically itereates through the array and checks how many times the previous property holds. In particular, the condition ((A[idx] - prevValue) * (A[idx + 1] - A[idx])) < 0 represents a very convenient way to test for that. Note that:

• prevValue keeps track of the height of the last min/max discovered, and is initially set to A[0];
• (A[idx] - prevValue) represents the derivative before idx, and;
• (A[idx + 1] - A[idx]) is the derivative after idx.

If the funtion is monotonically increasing or decreasing, both factors will be positive and negative, respectively. This means that their product is positive. On the other hand, if at idx you have a valley, you go down and then up, so (A[idx] - prevValue) has to be negative, and (A[idx + 1] - A[idx]) has to be positve. Their product is thus negative. A similar analysis can be made for peaks.

Try to understand why we need to keep track of prevVal instead of simply using (A[idx] - A[idx - 1]). Also, an interesting point to note is that when the product of the aforementioned factors is exactly 0, then we are in a flat area, and we are simply moving forward without adding to the count.

Lastly, the condition at the end is testing for rather edge cases. If the previous loop did not find any valley or peak, there are two options:

• either we are in a completely flat region such that A[0] == A[N-1] and thus only 1 castle can be constructed, e.g. [4, 4, 4] or;
• we are in a region with two flat areas, e.g. [1, 1, 3, 3] or [1, -5], and thus we can construct two castles.

Finally, if our loop did actually detect any valley or peak, then besides this count, we also need to take into consideration the castle that will be constructed at each the extremes of the terrain, and sum 2.