How to optimize my function, which takes a positive integer and returns the next smaller positive integer?

Question

I am trying to write a function that takes a positive integer and returns the next smaller positive integer containing the same digits, and -1 when there is no smaller number containing the same digits.

For example: nextSmaller(21) == 12 nextSmaller(531) == 513 nextSmaller(2071) == 2017 

I wrote code that solves this, but I really don't know how to optimize it. could you help me? It works pretty fast on repl.it, but when I send it, it says that it takes more than 1200 ms and does not allow me to send it, even if all the tests pass.

 function nextSmaller(n) { var nArray= n.toString().split("") var minimumNum = 1 + Array(nArray.length).join('0') for(var i=n-1; i >= minimumNum; i--) { var newNumArray = i.toString().split(''); var counter = 0; for (var j=0; j<newNumArray.length; j++) { if (nArray.indexOf(newNumArray[j]) > -1) { counter++ nArray.splice(nArray.indexOf(newNumArray[j]), 1) if (counter === n.toString().split("").length) { return i; } } } nArray = n.toString().split(""); if (i === Number(minimumNum)) return -1; } } 

Answer 1

Your code can be optimized a bit, for example, you can use the break statement in your inner loop to move to the next number as soon as you find out that the current one will not work (which should make it work in about half the cases, but for n like 91234567 ) is still pretty slow, but instead of n.toString().split("").length , a variable is used in the loop, so you only need to convert n to an array once.

 function nextSmaller(n) { var nArray = n.toString().split("") var length = nArray.length; var minimumNum = 1 + Array(length).join('0') for(var i=n-1; i >= minimumNum; i--) { var newNumArray = i.toString().split(''); var counter = 0; for (var j=0; j<newNumArray.length; j++) { if (nArray.indexOf(newNumArray[j]) < 0) break; counter++ nArray.splice(nArray.indexOf(newNumArray[j]), 1) if (counter === length) { return i; } } nArray = n.toString().split(""); } return -1; } 

There is a very efficient algorithm for computing the next permutation, which can be easily adapted to obtain the previous one (and returns -1 if the resulting permutation starts from 0 ). I adapted this algorithm for this:

 [21,531,2071,912345678,9123545678,915345678].forEach( x => console.log( nextSmaller( x ) ) ); function nextSmaller(n) { const arr = ( n + '' ).split( '' ).map( Number ); // Find longest non-decreasing suffix let i, prev = 9; for ( i = arr.length; i--; ) { if ( arr[ i ] > prev ) break; prev = arr[ i ]; } // If whole sequence is non-decreasing, // it is already the smallest permutation if ( i < 0 ) return -1; const pivot_i = i; const pivot = arr[ pivot_i ]; for ( i = arr.length; i--; ) { if ( arr[ i ] < pivot ) break; } arr[ pivot_i ] = arr[ i ]; arr[ i ] = pivot; if ( arr[ 0 ] === 0 ) return -1; return +arr.slice( 0, pivot_i + 1 ).concat( arr.slice( pivot_i + 1 ).reverse( ) ).join(''); } 

Answer 2

The algorithm may be as follows:

• For input number n find all numbers that are formed with some permutations from the same digits and sort these numbers. For example, if n=213 , we get a sorted list as [123, 132, 213, 231, 312, 321] . (e.g. Permutation in JavaScript? may help you).

• Find index i numbers n in the sorted list. If i>0 returns the number in index i-1 else return -1 (if it is the smallest number that appears in the first position of the sorted list).

Another alternative algorithm might be the following:

Decrease the number n until you find one that has exactly the same numbers (in a different order, you can sort the numbers and check for equality).

The most efficient one will be similar to the one mentioned by @Paulpro ( https://www.nayuki.io/page/next-lexicographical-permutation-algorithm )

• Find longest non-decreasing suffix from decimal string representation n .
• If the whole string n does not decrease, then return -1 (there can be no less than them).
• Otherwise, select the digit immediately before the suffix begins, like pivot and replace it with the number ( the leftmost and) of the largest in suffix , which is smaller than the pivot . Return this number.