ArraySorting | Topcoder Archive

Problem Statement

You are given the int[] A. All elements of A are positive integers not exceeding 2000.

You can perform several operations on this array. In each operation you can take any element of A and replace it by any new value from the range [1,2000].

Using as few such operations as possible, convert A into an array that is sorted in non-decreasing order. Return the sorted array you produced. If there are multiple correct answers, return the lexicographically smallest one among them.

Definition

Class:: ArraySorting
Method:: arraySort
Parameters:: int[]
Returns:: int[]
Method signature:: int[] arraySort(int[] A)
(be sure your method is public)

Notes

Given two distinct arrays with the same number of elements, the lexicographically smaller one is the one that has a smaller value at the first index at which they differ.

Constraints

A will contain between 1 and 2000 elements,
Each element of A will be between 1 and 2000, inclusive.

Examples

```
{ 10, 8 }
```
```
Returns: {1, 8 }
```
The sequence is not sorted, so we need to make at least one change. There are multiple ways how to make it sorted in exactly one change. For example, we could produce {3, 8}, {10, 10}, or {10, 470}. The lexicographically smallest sorted sequence that can be produced in one step is obtained by changing the 10 to a 1.
```
{ 6, 9 }
```
```
Returns: {6, 9 }
```
This sequence is already sorted, so no changes are needed.
```
{ 9, 8, 10, 4 }
```
```
Returns: {1, 8, 10, 10 }
```
The minimum number of changes is two. The optimal way to perform the two changes is to replace the 9 by a 1 and to replace the 4 by a 10.
```
{ 3, 7, 7, 7, 6 }
```
```
Returns: {3, 7, 7, 7, 7 }
```
In this case, the input sequence can be turned into a non-decreasing sequence in a single operation: by changing the last element to a 7 (or something bigger).

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.