Next Permutation of Array in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the first index from the end where the array value is less than the next value.

DSA C

int i = n - 2;
while (i >= 0 && nums[i] [1]= nums[i + 1]) {
    i--;
}

Drag options to blanks, or click blank then click option'

A>

B<

C>=

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' instead of '>=' causes the loop to stop too early.

Using '>' misses the case when nums[i] equals nums[i+1].

We look for the first index i from the right where nums[i] is less than nums[i+1], so we continue while nums[i] >= nums[i+1].

2fill in blank

medium

Complete the code to find the first index from the end where the array value is greater than nums[i].

DSA C

int j = n - 1;
while (j >= 0 && nums[j] [1]= nums[i]) {
    j--;
}

Drag options to blanks, or click blank then click option'

A>=

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '<=' causes skipping equal values.

Using '>=' causes the loop to stop too late.

We want to find the first index j from the right where nums[j] is greater than nums[i], so we continue while nums[j] <= nums[i].

3fill in blank

hard

Fix the error in swapping nums[i] and nums[j].

DSA C

int temp = nums[i];
nums[i] = nums[[1]];
nums[j] = temp;

Drag options to blanks, or click blank then click option'

Ai + 1

Bj

Ci

Dj - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with nums[i] again causes no change.

Using wrong indices causes incorrect swap.

To swap nums[i] and nums[j], we assign nums[i] = nums[j], then nums[j] = temp.

4fill in blank

hard

Fill both blanks to reverse the subarray from i+1 to end.

DSA C

int start = i + 1;
int end = n - 1;
while (start [1] end) {
    int temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start[2];
    end--;
}

Drag options to blanks, or click blank then click option'

A<

B<=

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes swapping the middle element twice.

Using '--' on start moves it backward incorrectly.

We reverse while start < end, and increment start with start++ each loop.

5fill in blank

hard

Fill all three blanks to complete the next permutation function.

DSA C

void nextPermutation(int* nums, int n) {
    int i = n - 2;
    while (i >= 0 && nums[i] [1]= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = n - 1;
        while (j >= 0 && nums[j] [2]= nums[i]) {
            j--;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    int start = i + 1;
    int end = n - 1;
    while (start [3] end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

Drag options to blanks, or click blank then click option'

A>=

B<=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up comparison operators causes incorrect next permutation.

Using wrong loop conditions leads to infinite loops or wrong output.

The blanks correspond to the conditions and loop control: i moves left while nums[i]>=nums[i+1], j moves left while nums[j]<=nums[i], and reversing while start

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