How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at IBM.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at IBM during technical interviews.

Find minimum operations to make array sorted

Company: IBM

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

## Problem You are given an integer array `a` of length `n`. Define **one operation** as follows: 1. Remove the first element `x = a[0]`. 2. Append `x` to the end of the array. 3. 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.

Quick Answer: This question evaluates a candidate's competence in array manipulation, algorithmic optimization, and reasoning about deterministic, operation-driven state transitions.

You are given an integer array `a` of length `n`. Define **one operation** as follows: 1. Remove the first element `x = a[0]`. 2. Append `x` to the end of the array. 3. Starting from the end, repeatedly swap `x` leftward **while** it has a left neighbor and `x` is **strictly 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]`. Intuitively, each operation pops the front element and insertion-sorts it back into the array from the right side. After each operation the array is updated deterministically. **Task:** Return the **minimum number of operations** needed to make the array **non-decreasing** (`a[i] <= a[i+1]` for all `i`). If the array can never become non-decreasing under repeated operations, return `-1`. Key fact that makes this tractable: a solvable array always becomes sorted within `n` operations. If it isn't sorted after `n` operations, the global minimum has cycled back to the front unchanged and the process loops forever, so the answer is `-1`.

Constraints

1 <= n <= 2 * 10^5
a[i] fits in a 32-bit signed integer
An empty array and a single-element array are already non-decreasing (answer 0)
If the array never becomes non-decreasing, return -1

Examples

Input: ([3, 1, 2],)

Expected Output: 1

Explanation: Pop 3, append -> [1,2,3]; 3 stays at the end (1<=2<=3). Array is now sorted after 1 operation.

Input: ([1, 2, 3, 4],)

Expected Output: 0

Explanation: Already non-decreasing, so 0 operations are needed.

Input: ([5],)

Expected Output: 0

Explanation: A single element is trivially non-decreasing.

Input: ([],)

Expected Output: 0

Explanation: An empty array is non-decreasing by definition.

Input: ([2, 1],)

Expected Output: 1

Explanation: Pop 2, append -> [1,2]; sorted after 1 operation.

Input: ([0, 3, 2, 4, 0],)

Expected Output: 4

Explanation: States: [3,2,4,0,0] -> [2,4,0,0,3] -> [4,0,0,2,3] -> [0,0,2,3,4]. Sorted after 4 operations.

Input: ([4, 3, 2, 1],)

Expected Output: 3

Explanation: Reverse-sorted: [3,2,1,4] -> [2,1,3,4] -> [1,2,3,4]. Sorted after 3 operations.

Input: ([0, 4, 2, 3],)

Expected Output: -1

Explanation: The minimum 0 is already at the front; popping it and bubbling sends it back to index 0 unchanged, so the array can never sort. Return -1.

Input: ([2, 2, 2],)

Expected Output: 0

Explanation: All equal elements are already non-decreasing.

Input: ([1, 4, 3, 2],)

Expected Output: -1

Explanation: The trajectory cycles without ever reaching the sorted order, so it is impossible.

Input: ([-1, -3, -2],)

Expected Output: 1

Explanation: Negatives work the same: pop -1, append -> [-3,-2,-1]; sorted after 1 operation.

Input: ([3, 3, 0, 0],)

Expected Output: 2

Explanation: Pop 3 -> [3,0,0,3]; pop 3 -> [0,0,3,3]. Sorted after 2 operations (duplicates and ties handled).

Hints

Each operation is just: pop the front element and insertion-sort it back in from the right. The relative order of the other elements never changes.
If the array is solvable, it becomes sorted within n operations. Convince yourself: once the global minimum reaches the front of an unsorted array, it bubbles all the way to index 0 and the array is unchanged, so the process cycles.
That gives a clean termination rule: simulate at most n operations. If it is sorted at step k, return k; if it is still unsorted after n operations, return -1.

Quick Overview

This question evaluates a candidate's competence in array manipulation, algorithmic optimization, and reasoning about deterministic, operation-driven state transitions.