Tasks Details
medium
Given N rectangular buildings of width 1, find the minimum total area of two rectangular banners that cover all of the buildings.
Task Score
100%
Correctness
100%
Performance
100%
There are N rectangular buildings standing along the road next to each other. The K-th building is of size H[K] × 1.
Because a renovation of all of the buildings is planned, we want to cover them with rectangular banners until the renovations are finished. Of course, to cover a building, the banner has to be at least as high as the building. We can cover more than one building with a banner if it is wider than 1.
For example, to cover buildings of heights 3, 1, 4 we could use a banner of size 4×3 (i.e. of height 4 and width 3), marked here in blue:
We can order at most two banners and we want to cover all of the buildings. Also, we want to minimize the amount of material needed to produce the banners.
What is the minimum total area of at most two banners which cover all of the buildings?
Write a function:
class Solution { public int solution(int[] H); }
that, given an array H consisting of N integers, returns the minimum total area of at most two banners that we will have to order.
Examples:
1. Given H = [3, 1, 4], the function should return 10. The result can be achieved by covering the first two buildings with a banner of size 3×2 and the third building with a banner of size 4×1:
2. Given H = [5, 3, 2, 4], the function should return 17. The result can be achieved by covering the first building with a banner of size 5×1 and the other buildings with a banner of size 4×3:
3. Given H = [5, 3, 5, 2, 1], your function should return 19. The result can be achieved by covering the first three buildings with a banner of size 5×3 and the other two with a banner of size 2×2:
4. Given H = [7, 7, 3, 7, 7], your function should return 35. The result can be achieved by using one banner of size 7×5:
5. Given H = [1, 1, 7, 6, 6, 6], your function should return 30. The result can be achieved by using banners of size 1×2 and 7×4:
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array H is an integer within the range [1..10,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 2 minutes
Notes
not defined yet
Code: 12:24:20 UTC,
java,
autosave
Code: 12:24:42 UTC,
java,
autosave
/**
* The challenge can be found here: https://app.codility.com/programmers/challenges/palladium2020/
*
* The goal of this challenge is to find the smallest (two) area(s) which will cover the buildings of the array H.
* The size of the coverage is defined as the highest point (building) within this area multiplied with the
* number of elements (buildings) covered by the area.
*
* Problem solution:
*
* To find the solution we must imagine every possible distribution of the left and right area within the given
* array H= | 5, 3, 5, 2, 1 | these would be:
* 1. left area = 6 (all) buildings
* 2. left area = 5, right area = 1
* 3. left area = 4, right area = 2
* 4. left area = 3, right area = 3
* ....
*
* To be able to calculate all of these we must first know which is the highest point within the mentioned areas.
* This we achieve by iterating from both the left and right end of the array and setting:
* leftMax [current size of left area] = max( leftMax[previous size] , H[current size of left area] )
* rightMax [current size of right area] = max( rightMax[previous size] , H[current size of right area] )
*
* Now, for our array H = | 5, 3, 5, 2, 1 |
* we have: leftMax ->| 5, 5, 5, 5, 5 |
* | 5, 5, 5, 2, 1 | <- rightMax
*
* Assuming now that our left coverage is covering 1 building and our right building is covering 5
* we just need to look into leftMax[0] and rightMax[1]. If we do this for all valid combinations of coverages we
* find the minimal possible coverage with a complexcity of N*2 = O(n)
*/
class Solution {
public int solution(int[] H) {
// write your code in Java SE 8
}
}
Code: 12:25:00 UTC,
java,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
/**
* The challenge can be found here: https://app.codility.com/programmers/challenges/palladium2020/
*
* The goal of this challenge is to find the smallest (two) area(s) which will cover the buildings of the array H.
* The size of the coverage is defined as the highest point (building) within this area multiplied with the
* number of elements (buildings) covered by the area.
*
* Problem solution:
*
* To find the solution we must imagine every possible distribution of the left and right area within the given
* array H= | 5, 3, 5, 2, 1 | these would be:
* 1. left area = 6 (all) buildings
* 2. left area = 5, right area = 1
* 3. left area = 4, right area = 2
* 4. left area = 3, right area = 3
* ....
*
* To be able to calculate all of these we must first know which is the highest point within the mentioned areas.
* This we achieve by iterating from both the left and right end of the array and setting:
* leftMax [current size of left area] = max( leftMax[previous size] , H[current size of left area] )
* rightMax [current size of right area] = max( rightMax[previous size] , H[current size of right area] )
*
* Now, for our array H = | 5, 3, 5, 2, 1 |
* we have: leftMax ->| 5, 5, 5, 5, 5 |
* | 5, 5, 5, 2, 1 | <- rightMax
*
* Assuming now that our left coverage is covering 1 building and our right building is covering 5
* we just need to look into leftMax[0] and rightMax[1]. If we do this for all valid combinations of coverages we
* find the minimal possible coverage with a complexcity of N*2 = O(n)
*/
class Solution {
public int solution(int[] H) {
int N = H.length;
int[] maxOfLeftCover = new int[N];
int[] maxOfRightCover = new int[N];
// Since the both areas MUST touch either boundary of the array, we can initalize them to the value of the boundaries
maxOfLeftCover[0] = H[0];
maxOfRightCover[N-1] = H[N-1];
// loop interating the array from the left and the right border. While skipping the first entry!
for ( int left = 1, right = N-2; left < H.length && right >= 0; left++, right-- ){
maxOfLeftCover[left] = Math.max( maxOfLeftCover[left-1], H[left]);
maxOfRightCover[right] = Math.max( maxOfRightCover[right +1], H[right]);
}
// We initalize the minimal required cover to the biggest possible cover, which is one cover for everything.
int minimalRequiredArea = maxOfRightCover[0] * N;
// to determine the minimal coverage we must check all other valid coverages.
for (int i = 1; i < H.length; i++) {
final int sizeOfLeftCover = maxOfLeftCover[i-1] * i;
final int sizeOfRightCover = maxOfRightCover[i] * (N-i);
minimalRequiredArea = Math.min(minimalRequiredArea, sizeOfLeftCover + sizeOfRightCover);
}
return minimalRequiredArea;
}
}
Code: 12:25:06 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
/**
* The challenge can be found here: https://app.codility.com/programmers/challenges/palladium2020/
*
* The goal of this challenge is to find the smallest (two) area(s) which will cover the buildings of the array H.
* The size of the coverage is defined as the highest point (building) within this area multiplied with the
* number of elements (buildings) covered by the area.
*
* Problem solution:
*
* To find the solution we must imagine every possible distribution of the left and right area within the given
* array H= | 5, 3, 5, 2, 1 | these would be:
* 1. left area = 6 (all) buildings
* 2. left area = 5, right area = 1
* 3. left area = 4, right area = 2
* 4. left area = 3, right area = 3
* ....
*
* To be able to calculate all of these we must first know which is the highest point within the mentioned areas.
* This we achieve by iterating from both the left and right end of the array and setting:
* leftMax [current size of left area] = max( leftMax[previous size] , H[current size of left area] )
* rightMax [current size of right area] = max( rightMax[previous size] , H[current size of right area] )
*
* Now, for our array H = | 5, 3, 5, 2, 1 |
* we have: leftMax ->| 5, 5, 5, 5, 5 |
* | 5, 5, 5, 2, 1 | <- rightMax
*
* Assuming now that our left coverage is covering 1 building and our right building is covering 5
* we just need to look into leftMax[0] and rightMax[1]. If we do this for all valid combinations of coverages we
* find the minimal possible coverage with a complexcity of N*2 = O(n)
*/
class Solution {
public int solution(int[] H) {
int N = H.length;
int[] maxOfLeftCover = new int[N];
int[] maxOfRightCover = new int[N];
// Since the both areas MUST touch either boundary of the array, we can initalize them to the value of the boundaries
maxOfLeftCover[0] = H[0];
maxOfRightCover[N-1] = H[N-1];
// loop interating the array from the left and the right border. While skipping the first entry!
for ( int left = 1, right = N-2; left < H.length && right >= 0; left++, right-- ){
maxOfLeftCover[left] = Math.max( maxOfLeftCover[left-1], H[left]);
maxOfRightCover[right] = Math.max( maxOfRightCover[right +1], H[right]);
}
// We initalize the minimal required cover to the biggest possible cover, which is one cover for everything.
int minimalRequiredArea = maxOfRightCover[0] * N;
// to determine the minimal coverage we must check all other valid coverages.
for (int i = 1; i < H.length; i++) {
final int sizeOfLeftCover = maxOfLeftCover[i-1] * i;
final int sizeOfRightCover = maxOfRightCover[i] * (N-i);
minimalRequiredArea = Math.min(minimalRequiredArea, sizeOfLeftCover + sizeOfRightCover);
}
return minimalRequiredArea;
}
}
Code: 12:25:18 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
/**
* The challenge can be found here: https://app.codility.com/programmers/challenges/palladium2020/
*
* The goal of this challenge is to find the smallest (two) area(s) which will cover the buildings of the array H.
* The size of the coverage is defined as the highest point (building) within this area multiplied with the
* number of elements (buildings) covered by the area.
*
* Problem solution:
*
* To find the solution we must imagine every possible distribution of the left and right area within the given
* array H= | 5, 3, 5, 2, 1 | these would be:
* 1. left area = 6 (all) buildings
* 2. left area = 5, right area = 1
* 3. left area = 4, right area = 2
* 4. left area = 3, right area = 3
* ....
*
* To be able to calculate all of these we must first know which is the highest point within the mentioned areas.
* This we achieve by iterating from both the left and right end of the array and setting:
* leftMax [current size of left area] = max( leftMax[previous size] , H[current size of left area] )
* rightMax [current size of right area] = max( rightMax[previous size] , H[current size of right area] )
*
* Now, for our array H = | 5, 3, 5, 2, 1 |
* we have: leftMax ->| 5, 5, 5, 5, 5 |
* | 5, 5, 5, 2, 1 | <- rightMax
*
* Assuming now that our left coverage is covering 1 building and our right building is covering 5
* we just need to look into leftMax[0] and rightMax[1]. If we do this for all valid combinations of coverages we
* find the minimal possible coverage with a complexcity of N*2 = O(n)
*/
class Solution {
public int solution(int[] H) {
int N = H.length;
int[] maxOfLeftCover = new int[N];
int[] maxOfRightCover = new int[N];
// Since the both areas MUST touch either boundary of the array, we can initalize them to the value of the boundaries
maxOfLeftCover[0] = H[0];
maxOfRightCover[N-1] = H[N-1];
// loop interating the array from the left and the right border. While skipping the first entry!
for ( int left = 1, right = N-2; left < H.length && right >= 0; left++, right-- ){
maxOfLeftCover[left] = Math.max( maxOfLeftCover[left-1], H[left]);
maxOfRightCover[right] = Math.max( maxOfRightCover[right +1], H[right]);
}
// We initalize the minimal required cover to the biggest possible cover, which is one cover for everything.
int minimalRequiredArea = maxOfRightCover[0] * N;
// to determine the minimal coverage we must check all other valid coverages.
for (int i = 1; i < H.length; i++) {
final int sizeOfLeftCover = maxOfLeftCover[i-1] * i;
final int sizeOfRightCover = maxOfRightCover[i] * (N-i);
minimalRequiredArea = Math.min(minimalRequiredArea, sizeOfLeftCover + sizeOfRightCover);
}
return minimalRequiredArea;
}
}
Code: 12:25:23 UTC,
java,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
/**
* The challenge can be found here: https://app.codility.com/programmers/challenges/palladium2020/
*
* The goal of this challenge is to find the smallest (two) area(s) which will cover the buildings of the array H.
* The size of the coverage is defined as the highest point (building) within this area multiplied with the
* number of elements (buildings) covered by the area.
*
* Problem solution:
*
* To find the solution we must imagine every possible distribution of the left and right area within the given
* array H= | 5, 3, 5, 2, 1 | these would be:
* 1. left area = 6 (all) buildings
* 2. left area = 5, right area = 1
* 3. left area = 4, right area = 2
* 4. left area = 3, right area = 3
* ....
*
* To be able to calculate all of these we must first know which is the highest point within the mentioned areas.
* This we achieve by iterating from both the left and right end of the array and setting:
* leftMax [current size of left area] = max( leftMax[previous size] , H[current size of left area] )
* rightMax [current size of right area] = max( rightMax[previous size] , H[current size of right area] )
*
* Now, for our array H = | 5, 3, 5, 2, 1 |
* we have: leftMax ->| 5, 5, 5, 5, 5 |
* | 5, 5, 5, 2, 1 | <- rightMax
*
* Assuming now that our left coverage is covering 1 building and our right building is covering 5
* we just need to look into leftMax[0] and rightMax[1]. If we do this for all valid combinations of coverages we
* find the minimal possible coverage with a complexcity of N*2 = O(n)
*/
class Solution {
public int solution(int[] H) {
int N = H.length;
int[] maxOfLeftCover = new int[N];
int[] maxOfRightCover = new int[N];
// Since the both areas MUST touch either boundary of the array, we can initalize them to the value of the boundaries
maxOfLeftCover[0] = H[0];
maxOfRightCover[N-1] = H[N-1];
// loop interating the array from the left and the right border. While skipping the first entry!
for ( int left = 1, right = N-2; left < H.length && right >= 0; left++, right-- ){
maxOfLeftCover[left] = Math.max( maxOfLeftCover[left-1], H[left]);
maxOfRightCover[right] = Math.max( maxOfRightCover[right +1], H[right]);
}
// We initalize the minimal required cover to the biggest possible cover, which is one cover for everything.
int minimalRequiredArea = maxOfRightCover[0] * N;
// to determine the minimal coverage we must check all other valid coverages.
for (int i = 1; i < H.length; i++) {
final int sizeOfLeftCover = maxOfLeftCover[i-1] * i;
final int sizeOfRightCover = maxOfRightCover[i] * (N-i);
minimalRequiredArea = Math.min(minimalRequiredArea, sizeOfLeftCover + sizeOfRightCover);
}
return minimalRequiredArea;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N) or O(N + max(H))
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
expand all
Performance tests
1.
0.020 s
OK
2.
0.024 s
OK
3.
0.024 s
OK
4.
0.024 s
OK
1.
0.244 s
OK
2.
0.244 s
OK
3.
0.256 s
OK
4.
0.244 s
OK
1.
0.244 s
OK
2.
0.244 s
OK
3.
0.224 s
OK
4.
0.224 s
OK
5.
0.244 s
OK
6.
0.244 s
OK
max_pyramid
Values in the tests are arranged into ascending or descending pyramids. N=100,000.
Values in the tests are arranged into ascending or descending pyramids. N=100,000.
✔
OK
1.
0.228 s
OK
2.
0.248 s
OK
3.
0.220 s
OK
4.
0.224 s
OK
5.
0.232 s
OK
1.
0.268 s
OK
2.
0.248 s
OK
3.
0.248 s
OK
4.
0.244 s
OK
5.
0.248 s
OK
6.
0.244 s
OK
7.
0.248 s
OK