You are given an array of size N You need to change this array into a mountain

Mountain Array Problem

You are given an array of size N. You need to change this array into a mountain.

Infosys HackWithInfy 2025

By mountain, we mean the ends of the array should have equal elements. As we move towards the middle from both ends, the next element is just one more than the previous one.

Examples of valid mountain arrays:

[1, 2, 3, 2, 1]

[6, 7, 8, 8, 7, 6]

Examples of invalid mountain arrays:

[1, 2, 4, 2, 1] (is not a mountain because from 2 to 4 the difference is 2)

[1, 2, 3, 1] (is also not a mountain because the elements 2 and 3 are not equal from both ends.)

Input Format

• N - The first line contains an integer, N, denoting the number of elements in the array. (N :: 1 -> 10^5).
• array - Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing the i-th element of the array. array[i] :: 1 -> 10^6

Output Format

An integer representing the minimum number of elements that should be changed to make the array a mountain.

Example Cases

Case #1

Input:

5
1
2
3
4
5

Output:

2

Explanation: array = [1, 2, 3, 4, 5]. We can change 4 and 5 to make it [1, 2, 3, 2, 1].

Case #2

Input:

9
1
1
1
2
3
2
1
1
1

Output:

4

Explanation: array = [1, 1, 1, 2, 3, 2, 1, 1, 1]. We can change the array to [-1, 0, 1, 2, 3, 2, 1, 0, -1].

Case #3

Input:

6
3
3
4
4
5
5

Output:

3

Explanation: array = [3, 3, 4, 4, 5, 5]. We can change the array to [2, 3, 4, 4, 3, 2].

Infosys HackWithInfy 2025

Java Code - Mountain Array

import java.util.*;

public class MountainArray {

    public static int minChangesToMountain(int n, int[] arr) {

        if (n <= 2) return 0;

        int minChanges = Integer.MAX_VALUE;

        for (int peakPos = 1; peakPos < n-1; peakPos++) {

            int currentChanges = 0;

            int[] tempArr = new int[n];

            int peakValue = arr[peakPos];

            for (int i = peakPos - 1; i >= 0; i--) {

                int requiredValue = peakValue - (peakPos - i);

                if (arr[i] != requiredValue) {

                    currentChanges++;

                }

                tempArr[i] = requiredValue;

            }

            for (int i = peakPos + 1; i < n; i++) {

                int requiredValue = peakValue - (i - peakPos);

                if (arr[i] != requiredValue) {

                    currentChanges++;

                }

                tempArr[i] = requiredValue;

            }

            boolean isValid = true;

            for (int val : tempArr) {

                if (val < 0) {

                    isValid = false;

                    break;

                }

            }

            if (isValid) {

                minChanges = Math.min(minChanges, currentChanges);

            }

        }

        return minChanges == Integer.MAX_VALUE ? -1 : minChanges;

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {

            arr[i] = scanner.nextInt();

        }

        int result = minChangesToMountain(n, arr);

        System.out.println(result);

        scanner.close();

    }

}

Mountain Array Solution

This solution:

• Takes input for array size and array elements
• For each possible peak position:
  • Calculates required values for left and right sides
  • Counts minimum changes needed for that peak position
  • Ensures no negative values are required
• Returns the minimum number of changes needed across all valid peak positions

Algorithm Explanation:

• Trying each position as a potential peak
• For each peak position, calculating what values are needed on both sides to form a valid mountain
• Counting how many changes would be needed to achieve those values
• Taking the minimum number of changes across all valid peak positions

Example Cases:

• Case #1: Returns 2 (changing 4, 5 to 2, 1)
• Case #2: Returns 4 (changing values to form a valid mountain)
• Case #3: Returns 3 (changing values to form 2, 3, 4, 4, 3, 2)

Infosys HackWithInfy 2025

Python Code: Minimum Changes to Mountain

def min_changes_to_mountain(n: int, arr: list) -> int:

    if n <= 2:

        return 0

    min_changes = float('inf')

    # Try each possible peak position
    for peak_pos in range(1, n-1):

        current_changes = 0
        temp_arr = [0] * n
        peak_value = arr[peak_pos]

        # Left side of peak
        for i in range(peak_pos - 1, -1, -1):
            required_value = peak_value - (peak_pos - i)
            if arr[i] != required_value:
                current_changes += 1
            temp_arr[i] = required_value

        # Right side of peak
        for i in range(peak_pos + 1, n):
            required_value = peak_value - (i - peak_pos)
            if arr[i] != required_value:
                current_changes += 1
            temp_arr[i] = required_value

        # Check if this is a valid mountain (no negative values)
        if all(val >= 0 for val in temp_arr):
            min_changes = min(min_changes, current_changes)

    return min_changes if min_changes != float('inf') else -1

def main():

    # Read input
    n = int(input())
    arr = []

    for _ in range(n):
        arr.append(int(input()))

    # Calculate and print result
    result = min_changes_to_mountain(n, arr)
    print(result)

if __name__ == "__main__":
    main()

Infosys HackWithInfy 2025

Python Solution: Minimum Changes to Mountain Array

This Python solution follows the same logic as the Java version but with Python's cleaner syntax. Here's how it works:

The min_changes_to_mountain function:

• Takes array size n and the array arr as input.
• Returns the minimum number of changes needed to make a mountain array.

For each possible peak position, it:

• Creates a temporary array to store required values.
• Calculates required values for the left side (decreasing from peak).
• Calculates required values for the right side (decreasing from peak).
• Counts how many changes are needed.
• Checks if the solution is valid (no negative values).

Infosys HackWithInfy 2025

Infosys HackWithInfy 2025