I tried sorting but it's O(n log n). How to do it in O(n)?
Comments (1)
abhinav01
April 29, 2026, 5:38 p.m.
You can solve this problem in O(n) time using a cyclic sort / index placement approach.
The idea is to place each number at its correct index position. Since the array contains numbers in the range [1, n], ideally number x should be placed at index (x - 1).
You can solve this problem in O(n) time using a cyclic sort / index placement approach. The idea is to place each number at its correct index position. Since the array contains numbers in the range [1, n], ideally number x should be placed at index (x - 1).