Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Next Permutation Problem

Given a sequence, return its next lexicographically greater permutation. If such a permutation does not exist then return it in ascending order. 

Try to solve the problem with a constant amount of additional memory. 

Example One

Input: [1, 3, 2]

Output: [2, 1, 3]

Example Two

Input: [2, 2, 1]

Output: [1, 2, 2]

Constraints:

● 1

● 0

Solutions

We provided two solutions. Let us assume that n is the size of the sequence.

1) brute_force_solution.cpp

First, We need to generate all the permutations of the given array but before that, we need to create a copy of it so that we have the original permutation because we will need it later to compare with each possible permutation of the array. 

1. Sort the array.

2. Generate permutations in the lexicographic order.

3. Compare the generated permutations to the original permutation of the given array.

4. When both permutations become equal, skip all equal permutations of original permutation.

5. After skipping equal permutations, get the next greater permutation. 

Time Complexity:

O(n * n!).

Sorting array of size n will take O(n * log n) time. There are n! possible permutations of the array of size n. Generating all of them will contribute O(n!) to time complexity. Now, we have n! permutations each of size n. Comparing given permutation to each of permutation will add O(n * n!) to time complexity. Hence, our overall time complexity will be O(n * n!).

Auxiliary Space Used:

O(n * n!).

Creating a copy of the original array will take O(n) space. We are storing all permutations of the array of size n. There are n! possible permutations and each of size n. Hence auxiliary space used by brute force approach is O(n * n!).

Space Complexity:

O(n * n!).

Memory used for input = O(n)

Memory used for output = O(n)

Auxiliary space = O(n * n!)

Total space complexity = O(n * n!)


// -------- START --------

void generate_all_permutations(vector arr, vector> &permutations, int index)
{
    if (index == arr.size())
    {
        permutations.push_back(arr);
        return;
    }

    // Swap all of the values from greater or equal indices to 'index' to generate all possible permutations.
    for (int i = index; i < arr.size(); i++)
    {
        swap(arr[i], arr[index]);
        generate_all_permutations(arr, permutations, index + 1);
        swap(arr[i], arr[index]);
    }
}

vector next_permutation(vector arr)
{
    vector> all_permutations;

    vector dupArr(arr.begin(), arr.end());

    sort(dupArr.begin(), dupArr.end());

    generate_all_permutations(dupArr, all_permutations, 0);

    int total_permutations = all_permutations.size();
    for (int i = 0; i < total_permutations; i++)
    {
        if (all_permutations[i] == arr)
        {
            /**
             * The given array can have duplicates but our algorithm does not take that into consideration.
             * So the same permutation can appear more than once while generating all of the permutations.
             * Hence, we need to skip such equal permutations.
             */
            while (i < total_permutations && all_permutations[i] == arr)
            {
                i++;
            }
            arr = all_permutations[i % total_permutations];
            break;
        }
    }
    return arr;
}

// -------- END --------


2) optimized_solution.cpp

We will move step by step with an example of n = 6, array = [1, 4, 6, 5, 3, 2].

● A greater permutation than the current permutation can be formed only if there exists an element at index i which is strictly smaller than an element at index j where i < j. For example:

○ We can get a greater permutation if we swap the values at index 0 with any value at index between 1 to 5. If we swap the value at index 0 with the value at index 5, we get the permutation [2, 4, 6, 5, 3, 1] which is a greater permutation than the permutation [1, 4, 6, 5, 3, 2].

○ We also can get a greater permutation by swapping the value at index 1 with the values at indices 2 and 3.

● In order to get the lexicographically next permutation, we need to modify the smallest suffix which has the above property when considered as an independent sequence. Let us assume that the smallest suffix which has the above property starts at index i. We have two indices for the possible value of i for the given example. They are 0 and 1. Finding the value of i is trivial and left as an exercise to the reader.

● After finding i, which in our case is equal to 1, we need to find the last index j in [i+1 … n] such that array[i] < array[j]. In our example, j equals 3. We will now swap the values at index i and j.

● After swapping the values at i and j, the array becomes [1, 5, 6, 4, 3, 2] which is a greater permutation than [1, 4, 6, 5, 3, 2]. But there are few other permutations which lie between [1, 4, 6, 5, 3, 2] and [1, 5, 6, 4, 3, 2].

● The way we picked i and j ensures that after swapping i and j, all of the following statements hold:

○ We will get a permutation larger than the initial one.

○ The longest possible prefix of the array will remain unmodified.

○ The smallest possible number will be placed at index j after swapping.

○ The number in the indices between i+1 to n-1 will remain sorted in non-increasing order.

● After replacing the value at index i with a greater number from index j, we can shuffle the numbers between the indices i+1 to n-1 and still get a larger permutation than the initial one. The permutation where the numbers from i+1 to n-1 are sorted in non-decreasing order is indeed the smallest one among them. Now as the segment is sorted in non-increasing order, we will just reverse it as the last step of the algorithm.

● After reversing array[i+1 … n], the array becomes [1, 5, 2, 3, 4, 6] which is the next permutation for the initial array.

Time Complexity:

O(n).

Finding index i contributes to O(n) time complexity. Finding index j may take O(n) time. Reversing the array contributes O(n) time. Hence, our overall time complexity becomes O(n).

Auxiliary Space Used:

O(1).

We used a constant amount of additional memory. 

Space Complexity:

O(n).

Memory used for input = O(n)

Memory used for output = O(n)

Auxiliary space = O(1)

Total space complexity = O(n)


// -------- START --------

vector next_permutation(vector arr)
{
    if (arr.size() < 2)
    {
        return arr;
    }

    int n = arr.size();
    int index;
    for (index = n - 1; index > 0; index--)
    {
        if (arr[index] > arr[index - 1])
        {
            break;
        }
    }

    /**
     * The value of index being equal to zero implies that the array is sorted in non-increasing order.
     * Reversing the array will sort the array in ascending order.
     */
    if (index == 0)
    {
        reverse(arr.begin(), arr.end());
        return arr;
    }

    // Find the smallest number which is greater than the pivot element and swap them.
    int pivotIndex = index - 1;
    while (index < n && arr[index] > arr[pivotIndex])
    {
        index++;
    }
    swap(arr[pivotIndex], arr[index - 1]);

    reverse(arr.begin() + pivotIndex + 1, arr.end());
    return arr;
}

// -------- END --------


Try yourself in the Editor

Note: Input and Output will already be taken care of.

Next Permutation Problem

Given a sequence, return its next lexicographically greater permutation. If such a permutation does not exist then return it in ascending order. 

Try to solve the problem with a constant amount of additional memory. 

Example One

Input: [1, 3, 2]

Output: [2, 1, 3]

Example Two

Input: [2, 2, 1]

Output: [1, 2, 2]

Constraints:

● 1

● 0

Solutions

We provided two solutions. Let us assume that n is the size of the sequence.

1) brute_force_solution.cpp

First, We need to generate all the permutations of the given array but before that, we need to create a copy of it so that we have the original permutation because we will need it later to compare with each possible permutation of the array. 

1. Sort the array.

2. Generate permutations in the lexicographic order.

3. Compare the generated permutations to the original permutation of the given array.

4. When both permutations become equal, skip all equal permutations of original permutation.

5. After skipping equal permutations, get the next greater permutation. 

Time Complexity:

O(n * n!).

Sorting array of size n will take O(n * log n) time. There are n! possible permutations of the array of size n. Generating all of them will contribute O(n!) to time complexity. Now, we have n! permutations each of size n. Comparing given permutation to each of permutation will add O(n * n!) to time complexity. Hence, our overall time complexity will be O(n * n!).

Auxiliary Space Used:

O(n * n!).

Creating a copy of the original array will take O(n) space. We are storing all permutations of the array of size n. There are n! possible permutations and each of size n. Hence auxiliary space used by brute force approach is O(n * n!).

Space Complexity:

O(n * n!).

Memory used for input = O(n)

Memory used for output = O(n)

Auxiliary space = O(n * n!)

Total space complexity = O(n * n!)


// -------- START --------

void generate_all_permutations(vector arr, vector> &permutations, int index)
{
    if (index == arr.size())
    {
        permutations.push_back(arr);
        return;
    }

    // Swap all of the values from greater or equal indices to 'index' to generate all possible permutations.
    for (int i = index; i < arr.size(); i++)
    {
        swap(arr[i], arr[index]);
        generate_all_permutations(arr, permutations, index + 1);
        swap(arr[i], arr[index]);
    }
}

vector next_permutation(vector arr)
{
    vector> all_permutations;

    vector dupArr(arr.begin(), arr.end());

    sort(dupArr.begin(), dupArr.end());

    generate_all_permutations(dupArr, all_permutations, 0);

    int total_permutations = all_permutations.size();
    for (int i = 0; i < total_permutations; i++)
    {
        if (all_permutations[i] == arr)
        {
            /**
             * The given array can have duplicates but our algorithm does not take that into consideration.
             * So the same permutation can appear more than once while generating all of the permutations.
             * Hence, we need to skip such equal permutations.
             */
            while (i < total_permutations && all_permutations[i] == arr)
            {
                i++;
            }
            arr = all_permutations[i % total_permutations];
            break;
        }
    }
    return arr;
}

// -------- END --------


2) optimized_solution.cpp

We will move step by step with an example of n = 6, array = [1, 4, 6, 5, 3, 2].

● A greater permutation than the current permutation can be formed only if there exists an element at index i which is strictly smaller than an element at index j where i < j. For example:

○ We can get a greater permutation if we swap the values at index 0 with any value at index between 1 to 5. If we swap the value at index 0 with the value at index 5, we get the permutation [2, 4, 6, 5, 3, 1] which is a greater permutation than the permutation [1, 4, 6, 5, 3, 2].

○ We also can get a greater permutation by swapping the value at index 1 with the values at indices 2 and 3.

● In order to get the lexicographically next permutation, we need to modify the smallest suffix which has the above property when considered as an independent sequence. Let us assume that the smallest suffix which has the above property starts at index i. We have two indices for the possible value of i for the given example. They are 0 and 1. Finding the value of i is trivial and left as an exercise to the reader.

● After finding i, which in our case is equal to 1, we need to find the last index j in [i+1 … n] such that array[i] < array[j]. In our example, j equals 3. We will now swap the values at index i and j.

● After swapping the values at i and j, the array becomes [1, 5, 6, 4, 3, 2] which is a greater permutation than [1, 4, 6, 5, 3, 2]. But there are few other permutations which lie between [1, 4, 6, 5, 3, 2] and [1, 5, 6, 4, 3, 2].

● The way we picked i and j ensures that after swapping i and j, all of the following statements hold:

○ We will get a permutation larger than the initial one.

○ The longest possible prefix of the array will remain unmodified.

○ The smallest possible number will be placed at index j after swapping.

○ The number in the indices between i+1 to n-1 will remain sorted in non-increasing order.

● After replacing the value at index i with a greater number from index j, we can shuffle the numbers between the indices i+1 to n-1 and still get a larger permutation than the initial one. The permutation where the numbers from i+1 to n-1 are sorted in non-decreasing order is indeed the smallest one among them. Now as the segment is sorted in non-increasing order, we will just reverse it as the last step of the algorithm.

● After reversing array[i+1 … n], the array becomes [1, 5, 2, 3, 4, 6] which is the next permutation for the initial array.

Time Complexity:

O(n).

Finding index i contributes to O(n) time complexity. Finding index j may take O(n) time. Reversing the array contributes O(n) time. Hence, our overall time complexity becomes O(n).

Auxiliary Space Used:

O(1).

We used a constant amount of additional memory. 

Space Complexity:

O(n).

Memory used for input = O(n)

Memory used for output = O(n)

Auxiliary space = O(1)

Total space complexity = O(n)


// -------- START --------

vector next_permutation(vector arr)
{
    if (arr.size() < 2)
    {
        return arr;
    }

    int n = arr.size();
    int index;
    for (index = n - 1; index > 0; index--)
    {
        if (arr[index] > arr[index - 1])
        {
            break;
        }
    }

    /**
     * The value of index being equal to zero implies that the array is sorted in non-increasing order.
     * Reversing the array will sort the array in ascending order.
     */
    if (index == 0)
    {
        reverse(arr.begin(), arr.end());
        return arr;
    }

    // Find the smallest number which is greater than the pivot element and swap them.
    int pivotIndex = index - 1;
    while (index < n && arr[index] > arr[pivotIndex])
    {
        index++;
    }
    swap(arr[pivotIndex], arr[index - 1]);

    reverse(arr.begin() + pivotIndex + 1, arr.end());
    return arr;
}

// -------- END --------


Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts