Array - Cyclic Sort — Array/Matrix Manipulation Patterns

The Array - Cyclic Sort pattern applies when you need the Array - Cyclic Sort technique within the Array/Matrix Manipulation Patterns pattern. Its time complexity is O(n) and space complexity O(1). It is used in 3 problems on Thita, including Find All Duplicates in an Array, Find All Numbers Disappeared in an Array and First Missing Positive. Common variations are Product Except Self (Prefix/Suffix Products) and Merge Sorted Array (In-place from End).

Master cyclic sort pattern to find missing, duplicate, or misplaced numbers in arrays with O(n) time and O(1) space.

Array - Cyclic Sort is one of the 10 subpatterns of the Array/Matrix Manipulation Patterns pattern, which covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort. The whole pattern is about 4 hours of study. This subpattern is a depth topic for once the core techniques are automatic.

What Array - Cyclic Sort covers

Master array and matrix manipulation techniques including in-place rotation, spiral traversal, prefix/suffix products, and cyclic sort. Essential patterns for coding interviews at FAANG companies. Problems in this subpattern are usually searched for as cyclic sort, find missing number, find duplicate, array sorting, in-place sort, leetcode 268.

How to practise Array - Cyclic Sort on Thita.ai

Read the theory for Array - Cyclic Sort, then work the problems attached to it in the browser editor. Your solution runs against the problem's test cases, and the AI coach offers a hint about the technique you are missing rather than a finished solution. Progress is tracked per subpattern, so the Array/Matrix Manipulation Patterns tracker shows this one as covered once you have solved its problems.

Other subpatterns in Array/Matrix Manipulation Patterns

• Merge Sorted Array (In-place from End) — Learn the merge sorted array technique starting from the end. Essential for space-efficient array merging in coding interviews.
• Spiral Traversal — Master spiral traversal pattern for 2D matrices. Learn to traverse matrices in spiral order for interview problems.
• Set Matrix Zeroes (In-place Marking) — Learn the in-place marking technique to set entire rows and columns to zero efficiently without extra space.
• Hashing - Frequency Map / Counting — Master hash map frequency counting for array problems. Count occurrences, find duplicates, and solve majority element problems efficiently.
• Prefix Sum - Subarray Sum / Range Query — Master prefix sum technique for efficient subarray sum and range query problems. Solve subarray sum equals K and contiguous array problems.
• Product Except Self (Prefix/Suffix Products) — Master the prefix and suffix products technique to calculate product of array except self without division.
• Plus One (Handling Carry) — Learn to handle carry operations when adding one to a number represented as an array of digits.
• Hashing - Previously Seen / Existence Check — Use hash sets for O(1) existence checks. Track previously seen elements to detect duplicates, find pairs, and validate sequences.
• In-place Rotation — Learn in-place rotation techniques for arrays and matrices. Rotate without using extra space.

Related DSA patterns

• Sliding Window — Fixed-size, variable-size, and character frequency matching window techniques.
• Binary Search Patterns — Standard binary search, rotated arrays, first/last occurrence, and search on answer space.
• Linked List Manipulation Patterns — In-place reversal, merging sorted lists, reordering, and intersection detection.
• Stack Patterns — Parentheses matching, monotonic stack, histogram, and expression evaluation.

Where to go next

Array - Cyclic Sort is one lesson in a 16-pattern DSA course. If you are preparing end to end, work the interview-critical patterns first and use the pattern sheet as the checklist; if you are here for one technique, the Array/Matrix Manipulation Patterns guide is the shortest path back to the rest of it.

• The Array/Matrix Manipulation Patterns pattern guide
• All DSA patterns
• The DSA patterns sheet
• Coding practice