List value reduction algorithm

Question

Forgive me, but I am very confused and I cannot find any sources that are pointing my in the right direction.

Given list of n elements:

[3, 6, 5, 1]

Reduce the values to be no larger than the size of the list while keeping prioritization values relative to one another (In their original order).

Constraints:

• Order must be maintained
• Elements are >= 0
• Distinct values

I am trying to stay away from sorting and creating a new list, but modifying the list in-place.

What my expected outcome should be:

[1, 3, 2, 0]

Is there an algorithm that exists for this problem?

Answer 1

You could do this in O(n^2).

Just go through the list n times, setting the minimum element(while >= i) to i each time, where i starts at 0 and increments to n-1

I suspect you're looking for something better than that, but I'm not sure how much better you can do in-place.

Example:

Input: 3  6  5  1

3  6  5  0*
1* 6  5  0
1  6  2* 0
1  3* 2  0

Note: this assumes elements are >= 0 and distinct

Answer 2

There may be one, but you don't need it if you think about the steps needed to take to solve this problem.

First, you know that each value in the array cannot be greater than 4, since that is the size in this particular example.

You need to go through each number in the array and with a if condition check to see if the number is greater; if it is then you'll need to decrement it until it is meets the correct condition (in this case, that it is less than 4).

Perform these steps for each index of the array. As far as order, don't swap any indices, since you must retain the original order. Hope that helps!