JP Morgan OA-2 2022

Problem Description

Write a function:

int MinSizeArray(int* arr, int n, int k);

Parameters:

• The function takes in an array arr of n positive integers and a positive integer k as inputs.

Task:

Remove elements from the array based on the following rules:

1. In one turn, exactly three consecutive elements are removed from the array.
2. The elements being removed must be adjacent, meaning you can remove elements arr[i], arr[i+1], arr[i+2] if:
   • The second element is exactly k more than the first: arr[i+1] - arr[i] = k
   • The third element is exactly k more than the second: arr[i+2] - arr[i+1] = k

The goal is to keep removing triplets as long as possible and return the size of the smallest possible array.

Return:

• If no elements can be removed, return the size of the smallest possible array after all valid removals.
• If the array is already empty, return -1.

Example 1:

Input:
k = 2
arr = [2, 4, 6, 8, 10, 12, 8, 10, 6, 8]

Output:
1

Explanation:
Here’s how we can remove elements:

• First, remove the triplet (8, 10, 12) at indices (3, 4, 5), leaving [2, 4, 6, 8, 10, 6, 8].
• Next, remove the triplet (6, 8, 10) at indices (2, 3, 4), leaving [2, 4, 6, 8].
• Finally, remove the triplet (2, 4, 6) at indices (0, 1, 2), leaving [8].
• The smallest possible array is of size 1, so the output is 1.

Example 2:

Input:
k = 1
arr = [12, 13, 14, 15, 16, 19]

Output:
3

Explanation:
In this case, no valid triplets can be removed, so the smallest possible array size remains 3.