How to find the smallest strokes needed to draw a horizon with time and storage complexity == O (N)

Question

I recently got an online coding test. I got 100% for correctness, but 0% for performance. How could I write my solution to increase productivity? I can’t believe that I scored 0%.

[Coding Test]

You want to draw a horizon line using continuous horizontal strokes consisting of rectangular buildings located in one line. Each horizontal stroke has a unit of height and is arbitrarily wide. Buildings have the same width, but they can have different heights. The shape of the horizon is shown as array A, the elements of which determine the heights in units of successive buildings.

For instance:

A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 3 A[4] = 2 A[5] = 1 

Would create a horizon line (5 strokes required):

Write a function that defines a non-empty array A, consisting of N integers, returns the minimum number of horizontal strokes needed to draw the horizon line represented by the array. The function should return -1 if the number of strokes exceeds 1,000,000,000. The complexity of the time must be O (N). The complexity of the space must be O (N) outside the input store (not counting the storage needed for the input arguments).

 public static int solution(int[] A) { int largestNumber = 0; for (int i = 0; i < A.Length; i++) { if(A[i] > largestNumber) { largestNumber = A[i]; } } int strokeCount = 0; for (int i = 0; i <= largestNumber; i++) { bool highestMatch = false; for (int j = 0; j < A.Length; j++) { if (!highestMatch && A[j] >= (i + 1)) { strokeCount++; highestMatch = true; } else { if (highestMatch && A[j] < (i + 1)) { highestMatch = false; } } } } if(strokeCount > 1000000000) { return -1; } else { return strokeCount; } } 

Answer 1

You may notice that if A[n+1] > A[n] , we must start strokes A[n+1]-A[n] . But if A[n+1] < A[n] , we must put an end to A[n]-A[n+1] .

Since we are only interested in the number of strokes started, we could sum A[n+1]-A[n] when the condition A[n+1] > A[n] is fulfilled.

This means that we perform no more than N-1 sums, that is, O(N) .

 class Program { public static int ComputeNumberOfStrokes(List<int> skyline) { const int MAX = 1000000001; var strokes = skyline.Zip(skyline.Skip(1), (a, b) => b - a) .Where(d => d > 0) .Aggregate(skyline[0], (a, b) => Math.Min(a + b, MAX)); return strokes >= MAX ? -1 : strokes; } static void Main(string[] args) { var skyline1 = new List<int> { 1, 3, 1, 3, 2, 1 }; var skyline2 = new List<int> { 1, 2, 3, 4, 3, 2, 1 }; var skyline3 = new List<int> { 1, 2, 3, 4, 1, 2, 3, 4 }; Console.WriteLine(ComputeNumberOfStrokes(skyline1)); Console.WriteLine(ComputeNumberOfStrokes(skyline2)); Console.WriteLine(ComputeNumberOfStrokes(skyline3)); Console.In.ReadLine(); } } 

This will return 5 4 7 . What are the expected results.

Answer 2

A very simple solution that performs a single pass in linear time with constant space:

 int strokeCount(IEnumerable<int> skyline) { int level = 0; int strokes = 0; foreach (int height in skyline) { // if the building is higher than the current level, we need // to make (level - height) new strokes if (height > level) { strokes += height - level; level = height; } // if the building is lower than the current level, we need // to end the difference in strokes, but this doesn't cost // "new" ones else if (height < level) { level = height; } // if we stay on the same level, don't do anything // explicitely check for the maximum stroke count for every // building, so we can abort early if (strokes > 1000000000) return -1; } return strokes; } 

Answer 3

Here's a simpler solution in javascript

 function solution(A) { var strokesCount = 0; var currStrokeHeight = 0; for (var i = 0; i < A.length; i++) { if (currStrokeHeight < A[i]) { // next building is taller than our current stroke height // add the difference between heights to strokesCount strokesCount += A[i] - currStrokeHeight; // edge case if (strokesCount > 1000000000) { return -1; } } currStrokeHeight = A[i]; } return strokesCount; }