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

Your email address will not be published.