AARRAY - Editorial

editorial
,
1

PROBLEM LINK:

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

DIFFICULTY:

Simple

PREREQUISITES:

Sorting, loops

PROBLEM:

Given a non-negative integer array of size N. Find the start and end index(1-based) of continuous subarray such that sorting that subarray will make complete array sorted. Print -1 if no such subarray exist.

OUICK EXPLANATION:

Sort the array and find first point of difference from left and right. They will mark the start and end of the subarray. If they both are same then answer is -1.

EXPLANATION:

Let array with N non-negative integers be arr. Create a sorted copy of the array let it be carr. Now take two iterators i.e. left=0 and right=N-1.

Now compare the values of arr and carr at these iterators.
if(arr[left] == carr[left]) then left += 1 else the left marks the start of the subarray.

Similarly

if(arr[right] == carr[right]) then right -= 1 else right marks the end of the subarray.
Answer will be start=left+1 end = right+1 (1-based).
If start and end are same then answer will be -1.

COMPLEXITIES:

Time Complexity: O(NlogN) for each test case
Space Complexity: O(N) for each test case

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int arr[1000005], carr[1000005];

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
		carr[i] = arr[i];
	}

	sort (arr, arr + n);

	int left = 0;
	int right = n-1;

	bool leftFlag = true;
	bool rightFlag = true;

	while(left < right)
	{
		if (arr[left] != carr[left])
			leftFlag = false;
		else if(leftFlag)
			left++;

		if(arr[right] != carr[right])
			rightFlag = false;
		else if(rightFlag)
			right--;

		if (!leftFlag && !rightFlag)
			break;
	}

	if (left >= right)
		cout << -1 << '\n';
	else
		cout << left + 1 << ' ' << right + 1;
}
1 Like