Quick Overview

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

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.

Hints

  1. 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.
  2. 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.
  3. 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.

Loading coding console...