|
Given an array stream of n integers in the form of a stream, the task is to find the minimum number of operations that are required to sort the stream (increasing order) following the below steps:
- In one operation you can pick up the first element and then put that element into the xth index.
- All the elements to the left of the xth index shift one position left and the first element go to the next position.
- The position of the elements on the right of the xth position remains unchanged.
- One can choose different x independently for different elements.
Examples:
Input: n = 5, stream[] = {4, 2, 3, 5, 6}
Output: 1
Explanation: In the initial stream we can access only the first element which is 4 in this case and seHend it to x = 2 positions back due to which the number 2 in the stream will come at first position. The new stream becomes {2, 3, 4, 5, 6} which is already sorted in increasing order. Hence we require 1 operation.
Input: n = 4, stream[] = {2, 3, 5, 4}
Output: 3
Explanation: In first step we choose x = 2 for first element and the new stream becomes {3, 5, 2, 4}. In second step we choose x = 2 for first element and the new stream becomes {5, 2, 3, 4}. In the third step we choose x = 4 for first element and the new stream becomes {2, 3, 4, 5} which is sorted. Hence we require 3 operations.
Approach: The given problem can be solved by using a small observation.
Observations:
We always want to pick up the first element and put it in a place such that the suffix of the array remains sorted. Hence we traverse from the last element of the array and find the length of the longest suffix that is sorted in the initial array. Now for each remaining element other than those in the longest sorted suffix we would require an operation. Hence, the final result would be n – length of the longest sorted suffix.
Follow the steps to solve the problem:
- Initialize a variable say count equal to 1. This variable stores the length of the longest sorted suffix.
- Start iterating the array from the second last element.
- Check for conditions whether the current element is less than or equal to the element on its right or not.
- If the condition is true, increment count by 1 (count = count + 1).
- If the condition is false, break from the loop.
- The final result is n – count.
Below is the implementation of the above approach:
C++
<?php
function minOpsToSort($stream, $n)
{
$count = 1;
for ($i = $n - 2; $i >= 0; $i--) {
if ($stream[$i] <= $stream[$i + 1]) {
$count++;
}
else {
break;
}
}
return $n - $count;
}
$stream = array(2, 3, 5, 4);
$n = count($stream);
$minimumOperations = minOpsToSort($stream, $n);
echo $minimumOperations;
?>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
|
