Find minimum operations to make array sorted

Q: Find minimum operations to make array sorted

This is a Coding & Algorithms interview question from IBM for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

You are given an integer array a of length n. Define one operation as follows:

Remove the first element x = a[0] .
Append x to the end of the array.
Starting from the end, repeatedly swap x leftward while it has a left neighbor and x is smaller than that left neighbor (i.e., while a[i] < a[i-1] ). Stop when either:
- x reaches index 0 , or
- a[i-1] <= a[i] .

After each operation, the array is updated deterministically.

Task

Return the minimum number of operations needed to make the array non-decreasing (i.e., for all i, a[i] <= a[i+1]). If it is impossible for the array to ever become non-decreasing under repeated operations, return -1.

Function signature (example)

Implement a function like:

min_ops_to_nondecreasing(a: List[int]) -> int

Assumptions / constraints (for interview)

1 <= n <= 2e5
a[i] fits in 32-bit signed integer
Time complexity should be better than simulating full array states.

Find minimum operations to make array sorted

Problem

Task

Function signature (example)

Assumptions / constraints (for interview)

Comments (0)