How to use Dynamic Programming In Javascript
In this approach, we are using the DP approach where we are iterating over the array by maintaining an array ‘dp’, where each element stores the index of the immediate smaller element to its right After each iteration, the ‘dp’ is updated with the actual values of the next smaller element and the last element is set as -1.
Example: This example implements the above mentioned approach
Javascript
function nextSmallest(inputArray, arrayLength) { let dp = new Array(arrayLength).fill(-1); for (let i = 0; i < arrayLength; i++) { for (let j = i + 1; j < arrayLength; j++) { if ( inputArray[j] < inputArray[i] && (dp[i] === -1 || inputArray[j] > inputArray[dp[i]]) ) { dp[i] = j; } } } for (let i = 0; i < arrayLength; i++) { if (dp[i] !== -1) { dp[i] = inputArray[dp[i]]; } } dp[arrayLength - 1] = -1; return dp; } let inputArr1 = [11, 13, 21, 3]; let inputArr2 = [1, 2, 3, 4]; console.log( nextSmallest(inputArr1, inputArr1.length) .join( " " )); console.log( nextSmallest(inputArr2, inputArr2.length) .join( " " )); |
3 3 3 -1 -1 -1 -1 -1
JavaScript Program to Find Next Smaller Element
In this JavaScript article, we will see how we can find the next smaller elements from the first input Array. We have given the array in which we need to print the next smaller element. The next smaller element is an element that is present after the target element in the input array. For elements for which no next smaller elements are present then the -1 will be printed.
Examples:
Input: inputArray=[ 11, 13, 21, 3 ]
Output: 3 3 3 -1
Explanation:
For the rightmost element (3), the next smaller is always -1 since there are no elements to its right.
Element: 3 => -1
Now, let's find the ISE for each element:
Element: 11: The next smaller element to its right is 3.
Element: 13: The next smaller element to its right is 3.
Element: 21: The next smaller element to its right is 3.
Element: 3: The rightmost element, so ISE is -1.
For printing the next Smaller Element we have four different approaches in JavaScript language. We have mentioned these approaches below:
- Using Dynamic Programming Approach
- Using the Stack Data Structure approach
- Using the Reverse Iteration of the Elements approach
- Using the Array Map and Find approach