Reacto fullstack11/23/2023 The 1st number in the array can be in any position from 0 to k, since there are no negative indices.Ĭonsider a sub-array of that length, k + 1, filled with the first k + 1 values in the array. How can we guarantee that? ‘Sliding Window’ Sub-Array ![]() ![]() However, if we can guarantee that the first index’s value is sorted, then this becomes k + 1 options for the next element. K provides a plus/minus deviation from the actual index, providing 2k + 1 options for every element. This would be done in O(nk) time, since for every element in the n length array, you need to loop through k values to obtain the minimum. However, this would ignore that fact that the array is already mostly sorted (k-sorted), resulting in a less optimal solution.Īnother approach utilizes the k values, by finding the minimum of the k values (a window of k values) in front of an element, and comparing its minimum to the element, swapping places if needed. Let arr = let k = 2 sortKMessedArray (arr, k ) //output: ApproachĪn initial approach would be to sort the array using mergeSort or JavaScript’s sort method, in nlog(n) time. Exampleįor an input array of size 10 and k = 2, an element belonging to index 6 in the sorted array will be located at either index 4, 5, 6, 7 or 8 in the input array. Given an array of integers arr where each element is at most k places away from its sorted position, write a function sortKMessedArray that sorts arr. We hope you enjoy! K-Messed Array Sort See Repl Prompt This series of posts will give you a problem to solve and an explanation of both the brute force & optimized solutions.
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |