Check whether a given array is a k sorted array or not in Python
By Abinash ReddyIn 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