Reduce given operations required to kind the stream array

Given an array stream of n integers within the type of a stream, the duty is to seek out the minimal variety of operations which are required to kind the stream (growing order) following the under steps:

• In a single operation you may decide up the primary component after which put that component to the xth index. 
• All the weather to the left of the xth index shift one place left and the primary component go to the following place. 
• The place of the weather on the fitting of the xth place stays unchanged.
• One can select totally different x independently for various parts. 

Examples:

Enter: n = 5, stream[] = {4, 2, 3, 5, 6}
Output: 1
Explaination: Within the preliminary stream we will entry solely the primary component which is 4 on this case and seHend it to x = 2 positions again as a consequence of which the quantity 2 within the stream will come at first place. The brand new stream turns into {2, 3, 4, 5, 6} which is already sorted in growing order. Therefore we require 1 operation.

Enter: n = 4, stream[] = {2, 3, 5, 4}
Output: 3
Explaination: In first step we select x = 2 for first component and the brand new stream turns into {3, 5, 2, 4}. In second step we select x = 2 for first component and the brand new stream turns into {5, 2, 3, 4}. Within the third step we select x = 4 for first component and the brand new stream turns into {2, 3, 4, 5} which is sorted. Therefore we require 3 operations.

Method: The given drawback will be solved through the use of a small commentary.

Observations:

We all the time wish to decide up the primary component and put it in a spot such that the suffix of the array stays sorted. Therefore we traverse from the final component of the array and discover the size of the longest suffix that’s sorted within the preliminary array. Now for every remaining component apart from these within the longest sorted suffix we’d require an operation. Therefore, the ultimate end result could be n – size of the longest sorted suffix.

Comply with the steps to unravel the issue:

• Initialize a variable say depend equal to 1. This variable shops the size of the longest sorted suffix.
• Begin iterating the array from the second final component.
• Verify for circumstances whether or not the present component is lower than or equal to the component on its proper or not.
• If the situation is true, increment depend by 1 (depend = depend + 1).
• If the situation is fake, break from the loop.
• The last result’s n – depend.

Under is the implementation of the above strategy:

Time Complexity: O(N) 
Auxiliary House: O(1)