Next Permutation of Array in DSA C - Execution Trace

Concept Flow - Next Permutation of Array

Start from right end

↓

Find first pair where nums[i

↓

If no such pair, reverse whole array -> Done

Yes↓

Find element nums[j

↓

Swap nums[i

↓

Reverse subarray from i+1 to end

↓

Done with next permutation

Find the next lexicographically greater permutation by locating a pivot, swapping, and reversing the suffix.

Execution Sample

DSA C

int i = n - 2;
while (i >= 0 && nums[i] >= nums[i+1]) i--;
if (i >= 0) {
  int j = n - 1;
  while (nums[j] <= nums[i]) j--;
  swap(nums[i], nums[j]);
}
reverse(nums + i + 1, nums + n);

This code finds the next permutation of the array nums in-place.

Execution Table

Step	Operation	i	j	Array State	Notes
1	Initialize i = n-2	4	-	[1, 2, 3, 6, 5, 4]	Start from second last index
2	Check nums[i] >= nums[i+1]	4	-	[1, 2, 3, 6, 5, 4]	5 >= 4 is True, decrement i
3	Check nums[i] >= nums[i+1]	3	-	[1, 2, 3, 6, 5, 4]	6 >= 5 is True, decrement i
4	Check nums[i] >= nums[i+1]	2	-	[1, 2, 3, 6, 5, 4]	3 >= 6 is False, stop
5	Initialize j = n-1	2	5	[1, 2, 3, 6, 5, 4]	j starts at last index
6	Check nums[j] <= nums[i]	2	5	[1, 2, 3, 6, 5, 4]	4 <= 3 is False, stop
7	Swap nums[i] and nums[j]	2	5	[1, 2, 4, 6, 5, 3]	Swap 3 and 4
8	Reverse subarray from i+1 to end	2	5	[1, 2, 4, 3, 5, 6]	Reverse [6,5,3] to [3,5,6]
9	Done	-	-	[1, 2, 4, 3, 5, 6]	Next permutation found

💡 After reversing suffix, next permutation is complete.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	Final
i	4	3	2	2	2	-
j	-	-	-	5	5	-
Array	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 3, 6, 5, 4]	[1, 2, 4, 6, 5, 3]	[1, 2, 4, 3, 5, 6]

Key Moments - 3 Insights

Why do we start searching for i from the right end (n-2) and not from the left?

Because the next permutation changes the suffix to the smallest bigger arrangement. Starting from right finds the longest non-increasing suffix quickly (see steps 1-4 in execution_table).

What if no i is found such that nums[i] < nums[i+1]?

It means the array is in descending order, the highest permutation. We reverse the whole array to get the lowest permutation (not shown in this example).

Why do we reverse the subarray after swapping nums[i] and nums[j]?

Because the suffix after i was in descending order. Reversing it makes it ascending, which is the smallest order to get the next permutation (see step 8).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of i?

A 3

B 1

C 2

D 4

💡 Hint

Check the 'i' column in execution_table row with Step '4'

At which step does the array first change from the original?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look for the first step where 'Array State' differs from original in execution_table

If the array was [3, 2, 1], what would happen according to the concept_flow?

A No i found, reverse whole array

B Only swap first two elements

C Find i and j, swap, then reverse suffix

D No changes, array is already next permutation

💡 Hint

Refer to concept_flow step 'If no such pair, reverse whole array -> Done'

Concept Snapshot

Next Permutation Algorithm:
- Start from right, find first i where nums[i] < nums[i+1]
- If none, reverse entire array (lowest permutation)
- Else find j from right where nums[j] > nums[i]
- Swap nums[i] and nums[j]
- Reverse subarray from i+1 to end
- Result is next lexicographically greater permutation

Full Transcript

The next permutation algorithm finds the next bigger arrangement of numbers by scanning from the right to find a pivot where the order breaks ascending. If none found, the array is reversed to the smallest order. Otherwise, it swaps the pivot with the next bigger number on the right and reverses the suffix to get the next permutation. This process is done in-place and ensures the next lexicographical order.

Practice

1. What does the next permutation of an array represent?

easy

A. The next lexicographically greater arrangement of the array elements

B. The array sorted in ascending order

C. The array reversed

D. The smallest element moved to the front

Solution

1. Step 1: Understand the concept of permutation order

   Permutations can be ordered lexicographically like words in a dictionary.

2. Step 2: Define next permutation

   The next permutation is the immediate next arrangement that is greater than the current one in lexicographic order.

3. Final Answer:

   The next lexicographically greater arrangement of the array elements -> Option A

4. Quick Check:

   Next permutation = next bigger arrangement [OK]

Hint: Next permutation means next bigger arrangement [OK]

Common Mistakes:

• Confusing next permutation with sorting ascending
• Thinking next permutation is just reversing array
• Assuming next permutation always moves smallest element front

2. Which of the following C code snippets correctly swaps two integers a and b using a temporary variable?

easy

A. a = a + b; b = a - b; a = a - b;

B. a = b; b = a;

C. int temp; a = b; b = temp;

D. int temp = a; a = b; b = temp;

Solution

1. Step 1: Understand swapping with a temporary variable

   Use a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   int temp = a; a = b; b = temp; correctly uses a temp variable to swap values safely.

3. Final Answer:

   int temp = a; a = b; b = temp; -> Option D

4. Quick Check:

   Swap with temp variable = int temp = a; a = b; b = temp; [OK]

Hint: Use temp variable to swap safely [OK]

Common Mistakes:

• Assigning a = b; b = a; loses original value
• Using arithmetic swap without considering overflow
• Not declaring or initializing temp variable

3. What is the output of the following C code that finds the next permutation of the array arr = {1, 3, 2}?

void nextPermutation(int* arr, int n) {
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (arr[j] <= arr[i]) j--;
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
    int left = i + 1, right = n - 1;
    while (left < right) {
        int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
        left++; right--;
    }
}

int main() {
    int arr[] = {1, 3, 2};
    nextPermutation(arr, 3);
    for (int i = 0; i < 3; i++) printf("%d ", arr[i]);
    return 0;
}

medium

A. 1 2 3

B. 1 3 2

C. 2 1 3

D. 3 1 2

Solution

1. Step 1: Find the pivot index i

   Start from right: arr[1]=3, arr[2]=2, since 3 >= 2, i moves left to 0 where arr[0]=1 < arr[1]=3, so i=0.

2. Step 2: Find j to swap with i

   From right, find j where arr[j] > arr[i]: arr[2]=2 > 1, so j=2. Swap arr[0] and arr[2]: arr becomes {2, 3, 1}.

3. Step 3: Reverse suffix after i

   Reverse elements from i+1=1 to end: reverse {3,1} to {1,3}. Final array: {2,1,3}.

4. Final Answer:

   2 1 3 -> Option C

5. Quick Check:

   Next permutation of [1,3,2] = [2,1,3] [OK]

Hint: Swap pivot with next bigger, then reverse suffix [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping with wrong element j
• Stopping pivot search too early

4. Identify the bug in the following C function that attempts to compute the next permutation of an array arr of size n:

void nextPermutation(int* arr, int n) {
    int i = n - 1;
    while (i > 0 && arr[i] <= arr[i - 1]) i--;
    if (i > 0) {
        int j = n - 1;
        while (arr[j] <= arr[i - 1]) j--;
        int temp = arr[i - 1]; arr[i - 1] = arr[j]; arr[j] = temp;
    }
    int left = i, right = n - 1;
    while (left < right) {
        int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
        left++; right--;
    }
}

medium

A. The swap should be done with arr[i], not arr[i - 1]

B. The initial value of i should be n - 2, not n - 1

C. The reversal loop should start from i - 1, not i

D. The comparison in the first while loop should be arr[i] >= arr[i - 1]

Solution

1. Step 1: Analyze the pivot search loop

   The pivot is found by moving left from n-2, but here i starts at n-1, which skips checking the last pair correctly.

2. Step 2: Correct initial i value

   Setting i = n - 2 ensures the loop compares arr[i] and arr[i+1] properly to find the pivot.

3. Final Answer:

   The initial value of i should be n - 2, not n - 1 -> Option B

4. Quick Check:

   Pivot search starts at n-2 index [OK]

Hint: Start pivot search at n-2 index [OK]

Common Mistakes:

• Starting pivot index at n-1 causes missed comparisons
• Incorrect comparison operators in loops
• Reversing wrong subarray segment

5. Given an array arr = {5, 4, 7, 5, 3, 2}, what will be the next permutation after applying the standard next permutation algorithm?

hard

A. [5, 5, 2, 3, 4, 7]

B. [5, 4, 7, 5, 3, 2]

C. [5, 4, 7, 5, 2, 3]

D. [7, 2, 3, 4, 5, 5]

Solution

1. Step 1: Find pivot index i

   Traverse from right: arr[4]=3, arr[5]=2 (3 >= 2), move left; arr[3]=5, arr[4]=3 (5 >= 3), move left; arr[2]=7, arr[3]=5 (7 >= 5), move left; arr[1]=4, arr[2]=7 (4 < 7), so i=1.

2. Step 2: Find j to swap with i

   From right, find j where arr[j] > arr[i]: arr[5]=2 (2 > 4? No), arr[4]=3 (3 > 4? No), arr[3]=5 (5 > 4? Yes), so j=3. Swap arr[1] and arr[3]: arr becomes {5,5,7,4,3,2}.

3. Step 3: Reverse suffix after i

   Reverse elements from i+1=2 to end: reverse {7,4,3,2} to {2,3,4,7}. Final array: {5,5,2,3,4,7}.

4. Final Answer:

   [5, 5, 2, 3, 4, 7] -> Option A

5. Quick Check:

   Next permutation of [5,4,7,5,3,2] = [5,5,2,3,4,7] [OK]

Hint: Swap pivot with next bigger, reverse suffix [OK]

Common Mistakes:

• Not finding correct pivot index
• Swapping with wrong element j
• Not reversing suffix correctly