{"id":115758,"date":"2026-06-15T23:00:52","date_gmt":"2026-06-15T17:30:52","guid":{"rendered":"https:\/\/www.guvi.in\/blog\/?p=115758"},"modified":"2026-06-15T23:00:55","modified_gmt":"2026-06-15T17:30:55","slug":"what-is-a-permutation-array-in-dsa","status":"publish","type":"post","link":"https:\/\/www.guvi.in\/blog\/what-is-a-permutation-array-in-dsa\/","title":{"rendered":"What is a Permutation Array in DSA?"},"content":{"rendered":"\n<p><strong>Quick TL;DR<\/strong><\/p>\n\n\n\n<ul>\n<li>A permutation array in DSA is an array of length n that contains every integer from 0 to n\u22121 exactly once, representing a specific rearrangement of elements. It is widely used in sorting algorithms, cycle detection, in-place operations, and competitive programming. <\/li>\n\n\n\n<li>Key operations include applying a permutation to another array, finding its inverse, composing two permutations, and detecting cycles, all achievable in O(n) time. <\/li>\n\n\n\n<li>Understanding Permutation Arrays in DSA is essential for cracking product-based company interviews and solving array manipulation problems efficiently.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Introduction<\/strong><\/h2>\n\n\n\n<p>Many beginners working through DSA problems stumble upon arrays that seem sorted but are not, and the missing concept is almost always the permutation array. A Permutation Array in DSA is a fundamental building block that powers everything from sorting algorithms to graph traversal. Understanding how it works, how to apply it, and where it goes wrong will sharpen your problem-solving skills and make a large class of interview questions significantly easier to tackle.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is a Permutation Array in DSA?<\/strong><\/h2>\n\n\n\n<p>A Permutation <a href=\"https:\/\/www.guvi.in\/blog\/array-data-structures-and-algorithms-in-java\/\" target=\"_blank\" rel=\"noreferrer noopener\">Array<\/a> in DSA is an array P of length n where every integer from 0 to n\u22121 appears exactly once. It defines a bijection, a one-to-one mapping from the set of indices to itself.<\/p>\n\n\n\n<p>Think of it as a rearrangement instruction. Each index i holds a value that says: the element at position i should move to position P[i].<\/p>\n\n\n\n<p>For example, if n = 4 and perm = [2, 0, 3, 1], the mapping is:<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Index 0 \u2192 position 2<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Index 1 \u2192 position 0<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Index 2 \u2192 position 3<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; Index 3 \u2192 position 1<\/p>\n\n\n\n<p>This simple structure becomes extremely powerful when you need to rearrange data, undo a shuffle, or solve complex in-place manipulation problems.<\/p>\n\n\n\n<p><strong>Read More: <\/strong><a href=\"https:\/\/www.guvi.in\/blog\/basic-coding-problems-in-dsa\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>Basic Coding Problems in DSA for Beginners<\/strong><\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>How Does a Permutation Array Work?<\/strong><\/h2>\n\n\n\n<p>Let&#8217;s walk through how a permutation array actually rearranges elements, step by step.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Step 1: Start with an input array and a permutation<\/strong><\/h3>\n\n\n\n<p>Suppose arr = [&#8216;A&#8217;, &#8216;B&#8217;, &#8216;C&#8217;, &#8216;D&#8217;] and perm = [2, 0, 3, 1]. The permutation tells you exactly where each element in arr needs to go.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Step 2: Apply the permutation<\/strong><\/h3>\n\n\n\n<p>Create a result array of the same size. For each index i, place arr[i] at result[perm[i]].<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>result&#91;perm&#91;0]] = result&#91;2] = 'A'\n\nresult&#91;perm&#91;1]] = result&#91;0] = 'B'\n\nresult&#91;perm&#91;2]] = result&#91;3] = 'C'\n\nresult&#91;perm&#91;3]] = result&#91;1] = 'D'<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Step 3: Read the output<\/strong><\/h3>\n\n\n\n<p>result = [&#8216;B&#8217;, &#8216;D&#8217;, &#8216;A&#8217;, &#8216;C&#8217;]. The array has been rearranged exactly as specified by the permutation in a single O(n) pass.<\/p>\n\n\n\n<p>Here is the complete code in Python:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def apply_permutation(arr, perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;n = len(arr)\n\n&nbsp;&nbsp;&nbsp;&nbsp;result = &#91;None] * n\n\n&nbsp;&nbsp;&nbsp;&nbsp;for i in range(n):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result&#91;perm&#91;i]] = arr&#91;i]\n\n&nbsp;&nbsp;&nbsp;&nbsp;return result\n\narr&nbsp; = &#91;'A', 'B', 'C', 'D']\n\nperm = &#91;2, 0, 3, 1]\n\nprint(apply_permutation(arr, perm))\n\n# Output: &#91;'B', 'D', 'A', 'C']<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Types of Permutations in DSA<\/strong><\/h2>\n\n\n\n<p>Not every permutation behaves the same way. Here are the main types you will encounter in DSA problems and interviews:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Type<\/strong><\/td><td><strong>Description<\/strong><\/td><td><strong>Example (n=4)<\/strong><\/td><\/tr><tr><td><strong>Identity<\/strong><\/td><td>Every element stays in place: P[i] = i<\/td><td>[0, 1, 2, 3]<\/td><\/tr><tr><td><strong>Inverse<\/strong><\/td><td>Reverses the mapping: inv[P[i]] = i<\/td><td>perm=[2,0,3,1] \u2192 inv=[1,3,0,2]<\/td><\/tr><tr><td><strong>Cyclic<\/strong><\/td><td>Rotates elements: P[i] = (i+1) % n<\/td><td>[1, 2, 3, 0]<\/td><\/tr><tr><td><strong>Derangement<\/strong><\/td><td>No element is in its original position<\/td><td>[1, 0, 3, 2]<\/td><\/tr><tr><td><strong>In-place<\/strong><\/td><td>Applied without an extra array using cycle detection<\/td><td>Swap along each cycle<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Key Operations on a Permutation Array<\/strong><\/h2>\n\n\n\n<p>Once you understand what a Permutation Array in DSA is, the next step is knowing what you can do with it. Here are the four operations that appear most frequently in interviews and competitive programming.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>1. Checking If an Array Is a Valid Permutation<\/strong><\/h3>\n\n\n\n<p>A valid permutation of size n must contain each integer from 0 to n\u22121 exactly once. The cleanest approach uses a boolean visited array.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def is_valid_permutation(perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;n = len(perm)\n\n&nbsp;&nbsp;&nbsp;&nbsp;visited = &#91;False] * n\n\n&nbsp;&nbsp;&nbsp;&nbsp;for x in perm:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if x &lt; 0 or x &gt;= n or visited&#91;x]:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return False\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visited&#91;x] = True\n\n&nbsp;&nbsp;&nbsp;&nbsp;return True<\/code><\/pre>\n\n\n\n<p>Time complexity: O(n). Space complexity: O(n).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>2. Inverting a Permutation<\/strong><\/h3>\n\n\n\n<p>The inverse of a permutation satisfies inv[perm[i]] = i. If perm moves element at index 2 to index 5, the inverse moves it back from 5 to 2. Inversion is essential when you need to undo a rearrangement.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def invert_permutation(perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;inv = &#91;0] * len(perm)\n\n&nbsp;&nbsp;&nbsp;&nbsp;for i, p in enumerate(perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inv&#91;p] = i\n\n&nbsp;&nbsp;&nbsp;&nbsp;return inv<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>3. In-Place Permutation Using Cycle Detection<\/strong><\/h3>\n\n\n\n<p>Applying a permutation without a result array is possible using cycle detection. Every permutation decomposes into independent cycles. For each cycle, you rotate the elements along it without needing extra storage.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def apply_inplace(arr, perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;visited = &#91;False] * len(arr)\n\n&nbsp;&nbsp;&nbsp;&nbsp;for i in range(len(arr)):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if not visited&#91;i]:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; j = i\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while not visited&#91;j]:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; visited&#91;j] = True\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; next_j = perm&#91;j]\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; arr&#91;i], arr&#91;next_j] = arr&#91;next_j], arr&#91;i]\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; j = next_j<\/code><\/pre>\n\n\n\n<p>Time complexity: O(n). Space complexity: O(n) for the visited array, or O(1) using a sign-flipping trick.<\/p>\n\n\n\n<div style=\"background-color: #099f4e; border: 3px solid #110053; border-radius: 12px; padding: 18px 22px; color: #FFFFFF; font-family: Montserrat, Helvetica, sans-serif; line-height: 1.6; box-shadow: 0 4px 12px rgba(0, 0, 0, 0.15); max-width: 800px;\">\n  <strong style=\"font-size: 22px; color: #FFFFFF;\">\ud83d\udca1 Did You Know?<\/strong>\n  <p style=\"margin-top: 14px;\">\n    The minimum number of swaps required to sort an array can be determined using the concept of <strong>cycle decomposition<\/strong> in permutations. When an array is viewed as a permutation of indices, it breaks down into disjoint cycles. Each cycle of length <em>k<\/em> requires <em>k \u2212 1<\/em> swaps to place all elements in their correct positions. As a result, the total number of swaps needed to sort the array equals <strong>n \u2212 number of cycles<\/strong>. For example, the permutation <code>[2, 0, 3, 1]<\/code> forms a single cycle of length 4, meaning it requires exactly <strong>3 swaps<\/strong> to sort. This insight is widely used in algorithm design problems involving optimal rearrangement and sorting efficiency.\n  <\/p>\n<\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>4. Composing Two Permutations<\/strong><\/h3>\n\n\n\n<p>If you have two permutations P and Q, their composition is a new permutation: composed[i] = Q[P[i]]. This represents applying P first, and then Q. Composition appears in multi-step rearrangement problems and cryptographic key scheduling.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def compose(P, Q):\n\n&nbsp;&nbsp;&nbsp;&nbsp;return &#91;Q&#91;P&#91;i]] for i in range(len(P))]<\/code><\/pre>\n\n\n\n<p><strong>Read More: <\/strong><a href=\"https:\/\/www.guvi.in\/blog\/sorting-in-data-structure-categories-types\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>Sorting in Data Structure: Categories &amp; Types<\/strong><\/a><strong>\u00a0<\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Real-World Example of a Permutation Array<\/strong><\/h2>\n\n\n\n<p>Let&#8217;s look at a practical scenario that companies like Amazon and Flipkart deal with at scale every day.<\/p>\n\n\n\n<p>Imagine a product recommendation engine storing one million products. After a machine learning model runs, it produces a ranked order for each user, stored as a permutation array, where each index represents a product slot, and the corresponding value is the product ID that fills that slot.<\/p>\n\n\n\n<p>When displaying products to the user, the system applies the permutation to the master product list in O(n) no re-sorting required. If the user&#8217;s preferences change, the system inverts the permutation to recover the original order, then efficiently applies a fresh permutation.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class RecommendationEngine:\n\n&nbsp;&nbsp;&nbsp;&nbsp;def __init__(self, products):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.products = products\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.perm = list(range(len(products)))&nbsp; # identity permutation\n\n&nbsp;&nbsp;&nbsp;&nbsp;def apply_ranking(self, perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.perm = perm\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = &#91;None] * len(self.products)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for i, p in enumerate(perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result&#91;p] = self.products&#91;i]\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return result\n\n&nbsp;&nbsp;&nbsp;&nbsp;def reset_to_original(self):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inv = &#91;0] * len(self.perm)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for i, p in enumerate(self.perm):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; inv&#91;p] = i\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.perm = inv<\/code><\/pre>\n\n\n\n<p>This same pattern is used in operating system schedulers, database query planners, and competitive programming problems like &#8216;Sort Array with Minimum Swaps&#8217; and &#8216;Reconstruct Original Array from Shuffled Output&#8217;.<\/p>\n\n\n\n<div style=\"background-color: #099f4e; border: 3px solid #110053; border-radius: 12px; padding: 18px 22px; color: #FFFFFF; font-family: Montserrat, Helvetica, sans-serif; line-height: 1.6; box-shadow: 0 4px 12px rgba(0, 0, 0, 0.15); max-width: 800px;\">\n  <strong style=\"font-size: 22px; color: #FFFFFF;\">\ud83d\udca1 Did You Know?<\/strong>\n  <p style=\"margin-top: 14px;\">\n    Many popular competitive programming problems, including <strong>First Missing Positive<\/strong> and <strong>Find All Duplicates in an Array<\/strong>, can be solved efficiently by treating the array as a form of <strong>permutation or index-mapping structure<\/strong>. Instead of using extra memory for hash tables or sets, these solutions often place each value at its \u201ccorrect\u201d index, allowing the array itself to act as a bookkeeping mechanism. Recognizing this pattern is a valuable problem-solving skill because it frequently transforms an apparently complex task into an <strong>O(n)<\/strong> time solution with constant extra space. Experienced programmers often look for clues such as values constrained to the range <code>1...n<\/code>, which commonly indicate that a permutation-based approach may be the key to an optimal solution.\n  <\/p>\n<\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>When Should You Use a Permutation Array?<\/strong><\/h2>\n\n\n\n<p>Use a permutation array when:<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; You need to track exactly where each element has moved after a rearrangement.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; You want to sort an array in-place with the minimum number of swaps.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; You need to undo a rearrangement by inverting the permutation.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; You are solving cycle detection problems on arrays in O(n) time.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; You need to compose multiple rearrangements into a single step.<\/p>\n\n\n\n<p>Avoid using a permutation array when:<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; The values in your array are not in the range [0, n\u22121]. Permutation-based tricks will not apply directly.<\/p>\n\n\n\n<p>\u2022 &nbsp; &nbsp; &nbsp; The array contains duplicates. A valid permutation requires every value to appear exactly once.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Common Mistakes When Working with Permutation Arrays<\/strong><\/h2>\n\n\n\n<p><strong>1. Assuming 1-indexed permutations: <\/strong>Most DSA problems use 0-indexed permutations. Treating perm[0] as unused introduces off-by-one errors that are difficult to debug. Always confirm the index range before writing code.<\/p>\n\n\n\n<p><strong>2. Modifying the permutation during in-place application: <\/strong>When applying a permutation in-place without a visited array, it is easy to overwrite values before they are used. Use a sign-flipping trick or a separate visited array to prevent data loss.<\/p>\n\n\n\n<p><strong>3. Confusing apply and compose: <\/strong>Applying perm to an array (result[perm[i]] = arr[i]) and composing two permutations (composed[i] = Q[P[i]]) are different operations. Mixing them up produces incorrect output that can be hard to trace.<\/p>\n\n\n\n<p><strong>4. Not validating input before in-place operations: <\/strong>Passing an invalid permutation one with duplicates or out-of-range values into a cycle-detection algorithm causes undefined behaviour. Always validate the permutation first, especially in interview settings where tricky inputs are common.<\/p>\n\n\n\n<p><strong>5. Using O(n log n) sort to validate: <\/strong>Sorting the array to check if it is a valid permutation works but is unnecessary. A simple boolean visited array gives O(n) time, faster and cleaner for large inputs.<\/p>\n\n\n\n<p>Want to master arrays, permutations, graphs, and dynamic programming with real projects and mentorship? Check out <a href=\"https:\/\/www.guvi.in\/courses\/programming\/dsa-using-python\/?utm_source=blog&amp;utm_medium=hyperlink&amp;utm_campaign=What+is+a+Permutation+Array+in+DSA\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>HCL GUVI&#8217;s Data Structures &amp; Algorithms Programme<\/strong><\/a> designed for students and working professionals who want to crack top product-based company interviews with structured, hands-on learning.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>As data structures continue to form the backbone of software engineering interviews and real-world systems, mastering concepts like the Permutation Array in DSA gives you a meaningful edge. From applying permutations in O(n) and inverting them efficiently, to detecting cycles and composing rearrangements, each operation unlocks a whole class of problems that would otherwise seem difficult. Start by writing a valid permutation checker, then build up to in-place application using cycle detection. These two exercises alone will make the concept click. From there, explore LeetCode problems like &#8216;Find All Duplicates in an Array&#8217; and &#8216;First Missing Positive&#8217; to see permutation thinking in action.\u00a0<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>FAQ<\/strong><\/h2>\n\n\n<div id=\"rank-math-faq\" class=\"rank-math-block\">\n<div class=\"rank-math-list \">\n<div id=\"faq-question-1781500706287\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">1.\u00a0 \u00a0 <strong>What is a permutation array in DSA?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>A permutation array in DSA is an array of length n that contains each integer from 0 to n\u22121 exactly once, representing a specific rearrangement or mapping of elements from their original positions.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781500718990\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">2.\u00a0 \u00a0 <strong>How do you check if an array is a valid permutation?\u00a0<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0Create a boolean visited array of size n. For each element, mark it as visited. If any element is out of range [0, n\u22121] or is marked visited twice, the array is not a valid permutation.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781500727524\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">3.\u00a0 \u00a0 <strong>What is the inverse of a permutation array?\u00a0<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0The inverse permutation inv satisfies inv[perm[i]] = i for all i. It reverses the mapping so applying the permutation and then its inverse restores the original order of elements.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781500737038\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">4.\u00a0 \u00a0 <strong>How do you apply a permutation to an array in O(n) time?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/strong>Create a result array of the same size. For each index i, set result[perm[i]] = arr[i]. This rearranges the array in a single pass with O(n) time and O(n) space.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781500747878\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">5.\u00a0 \u00a0 <strong>What is an in-place permutation and how does it work?\u00a0<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>\u00a0\u00a0\u00a0An in-place permutation rearranges elements without a result array using cycle detection. For each unvisited cycle, elements are rotated along it using O(1) extra space beyond a visited marker.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781500758478\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">6.\u00a0 \u00a0 <strong>What is the minimum number of swaps to sort using a permutation?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p><strong>\u00a0\u00a0\u00a0\u00a0<\/strong>The minimum swaps equals n minus the number of cycles in the permutation. A cycle of length k requires k\u22121 swaps to resolve, so more cycles means fewer swaps needed overall.<\/p>\n\n<\/div>\n<\/div>\n<\/div>\n<\/div>","protected":false},"excerpt":{"rendered":"<p>Quick TL;DR Introduction Many beginners working through DSA problems stumble upon arrays that seem sorted but are not, and the missing concept is almost always the permutation array. A Permutation Array in DSA is a fundamental building block that powers everything from sorting algorithms to graph traversal. Understanding how it works, how to apply it, [&hellip;]<\/p>\n","protected":false},"author":63,"featured_media":115879,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17],"tags":[],"views":"20","authorinfo":{"name":"Vishalini Devarajan","url":"https:\/\/www.guvi.in\/blog\/author\/vishalini\/"},"thumbnailURL":"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2026\/06\/what-is-a-permutation-array-in-dsa-300x116.webp","_links":{"self":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/115758"}],"collection":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/users\/63"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/comments?post=115758"}],"version-history":[{"count":4,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/115758\/revisions"}],"predecessor-version":[{"id":116658,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/115758\/revisions\/116658"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/media\/115879"}],"wp:attachment":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/media?parent=115758"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/categories?post=115758"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/tags?post=115758"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}