Best way to find the largest sorted suffix in a list - USACO Sleepy Cow Sorting Python

Question

Solving this problem.

Right now, my solution entails finding the largest sorted sublist, starting from the beginning, all the way to the end. However, I feel like the way I wrote the sorted_sublist function can definitely be improved. Besides that, I'm looking for any way to improve the way I write my code.

My code:

with open("sleepy.in", "r") as fin:
  n = int(next(fin))
  nums = [int(i) for i in fin.readline().split()]

def sorted_sublist(n, nums):
  for i in range(n):
    sublist = nums[i:n]
    if sublist == sorted(sublist):
      return sublist

def main(n, nums):
 x = sorted_sublist(n, nums)
 return n - len(x)

with open("sleepy.out", "w+") as fout:
 print(main(n, nums), file=fout)

Problem synopsis: Given a list of numbers, find the number of steps it would take to sort this list by repeatedly placing the first element of this list into another slot, provided that you do this in an optimal fashion.

Example:

Input:

4
4 3 2 1

Step 1. Place the 4 to the back of the list: 3, 2, 1, 4

Step 2. Place the 3 to the third index of the list: 2, 1, 3, 4

Step 3. Place the 2 to the second index of the list: 1, 2, 3, 4

Output: 3, as it took three optimal steps to reach a sorted list

Answer 1

Nice solution and implementation. Few suggestions:

• Naming: the name main is generally used for the entry point of the program. In this case, a better name could be steps_to_sort_cows.
• Sublist bounds: since n is fixed, instead of sublist = nums[i:n] you can write sublist = nums[i:]

Complexity

The time complexity is \$O(n*n*log(n))\$. Basically, for each cow sort all the remaining cows. Typically, it's considered not optimal for large inputs.

The space complexity is also not optimal. For each cow two lists are created, one for the new sublist and one for the sorted sublist.

Improved

To reduce space and time complexity, find the size of the sorted sublist in this way:

def steps_to_sort_cows(n, cows):
  first_sorted_cow = cows[-1]
  sorted_cows = 0
  for c in reversed(cows):
    if c > first_sorted_cow:
      return n - sorted_cows
    first_sorted_cow = c
    sorted_cows += 1
  return 0

Starting from the end, count the number of sorted cows and then return n - sorted_cows.

This approach takes \$O(n)\$ time and \$O(1)\$ space complexity.

Answer 2

Some suggestions:

• Use better indentation. Always the same, and especially not just one space. Four spaces are the standard.
• You're inconsistent, I'd replace fin.readline() with another next(fin).
• open has mode 'r' by default, no need to specify. And you don't really want + when writing.
• For the file variable, personally I prefer just f, and use fin and fout only when I have both open in parallel (like when the input file has multiple test cases).
• Your solution is to identify the longest sorted suffix and then discount it. A faster and shorter way to do that is to simply pop off from the end as long as it's sorted. And we can use N as sentinel to simplify and speed up a bit further.

So my rewrite is:

with open('sleepy.in') as f:
    cows = list(map(int, f.read().split()))

while cows.pop() > cows[-1]:
    pass

with open('sleepy.out', 'w') as f:
    print(len(cows) - 1, file=f)

Alternatively, find the last index where the number didn't go up:

with open('sleepy.in') as f:
    n = int(next(f))
    cows = list(map(int, next(f).split()))

result = max(i for i in range(n) if cows[i] <= cows[i-1])

with open('sleepy.out', 'w') as f:
    print(result, file=f)

(Should better use next and range(n)[::-1], but meh, I like brevity and we're spending Θ(n) on reading the input anyway.)