How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Citadel during technical interviews.

Sort a Nearly Sorted Array | Citadel Coding Question

Q: Sort a Nearly Sorted Array

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.

Sort a Nearly Sorted Array

Company: Citadel

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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.

Quick Answer: 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.

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 algorithm that takes advantage of this property and runs faster than general-purpose sorting when `k << n`.

Constraints

0 <= n <= 200000
-10^9 <= nums[i] <= 10^9
0 <= k
The input satisfies the nearly sorted property

Examples

Input: ([6, 5, 3, 2, 8, 10, 9], 3)

Expected Output: [2, 3, 5, 6, 8, 9, 10]

Explanation: Each element is at most 3 positions away from its sorted location, so a min-heap of size 4 is enough to recover the fully sorted order.

Input: ([1, 2, 3, 4], 0)

Expected Output: [1, 2, 3, 4]

Explanation: When k = 0, every element is already in its correct position, so the array is already sorted.

Input: ([], 5)

Expected Output: []

Explanation: An empty array remains empty after sorting.

Input: ([2, 1, 3, 3, 4], 1)

Expected Output: [1, 2, 3, 3, 4]

Explanation: This case includes duplicates. Since each element is at most 1 position away, the heap-based approach still sorts correctly.

Input: ([0, -1, 2, -3, 4], 3)

Expected Output: [-3, -1, 0, 2, 4]

Explanation: Negative numbers are handled normally. The array satisfies the nearly sorted property with k = 3.

Input: ([4, 1, 3, 2], 10)

Expected Output: [1, 2, 3, 4]

Explanation: Even when k is larger than the array length, the method still works by using a heap containing all available elements.

Hints

If the smallest remaining element can only be within the next `k+1` positions, what data structure helps you quickly extract the minimum from that window?
Maintain a min-heap of size at most `k+1` while scanning the array from left to right.

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.