in c++

Use the positions of the minimum and maximum elements.

There are only 3 possible optimal ways:

1. Remove both from the front
2. Remove both from the back
3. Remove one from the front and the other from the back

So if:

• l = min(minIndex, maxIndex)
• r = max(minIndex, maxIndex)

Then:

• Front only: r + 1
• Back only: n - l
• Mixed: (l + 1) + (n - r)

Take the minimum of these 3.

C++ code

cpp
#include <bits/stdc++.h>
using namespace std;

/*
 * Complete the 'minimum_removals' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY nums as parameter.
 */

int minimum_removals(vector<int> nums) {
    int n = nums.size();
    
    int mnIdx = 0, mxIdx = 0;
    
    for (int i = 1; i < n; i++) {
        if (nums[i] < nums[mnIdx]) mnIdx = i;
        if (nums[i] > nums[mxIdx]) mxIdx = i;
    }
    
    int l = min(mnIdx, mxIdx);
    int r = max(mnIdx, mxIdx);
    
    int removeFromFront = r + 1;
    int removeFromBack = n - l;
    int removeFromBoth = (l + 1) + (n - r);
    
    return min({removeFromFront, removeFromBack, removeFromBoth});
}

Example

For: [2, 10, 7, 5, 4, 1, 8, 6]

• max = 10 at index 1
• min = 1 at index 5

So:

• front only = 5 + 1 = 6
• back only = 8 - 1 = 7
• both sides = (1 + 1) + (8 - 5) = 2 + 3 = 5

Answer = 5

If you want, I can also give the full main() version for direct submission.

Use binary search on P and, for each P, check whether there exists a P x P square whose every element is >= P.

A check for fixed P becomes:

• convert the matrix logically into 1 where a[i][j] >= P, else 0
• find whether there is a square of size at least P made only of 1s

That can be done with the standard DP for largest square of 1s.

C++ code

cpp
#include <bits/stdc++.h>
using namespace std;

bool canMakeSquare(const vector<vector<int>>& a, int n, int m, int p) {
    vector<int> prev(m + 1, 0), cur(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        fill(cur.begin(), cur.end(), 0);

        for (int j = 1; j <= m; j++) {
            if (a[i - 1][j - 1] >= p) {
                cur[j] = 1 + min({cur[j - 1], prev[j], prev[j - 1]});
                if (cur[j] >= p) return true;
            } else {
                cur[j] = 0;
            }
        }
        prev.swap(cur);
    }
    return false;
}

int maximumP(vector<vector<int>>& a) {
    int n = a.size();
    int m = a[0].size();

    int low = 1, high = min(n, m), ans = 0;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (canMakeSquare(a, n, m, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    cout << maximumP(a) << '\n';
    return 0;
}

How it works

For a fixed P:

• if a[i][j] >= P, treat it as usable
• dp[i][j] stores the side length of the largest all-usable square ending at (i, j)
• recurrence:

cpp
dp[i][j] = 1 + min(top, left, topLeft)

If any dp[i][j] >= P, then a valid P x P square exists.

Complexity

• Each check: O(N * M)
• Binary search over P: O(log(min(N, M)))

So total:

cpp
O(N * M * log(min(N, M)))

If the platform gives a specific function stub, send that stub and I’ll fit this exactly into it.

Paste this into the stub:

cpp
int canMake(vector<vector<long>> &arr, int p) {
    int n = arr.size();
    int m = arr[0].size();

    vector<int> prev(m + 1, 0), cur(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        fill(cur.begin(), cur.end(), 0);

        for (int j = 1; j <= m; j++) {
            if (arr[i - 1][j - 1] >= p) {
                cur[j] = 1 + min({cur[j - 1], prev[j], prev[j - 1]});
                if (cur[j] >= p) return 1;
            }
        }

        prev.swap(cur);
    }

    return 0;
}

int findSquareSize(vector<vector<long>> arr) {
    int n = arr.size();
    int m = arr[0].size();

    int low = 1, high = min(n, m), ans = 0;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (canMake(arr, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return ans;
}

Idea

For a fixed p, treat each cell as usable if arr[i][j] >= p.

Then check whether there exists a square of size at least p made only of usable cells using DP:

cpp
dp[i][j] = 1 + min(left, up, diagonal)

Then binary search on p.

Complexity

• Each check: O(N*M)
• Binary search: O(log(min(N, M)))

Total: O(N*M*log(min(N,M)))

If you want, I can also give the same solution as a complete runnable main() program.