Problem Link - Sorting Books
Problem Statement
Indraneel has to sort the books in his library. His library has one long shelf. His books are numbered 1 through N and he wants to rearrange the books so that they appear in the sequence 1, 2, \dots, N.
He intends to do this by a sequence of moves. In each move, he can pick up any book from the shelf and insert it at a different place in the shelf. Suppose Indraneel has 5 books and they are initially arranged in the order
2~~~~~1~~~~~4~~~~~5~~~~~3.
Indraneel will rearrange this in ascending order by first moving book 1 to the beginning of the shelf to get
1~~~~~2~~~~~4~~~~~5~~~~~3
Then, moving book 3 to position 3, he gets
1~~~~~2~~~~~3~~~~~4~~~~~5
Your task is to write a program to help Indraneel determine the minimum number of moves that are necessary to sort his bookshelf.
Approach
To solve this problem, we find the length of the Longest Increasing Subsequence (LIS) in the bookshelf arrangement, representing the maximum number of books already in order. The minimum moves required will be the total books minus the LIS length. We maintain a sorted list to calculate the LIS efficiently. For each book, if it’s larger than the last in the list, we append it; otherwise, we use binary search to replace the appropriate position in the list. This keeps the list sorted and minimal, representing the LIS. The difference between the total books and the list size gives the result.
Time Complexity
The time complexity is O(N \log N), where N is the number of books, due to the binary search operations for each book.
Space Complexity
The space complexity is O(N), as we maintain an auxiliary list to track the LIS.