Sort a Nearly Sorted Array
Quick Overview
This question evaluates algorithm design and analysis skills, focusing on handling nearly-sorted arrays and reasoning about time and space complexity within the Coding & Algorithms domain.
Citadel
Feb 21, 2026, 12:00 AM
Data Scientist
Onsite
Coding & Algorithms
1
0
Loading...
Given an array nums of length n in which every element is at most k positions away from its location in the fully sorted order, return the array in sorted order.
Formally, if an element belongs at index i after sorting, then in the input it appears somewhere in the range [i-k, i+k].
Design an efficient algorithm that is better than general-purpose sorting when k << n, and analyze its time and space complexity.