Count Peaks

28 May, 2021

Problem

Map information is given on an N*N grid. Each grid is marked with the height of that area. The number on each grid that is greater than its top, bottom, left, and right numbers is the peak area. Write a program to find out how many peak regions there are.
It is assumed that the edges of the grid are initialized to zero.
If N=5 and the number of grids is as follows, then the number of peaks is 10.

input

A natural number N is given in the first line (1<=N<=50).
From the second line to the N lines, each line is given N natural numbers. Each natural number does not exceed 100.

5
[5, 3, 7, 2, 3]
[3, 7, 1, 6, 1]
[7, 2, 5, 3, 4]
[4, 3, 6, 4, 1]
[8, 7, 3, 5, 2]

output

Print the number of peaks.

Solution

Using surrounded array 0 (n^2)

function solution(arr) {
	let answer = 0;

	let postArr = Array.from({ length: 7 }, () => [0, 0, 0, 0, 0, 0, 0]);

	for (let i = 0; i < arr.length; i++) {
		for (let j = 0; j < arr[0].length; j++) {
			postArr[i + 1][j + 1] = arr[i][j];
		}
	}

	for (let i = 1; i < postArr.length - 1; i++) {
		for (let j = 1; j < postArr[0].length - 1; j++) {
			if (
				postArr[i][j] > postArr[i][j - 1] &&
				postArr[i][j] > postArr[i][j + 1] &&
				postArr[i][j] > postArr[i + 1][j] &&
				postArr[i][j] > postArr[i - 1][j]
			)
				answer++;
		}
	}

	return answer;
}

Using dx, dy (n^3)

function solution(arr) {
	let answer = 0;
	let n = arr.length;
	let dx = [-1, 0, 1, 0];
	let dy = [0, 1, 0, -1];

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			let flag = 1;
			for (let k = 0; k < 4; k++) {
				let nx = i + dx[k];
				let ny = j + dy[k];
				if (
					nx >= 0 &&
					nx < n &&
					ny >= 0 &&
					ny < n &&
					arr[nx][ny] >= arr[i][j]
				) {
					flag = 0;
					break;
				}
			}

			if (flag) answer++;
		}
	}

	return answer;
}