IBM Online Assessment Coding Problem LeetCode-style Experience

Problem Statement Given an integer array nums, you are tasked with sorting it in non-decreasing order using the minimum number of specific operations. If sorting is impossible,

return -1. **The

Problem Statement Given an integer array nums, you are tasked with sorting it in non-decreasing order using the minimum number of specific operations. If sorting is impossible,

return -1.

The Operation: 1. Move the element at index 0 (the first element) to the end of the array. 2. Repeatedly swap this newly moved element to the left with its preceding element as long as the moved element is not strictly greater than the one to its left. (i.e., swap if current <= previous, stop if current > previous).

Example: *

Input: nums = [2, 1, 3] *

Step 1: Move 2 to the end: [1, 3, 2] *

Step 2: Compare 2 with 3. Since 2 < 3, swap left: [1, 2, 3] *

Step 3: Compare 2 with 1. Since 2 > 1, stop. *

Result: [1, 2, 3] (Sorted). *

Output: 1 (1 operation required).

Solution

Approach The operation described functions similarly to a step in an Insertion Sort, where an element is taken and placed into its correct relative position among the elements currently in the array. To minimize the number of operations, we must maximize the number of elements that do not move. The elements that remain in place must already form a relative non-decreasing sequence. Therefore, the problem reduces to finding the

Longest Non-Decreasing Subsequence (LNDS) of the original array. The minimum number of operations is the total number of elements minus the length of the LNDS.

Algorithm: 1. Initialize an empty list sub to build the subsequence. 2. Iterate through each number x in nums. 3. If sub is empty or x is greater than or equal to the last element of sub, append x. 4. Otherwise, find the smallest element in sub that is strictly greater than x and replace it with x (this maintains the potential to extend the sequence length, a standard technique for finding LIS/LNDS). 5. The result is len(nums) - len(sub). ### Python Implementation

python import bisect def min_operations_to_sort(nums): if not nums:

**return** 0 # List to store the Longest Non-Decreasing Subsequence sub = [] for x in nums: # If sub is empty or x is >= the last element, extend the subsequence if not sub or x >= sub[-1]: sub.append(x) else: # Find the first element in sub that is > x and replace it # bisect_right is used to handle duplicates correctly for non-decreasing order idx = bisect.bisect_right(sub, x) if idx < len(sub): sub[idx] = x # Minimum operations = Total elements - Elements we keep (LNDS)

**return** len(nums) - len(sub)

**Example **Usage: # print(min_operations_to_sort([2, 1, 3]))

**Output**: 1