Examples:

Input -> output 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

**Problem explanation:**

Given a number, find the next highest number, using the same digits given in the array.

**For example:**

1234 -> 1243

Here 1235 is invalid because digit “5” is not in the input array. Hence the next highest number will be “1243”.

**Another example:**

4132 -> 4213

**One more, ok last one:**

4321 -> none.

Because the number is already sorted in descending order, cannot find the next higher element.

### This problem can be solved in 3 ways.

**Brute force approach****Direct Solution****Using inbuilt function. [Not really a solution, good to know]**

We shall look into all the 3 solutions below.

## 1. Brute force approach.

The solution is simple.

We increment the number by one and check if all the number are present in the given array.

If all the numbers are accounted for we take that number, else we search again.

Obviously, this will take a lot of time. First, you can give this solution, if the interviewer is not satisfied, go to the 2^{nd} solution.

## 2. Direct Solution

In this approach, we take 2 pointers.

**Step 1:** In the given array, from the right side, find a number that is not in ascending order. Mark that number as num_1.

**Step 2:** Then we find another digit from the right of num_1, such that it is the smallest number but greater than num_1, and mark it as num_2.

**Step 3:** Swap num_1, num_2.

**Step 4:** Sort the numbers from the right of the original position of num_1.

#### We shall analyze the above steps with the help of an example:

Given array:

3 2 8 4 1

From step 1, searching from right, “2” is breaking the ascending order of “1 4 8”. Mark it as num_1.

From step 2: “4” is the smallest number greater than num_1. Mark it as num_2.

From step 3: Swap num_1 and num_2

From step 4: Sort the array in ascending order from the original position of num_1.

We shall get our desired result.

## Solution 3: Use library function:

Use “next_permutation()” function found in STL in C++.

## Solution in C++

/* * File : Next_Permutation.cpp */ #include<iostream> #include<vector> using namespace std; void next_permutation_using_direct_approach(vector<int>& nums) { int len = nums.size(); int num_1_index; int num_2_index; //step 1: find the index of num 1 so that it is not in ascending order for (num_1_index = len - 2; num_1_index >= 0; num_1_index--) { if (nums[num_1_index] < nums[num_1_index + 1]) { break; } } //if we did not find, we just reverse the numbers. // example: if the number is 123, then 321 will be the next heighest permutation if (num_1_index < 0) { reverse(nums.begin(), nums.end()); } else { //step 2, we find second number index, such that it is greater than num 1 for (num_2_index = len - 1; num_2_index > num_1_index; num_2_index--) { //if we find, break the loop if (nums[num_2_index] > nums[num_1_index]) { break; } } // step 3: swap the numbers swap(nums[num_1_index], nums[num_2_index]); //step 4: reverse the numbers reverse(nums.begin() + num_1_index + 1, nums.end()); } } void nextPermutation_using_library_function(vector<int>& nums) { next_permutation(begin(nums), end(nums)); } int main() { vector<int> number; number.push_back(3); number.push_back(2); number.push_back(8); number.push_back(4); number.push_back(1); for (int i = 0; i < number.size(); i++) { cout <<number[i] << " "; } cout<<endl; //nextPermutation_using_library_function (number); next_permutation_using_direct_approach (number); for (int i = 0; i < number.size(); i++) { cout <<number[i] << " "; } cout<<endl; }

**Output**

3 2 8 4 1 3 4 1 2 8

## No Responses