Sorting: Check if a given array is K sorted or not

Problem Statement:

You are given an array of unique elements and and a number k..

You need to check if the array is K sorted or not.

Example:

Input: [3, 2, 1, 5, 6, 4] K =2

Output: Yes

All the elements are at most 2 blocks away from the sorted position.

Solution :

Take a temp array and copy the elements to the temp array, sort the temp array.

For each element at index i at original array find the index j in temp array using binary search.

Now check if the position is less than k and proceed with the result.

Time Complexity: O(n logn)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;


int binarySearch(int arr[], int low, int high, int x)
{
	while (low <= high)
	{
		int mid = (low + high) / 2;
		
		if (arr[mid] == x)
			return mid;

		else if (arr[mid] > x)
			high = mid - 1;

		else
			low = mid + 1; 
	}
}

string solution(int arr[], int n, int k)
{
	int temp[n];
	
	for (int i = 0; i<n; i++)
		temp[i] = arr[i];
	
	sort(temp, temp + n);
	
	for (int i = 0; i<n; i++)
	{
		int j = binarySearch(temp, 0, n-1, arr[i]);
		
		if (abs(i - j) > k)
			return "No";
	}
	
	return "Yes"; 
}

int main()
{
	int arr[] = {3, 2, 1, 5, 6, 4};
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 2;

	cout << solution(arr, n, k);

	return 0;	 
} 

Output

Yes