Check whether a given array is a k sorted array or not

0 0 10 minutes read

Given an array of n distinct elements. Check whether the given array is a k sorted array or not. A k sorted array is an array where each element is at most k distances away from its target position in the sorted array.

For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.

Examples:

Input : arr[] = {3, 2, 1, 5, 6, 4}, k = 2
Output : Yes
Every element is at most 2 distance away
from its target position in the sorted array.

Input : arr[] = {13, 8, 10, 7, 15, 14, 12}, k = 3
Output : No
13 is more than k = 3 distance away
from its target position in the sorted array.

Copy elements of the original array arr[] to an auxiliary array aux[].
Sort aux[]. Now, for each element at index i in arr[], find its index j in aux[] using Binary Search. If for any element k < abs(i-j), then arr[] is not a k sorted array. Else it is a k sorted array. Here abs are the absolute value.

Implementation:

C++

// C++ implementation to check whether the given array
// is a k sorted array or not
#include <bits/stdc++.h>
using namespace std;
 
// function to find index of element 'x' in sorted 'arr'
// uses binary search technique
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;    
    }
}
 
// function to check whether the given array is
// a 'k' sorted array or not
string isKSortedArray(int arr[], int n, int k)
{
    // auxiliary array 'aux'
    int aux[n];
     
    // copy elements of 'arr' to 'aux'
    for (int i = 0; i<n; i++)
        aux[i] = arr[i];
     
    // sort 'aux'    
    sort(aux, aux + n);
     
    // for every element of 'arr' at index 'i', 
    // find its index 'j' in 'aux'
    for (int i = 0; i<n; i++)
    {
        // index of arr[i] in sorted array 'aux'
        int j = binarySearch(aux, 0, n-1, arr[i]);
         
        // if abs(i-j) > k, then that element is
        // not at-most k distance away from its 
        // target position. Thus,  'arr' is not a 
        // k sorted array 
        if (abs(i - j) > k)
            return "No";
    }
     
    // 'arr' is a k sorted array
    return "Yes";    
}
 
// Driver program to test above
int main()
{
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "Is it a k sorted array?: "
         << isKSortedArray(arr, n, k);
    return 0;     
} 

Java

// Java implementation to check whether the given array
// is a k sorted array or not
 
import java.util.Arrays;
 
class Test
{
    // Method to check whether the given array is
    // a 'k' sorted array or not
    static String isKSortedArray(int arr[], int n, int k)
    {
        // auxiliary array 'aux'
        int aux[] = new int[n];
          
        // copy elements of 'arr' to 'aux'
        for (int i = 0; i<n; i++)
            aux[i] = arr[i];
          
        // sort 'aux'    
        Arrays.sort(aux);
          
        // for every element of 'arr' at index 'i', 
        // find its index 'j' in 'aux'
        for (int i = 0; i<n; i++)
        {
            // index of arr[i] in sorted array 'aux'
            int j = Arrays.binarySearch(aux,arr[i]);
              
            // if abs(i-j) > k, then that element is
            // not at-most k distance away from its 
            // target position. Thus,  'arr' is not a 
            // k sorted array 
            if (Math.abs(i - j) > k)
                return "No";
        }
          
        // 'arr' is a k sorted array
        return "Yes";    
    }
 
    // Driver method
    public static void main(String args[])
    {
        int arr[] = {3, 2, 1, 5, 6, 4};
        int k = 2;
         
        System.out.println("Is it a k sorted array ?: " +
                            isKSortedArray(arr, arr.length, k));
    }
}

Python3

# Python 3 implementation to check 
# whether the given array is a k 
# sorted array or not
 
# function to find index of element 
# 'x' in sorted 'arr' uses binary 
# search technique
def binarySearch(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
 
# function to check whether the given 
# array is a 'k' sorted array or not
def isKSortedArray(arr, n, k):
     
    # auxiliary array 'aux'
    aux = [0 for i in range(n)]
     
    # copy elements of 'arr' to 'aux'
    for i in range(0, n, 1):
        aux[i] = arr[i]
     
    # sort 'aux' 
    aux.sort(reverse = False)
     
    # for every element of 'arr' at 
    # index 'i', find its index 'j' in 'aux'
    for i in range(0, n, 1):
         
        # index of arr[i] in sorted
        # array 'aux'
        j = binarySearch(aux, 0, n - 1, arr[i])
         
        # if abs(i-j) > k, then that element is
        # not at-most k distance away from its 
        # target position. Thus, 'arr' is not a 
        # k sorted array 
        if (abs(i - j) > k):
            return "No"
     
    # 'arr' is a k sorted array
    return "Yes"
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 2, 1, 5, 6, 4]
    n = len(arr)
    k = 2
    print("Is it a k sorted array?:", 
           isKSortedArray(arr, n, k))
 
# This code is contributed by
# Shashank_Sharma

C#

// C# implementation to check 
// whether the given array is a 
// k sorted array or not
using System;
using System.Collections;
 
class GFG {
     
    // Method to check whether the given
    // array is a 'k' sorted array or not
    static String isKSortedArray(int []arr, int n, int k)
    {
        // auxiliary array 'aux'
        int []aux = new int[n];
         
        // copy elements of 'arr' to 'aux'
        for (int i = 0; i<n; i++)
            aux[i] = arr[i];
         
        // sort 'aux' 
        Array.Sort(aux);
         
        // for every element of 'arr' at index
        // 'i', find its index 'j' in 'aux'
        for (int i = 0; i<n; i++)
        {
            // index of arr[i] in sorted array 'aux'
            int j = Array.BinarySearch(aux,arr[i]);
             
            // if abs(i-j) > k, then that element is
            // not at-most k distance away from its 
            // target position. Thus, 'arr' is not a 
            // k sorted array 
            if (Math.Abs(i - j) > k)
                return "No";
        }
         
        // 'arr' is a k sorted array
        return "Yes"; 
    }
 
    // Driver method
    public static void Main()
    {
        int []arr = {3, 2, 1, 5, 6, 4};
        int k = 2;
         
        Console.WriteLine("Is it a k sorted array ?: " +
                           isKSortedArray(arr, arr.Length, k));
    }
}
 
// This code is contributed by Sam007

Javascript

<script>
  
// Javascript implementation to check whether the given array
// is a k sorted array or not
 
// function to find index of element 'x' in sorted 'arr'
// uses binary search technique
function binarySearch(arr, low, high, x)
{
    while (low <= high)
    {
        var mid = parseInt((low + high) / 2);
         
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] > x)
            high = mid - 1;
        else   
            low = mid + 1;    
    }
}
 
// function to check whether the given array is
// a 'k' sorted array or not
function isKSortedArray(arr, n, k)
{
    // auxiliary array 'aux'
    var aux = Array(n);
 
    // copy elements of 'arr' to 'aux'
    for (var i = 0; i<n; i++)
        aux[i] = arr[i];
     
    // sort 'aux'    
    aux.sort((a,b)=> a-b)
     
    // for every element of 'arr' at index 'i', 
    // find its index 'j' in 'aux'
    for (var i = 0; i<n; i++)
    {
        // index of arr[i] in sorted array 'aux'
        var j = binarySearch(aux, 0, n-1, arr[i]);
         
        // if abs(i-j) > k, then that element is
        // not at-most k distance away from its 
        // target position. Thus,  'arr' is not a 
        // k sorted array 
        if (Math.abs(i - j) > k)
            return "No";
    }
     
    // 'arr' is a k sorted array
    return "Yes";    
}
 
// Driver program to test above
var arr = [3, 2, 1, 5, 6, 4];
var n = arr.length;
var k = 2;
document.write( "Is it a k sorted array?: "
      + isKSortedArray(arr, n, k));
 
 
</script>

Output

Is it a k sorted array?: Yes

Time Complexity: O(nlogn)
Auxiliary space: O(n)

Another Approach can be to store the corresponding indices of elements into the aux array. Then simply check if abs ( i – aux[i].second ) <= k, return “No” if the condition is not satisfied. It is slightly faster than the approach mentioned above as we don’t have to perform binary search to check the distance from original index, though the “O notation” would remain same.

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
string isKSortedArray(int arr[], int n, int k)
{
  // creating an array to store value, index of the original array
  vector<pair<int, int>> aux;
   
  for(int i=0;i<n;i++){
    aux.push_back({arr[i], i}); //  pushing the elements and index of arr to aux
  }
   
  // sorting the aux array
  sort(aux.begin(), aux.end());
   
  //  for every element, check if the absolute value of (currIndex-originalIndex) <= k
  //  if not, then return "NO"
  for(auto i=0;i<n;i++){
    if(abs(i-aux[i].second)>k) return "No"; 
     
  }
   
  // If all elements satisfy the condition, the loop will terminate and 
  // "Yes" will be returned.
  return "Yes";
}
 
int main() {
    int arr[] = {3, 2, 1, 5, 6, 4}; //  input array
      int n = sizeof(arr)/sizeof(int); // number of elements in array(arr)
      int k = 2; // value to check is array is "k" sorted
   
    cout<<isKSortedArray(arr, n, k); // prints "Yes" since the input array is k-sorted
   
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.util.*;
class GFG {
 
  static class Pair{
    int key;
    int val;
 
    Pair(int k,int v){
      key = k;
      val = v;
    }
 
  }
 
  static String isKSortedArray(int arr[], int n, int k)
  {
    // creating an array to store value, 
    // index of the original array
    List<Pair> aux = new ArrayList<>();
 
    for(int i=0;i<n;i++){
      aux.add(new Pair(arr[i], i)); //  pushing the elements and index of arr to aux
    }
 
    // sorting the aux array
    Collections.sort(aux,(a,b)->a.key-b.key);
 
    //  for every element, check if the absolute 
    // value of (currIndex-originalIndex) <= k
    //  if not, then return "NO"
    for(int i=0;i<n;i++){
      if(Math.abs(i-aux.get(i).val)>k) return "No"; 
 
    }
 
    // If all elements satisfy the condition, 
    // the loop will terminate and 
    // "Yes" will be returned.
    return "Yes";
  }
 
  public static void main (String[] args) {
    int arr[] = {3, 2, 1, 5, 6, 4}; //  input array
    int n =arr.length; // number of elements in array(arr)
    int k = 2; // value to check is array is "k" sorted
 
    System.out.println(isKSortedArray(arr, n, k)); // prints "Yes" since the input array is k-sorted
 
  }
}
 
// This code is contributed by aadityaburujwale.

Python3

# Python code for the same approach
def isKSortedArray(arr, n, k):
 
    # creating an array to store value, index of the original array
    aux = []
 
    for i in range(n):
        aux.append([arr[i], i]) # pushing the elements and index of arr to aux
 
    # sorting the aux array
    aux.sort()
 
    # for every element, check if the absolute value of (currIndex-originalIndex) <= k
    # if not, then return "NO"
    for i in range(n):
        if(abs(i-aux[i][1])>k):
            return "No"
 
    # If all elements satisfy the condition, the loop will terminate and
    # "Yes" will be returned.
    return "Yes"
 
# driver code
 
arr = [3, 2, 1, 5, 6, 4] # input array
n = len(arr) # number of elements in array(arr)
k = 2 # value to check is array is "k" sorted
 
print(isKSortedArray(arr, n, k)) # prints "Yes" since the input array is k-sorted
 
# This code is contributed by shinjanpatra

C#

using System;
using System.Collections;
class GFG {
  static string isKSortedArray(int[] arr, int n, int k)
  {
    // creating an array to store value, index of the
    // original array
    SortedList aux = new SortedList();
    for (int i = 0; i < n; i++) {
      aux.Add(arr[i], i); //  pushing the elements and
      //  index of arr to aux
    }
    //  for every element, check if the absolute value
    //  of (currIndex-originalIndex) <= k if not, then
    //  return "NO"
    for (int i = 0; i < aux.Count; i++) {
      int x = (int)aux.GetByIndex(i);
      if (Math.Abs(i - x) > k)
        return "No";
    }
 
    // If all elements satisfy the condition, the loop
    // will terminate and "Yes" will be returned.
    return "Yes";
  }
 
  public static void Main()
  {
    int[] arr = { 3, 2, 1, 5, 6, 4 }; //  input array
    int n = 6; // number of elements in array(arr)
    int k = 2; // value to check is array is "k" sorted
 
    Console.Write(isKSortedArray(
      arr, n, k)); // prints "Yes" since the input
    // array is k-sorted
  }
}
 
// This code is contributed by garg28harsh.

Javascript

// Javascript code Addition
 
class Pair {
    constructor(k, v) {
        this.key = k;
        this.val = v;
    }
}
 
function isKSortedArray(arr, n, k) {
    // creating an array to store value, 
    // index of the original array
    let aux = [];
 
    for (let i = 0; i < n; i++) {
        aux.push(new Pair(arr[i], i)); //  pushing the elements and index of arr to aux
    }
 
    // sorting the aux array
    aux.sort((a, b) => a.key - b.key);
 
    //  for every element, check if the absolute 
    // value of (currIndex-originalIndex) <= k
    //  if not, then return "NO"
    for (let i = 0; i < n; i++) {
        if (Math.abs(i - aux[i].val) > k) return "No";
    }
 
    // If all elements satisfy the condition, 
    // the loop will terminate and 
    // "Yes" will be returned.
    return "Yes";
}
 
let arr = [3, 2, 1, 5, 6, 4]; //  input array
let n = arr.length; // number of elements in array(arr)
let k = 2; // value to check is array is "k" sorted
 
console.log(isKSortedArray(arr, n, k)); // prints "Yes" since the input array is k-sorted
 
// This code is contributed by lokesh.

Output

Yes

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

This article is contributed by Ayush Jauhari and Naman Monga. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!