Bike Tour|Google Coding Problem


Li has planned a bike tour through the mountains of Switzerland. His tour consists of N checkpoints, numbered from 1 to N in the order he will visit them. The i-th checkpoint has a height of Hi.

google coding

A checkpoint is a peak if:

  • It is not the 1st checkpoint or the N-th checkpoint, and
  • The height of the checkpoint is strictly greater than the checkpoint immediately before it and the checkpoint immediately after it.

Please help Li find out the number of peaks.


The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The i-th integer is Hi.


For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of peaks in Li's bike tour.


Time limit: 10 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Hi ≤ 100.

3 ≤ N ≤ 5.

3 ≤ N ≤ 100.



10 20 14
7 7 7 7
10 90 20 90 10
10 3 10


Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 0
  • In sample case #1, the 2nd checkpoint is a peak.
  • In sample case #2, there are no peaks.
  • In sample case #3, the 2nd and 4th checkpoint are peaks.
  • In sample case #4, there are no peaks.
google coding

Code & Algorithm

/* author : @akash kumar */
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb push_back
#define ld long double
int countPeaks(vector<int> checkpoints) {
int peaks = 0;
for(int i = 1; i < checkpoints.size() - 1; i++) {
if(checkpoints[i-1] < checkpoints[i] && checkpoints[i+1] < checkpoints[i]) {
return peaks;
int main()
int t;
for(int i=1;i<=t;++i)
int N;
for(int i=0;i<N;++i)
cout<<"Case #"<<i<<": "<<countPeaks(checkpoints);
return 0;

For each of the checkpoints, we can determine if it is a peak in O(1) time by comparing its height to the heights of the checkpoints before and after it.

google coding

There are N checkpoints, so the total time complexity of this approach is O(N), which is sufficient for both Test Set 1 and Test Set 2.

Thank You.

Akash Kumar

Software Engineer




Student of Computer Science & Engineering at Moradabad Institute of Technology.

Love podcasts or audiobooks? Learn on the go with our new app.

What is the Future of Python in Software Testing?

Future of Python I Software Testing

Oracle Database Operator for Kubernetes — Take 2

CS50’s Introduction to Algorithms

Using CCXT for Python to Access Binance, Lykke, and more crypto-APIs

Best Way to use reddit on your Android Smartphone

Color Luminance detection using TMG39931 I2C module to use with Industrial machines

Getting Started With Serverless Framework

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Akash Kumar

Akash Kumar

Student of Computer Science & Engineering at Moradabad Institute of Technology.

More from Medium

Women Who Code Delhi Mentorship Program 4.0: Week 1

What are Coursera and its feature?

Should you start with Kotlin as a beginner coder?

The Power of Atomic Habits for Becoming a Better Software Developer