Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

UPCOMING CHALLENGES:

CURRENT CHALLENGES:

Cuprum 2018

PAST CHALLENGES

Cutting Complexity

Nickel 2018

Cobaltum 2018

Ferrum 2018

Manganum 2017

Chromium 2017

Vanadium 2016

Titanium 2016

Scandium 2016

Calcium 2015

Kalium 2015

Argon 2015

Chlorum 2014

Sulphur 2014

Phosphorus 2014

Silicium 2014

Aluminium 2014

Magnesium 2014

Natrium 2014

Neon 2014

Fluorum 2014

Oxygenium 2014

Nitrogenium 2013

Carbo 2013

Boron 2013

Beryllium 2013

Lithium 2013

Helium 2013

Hydrogenium 2013

Omega 2013

Psi 2012

Chi 2012

Phi 2012

Upsilon 2012

Tau 2012

Sigma 2012

Rho 2012

Pi 2012

Omicron 2012

Xi 2012

Nu 2011

Mu 2011

Lambda 2011

Kappa 2011

Iota 2011

Theta 2011

Eta 2011

Zeta 2011

Epsilon 2011

Delta 2011

Gamma 2011

Beta 2010

Alpha 2010

ambitious

Count the number of islands on consecutive days.

Programming language:
Spoken language:

The city of Codicity is located at the seaside. The city area comprises N plots located along a boulevard on one side of the city. Each plot is flat, but different plots have different heights above the sea level. The relative heights of the consecutive plots are given in the form of a non-empty array A of N integers.

The sea level changes constantly and many plots are sometimes under water. Water levels on consecutive days are given in the form of a non-empty array B of M integers.

A *slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Assume that the following declarations are given:

struct Results { int * C; int M; // Length of the array };

Write a function:

struct Results solution(int A[], int N, int B[], int M);

that, given a non-empty array A of N integers and a non-empty array B of M integers, returns a sequence consisting of M integers representing the number of islands on consecutive days.

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));
- expected worst-case space complexity is O(N+M+max(A)+max(B)) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

The city of Codicity is located at the seaside. The city area comprises N plots located along a boulevard on one side of the city. Each plot is flat, but different plots have different heights above the sea level. The relative heights of the consecutive plots are given in the form of a non-empty array A of N integers.

The sea level changes constantly and many plots are sometimes under water. Water levels on consecutive days are given in the form of a non-empty array B of M integers.

A *slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

vector<int> solution(vector<int> &A, vector<int> &B);

that, given a non-empty array A of N integers and a non-empty array B of M integers, returns a sequence consisting of M integers representing the number of islands on consecutive days.

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));
- expected worst-case space complexity is O(N+M+max(A)+max(B)) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

The city of Codicity is located at the seaside. The city area comprises N plots located along a boulevard on one side of the city. Each plot is flat, but different plots have different heights above the sea level. The relative heights of the consecutive plots are given in the form of a non-empty array A of N integers.

The sea level changes constantly and many plots are sometimes under water. Water levels on consecutive days are given in the form of a non-empty array B of M integers.

A *slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

class Solution { public int[] solution(int[] A, int[] B); }

that, given a non-empty array A of N integers and a non-empty array B of M integers, returns a sequence consisting of M integers representing the number of islands on consecutive days.

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));
- expected worst-case space complexity is O(N+M+max(A)+max(B)) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

func Solution(A []int, B []int) []int

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

class Solution { public int[] solution(int[] A, int[] B); }

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

function solution(A, B);

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

function solution(A, B)

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

Note: All arrays in this task are zero-indexed, unlike the common Lua convention. You can use `#A` to get the length of the array A.

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

NSMutableArray * solution(NSMutableArray *A, NSMutableArray *B);

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Assume that the following declarations are given:

Results = record C : array of longint; M : longint; {Length of the array} end;

Write a function:

function solution(A: array of longint; N: longint; B: array of longint; M: longint): Results;

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

function solution($A, $B);

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

sub solution { my ($A, $B)=@_; my @A=@$A; my @B=@$B; ... }

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

def solution(A, B)

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

def solution(a, b)

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

object Solution { def solution(a: Array[Int], b: Array[Int]): Array[Int] }

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

public func solution(inout A : [Int], inout _ B : [Int]) -> [Int]

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

public func solution(_ A : inout [Int], _ B : inout [Int]) -> [Int]

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

*slice* of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An *island* is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

- P = 0 or A[P − 1] ≤ K
- Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

We have the following number of islands on consecutive days:

- on the first day there is only 1 island: (0, 4),
- on the second day there are 2 islands: (0, 0) and (2, 4),
- on the third day there are 2 islands: (2, 2) and (4, 4),
- on the fourth day there aren't any islands,
- on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

Private Function solution(A As Integer(), B As Integer()) As Integer()

The sequence should be returned as:

- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).

For example, given:

the function should return the array [1, 2, 2, 0, 2], as explained above.

Assume that:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B is an integer within the range [0..100,000].

Complexity:

- expected worst-case time complexity is O(N+M+max(A)+max(B));

Information about upcoming challenges, solutions and lessons directly in your inbox.

© 2009–2018 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN