python - Print the minimum number of moves required such that all the elements are equal to minimum element

Question

In one move we can make it equal to the 2nd maximum element and have to make all elements equal to the minimum element. My code is given below it works fine but I want to reduce its time complexity.

def No_Books(arr, n):
    arr = sorted(arr)
    steps = 0
    while arr[0]!= arr[arr.index(max(arr))]:
        max1 = max(arr)
        count = arr.count(max1)
        scnd_max = arr.index(max1)-1
        arr[scnd_max+count] = arr[scnd_max]
        steps += 1
    return steps

n = int(input())
arr = [int(x) for x in input().split()]
print(No_Books(arr,n))

Output

5
4 5 5 2 4

6

Here minimum moves required is 6

Answer 1

I'm interpreting the question in the following way:

For each element in the array, there is one and only one operation you're allowed to perform, and that operation is to replace an index's value with the array's current second-largest element.

How many operations are necessary to make the entire array's values equal to the initial minimum value?

With the example input 4 5 5 2 4 needing to go through the following steps:

Array     - step - comments
4 5 5 2 4 - 0 - start
4 4 5 2 4 - 1 - replace the first 5 with 4 (the second-largest value in the array)
4 4 4 2 4 - 2 - replace the second 5 with 4
2 4 4 2 4 - 3 - replace the first 4 with 2
2 2 4 2 4 - 4
2 2 2 2 4 - 5
2 2 2 2 2 - 6
It took 6 steps, so the result is 6.

If that is correct, then I can change your quadratic solution (O(n^2), where n is the size of the array) to a quasilinear solution (O(n + mlogm) where n is the size of the array, and m is the number of unique values in the array), as follows.

The approach is to notice that each value needs to be dropped down to the next largest value for each unique value smaller than itself. So if we can track the count of each unique value, we can determine the number of steps without actually doing any array updates.

In pseudocode:

function determineSteps(array):
  define map from integer to integer, defaulting to 0

  for each value in array: // Linear in N
    map(value)++

  sort map by key, descending // M log M

  // largerCount is the number of elements larger than the current second-largest value
  define largerCount, assign 0 to largerCount
  // stepCount is the number of steps required
  define stepCount, assign 0 to stepCount

  for each key in map except the last: // Linear in M
    largerCount = largerCount + map(key)
    stepCount = stepCount + largerCount

  return stepCount

On your example input:

4 5 5 2 4
Create map { 4: 2, 5: 2, 2: 1 }
Sort map by key, descending: { 5: 2, 4: 2, 2: 1 }
stepCount = 0
largerCount = 0
Examine key = 5, map(key) = 2
largerCount = 0 + 2 = 2 
stepCount = 0 + 2 = 2
Examine key = 4, map(key) = 2
largerCount = 2 + 2 = 4
stepCount = 2 + 4 = 6
return 6