# Check whether a given array is a k sorted array or not in Python

In this article, we learn how to check whether a given array is a k sorted array or not in Python. An array is said k sorted array if each element in the array is at most k distance away from the target position in the original sorted array.

Example

Input: arr[] = {3, 2, 1, 5, 6, 4, 8, 7} k = 2 Output: Yes Explanation: The sorted array is {1, 2, 3, 4, 5, 6, 7, 8} every element is at most 2 distance away from the sorted array. Input: arr[] = {2, 8, 1, 6, 3, 4} k = 1 Output: No Explanation: The sorted array is {1, 2, 3, 4, 6, 8} the at most distance away from the sorted array is 4.

## K sorted array in Python

1. Create a temporary list temp and copy the given array arr to temp.

2. Now sort the temp using the sort() function.

3. Create a function binary_search that returns the position of the particular element in the temp

4. Iterate the array from range 0 to n.

- Now find the position j of the element arr[i] in temp using binary_search function.
- Now compare the difference between i and j, if it is greater than then return “No”
- Else, return “Yes”

def binary_Search(arr, low, high, x): while (low <= high): mid = int((low + high) / 2) if (arr[mid] == x): return mid elif(arr[mid] > x): high = mid - 1 else: low = mid + 1 def kSortedArray(arr, n, k): temp = [0 for i in range(n)] for i in range(0, n, 1): temp[i] = arr[i] temp.sort(reverse = False) for i in range(0, n, 1): j = binary_Search(temp, 0, n - 1, arr[i]) if (abs(i - j) > k): return "No" return "Yes" arr = [3, 2, 1, 5, 6, 4, 8, 7] print("The given array is: ", str(arr)) n = len(arr) k = int(input("Enter the k value: ")) print(kSortedArray(arr, n, k))

Output

The given array is: [3, 2, 1, 5, 6, 4, 8, 7] Enter the k value: 2 Yes The given array is: [3, 2, 1, 5, 6, 4, 8, 7] Enter the k value: 1 No

Also, read

## Leave a Reply