Search code examples
algorithmlistmutation

List value reduction algorithm

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?

Solution

  • 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