Sort a nearly sorted array
CitadelData Scientist · Onsite
Last updated
This question evaluates algorithmic problem-solving skills, specifically understanding sorting under constrained inputs and rigorous time and space complexity analysis.
Given an array of length (n) in which every element is at most (k) positions away from its location in the fully sorted order, design an algorithm to return the sorted array. Aim for a solution that is more efficient than (O(n \log n)), and state the time and space complexity.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.