Leetcode 556. Next Greater Element III

July 22, 2018

Introduction

It is a medium level algorithm, and it is not easy to come out the idea to find smallest larger integer. I plan to write the algorithm in short future.

My practice 

It took me over 60 minutes to write the code. I submitted a few times before the code can pass online judge.

Here is the C# code.


There are a few issues to slow me down in the coding process. I will look into later.

1. Content is wrong. Try to call .ToString() method from a char array, and then output is not char array content. I fixed the issue on line 56, using string constructor instead.
2. Confuse myself on line 76, current variable name is confusing. It is better called digit, which should be declared as int, int digit = s[i] - '0'
3. ...

Actionable Item

I do not know how to come out the idea by myself next time, I read the hint and analysis from geeksforgeeks.com "Find next greater number with the same set of digits" this time. The article link is here.

I have to push myself hard and figure out the idea by myself next time. The analysis is so well written in the article. Here is the analysis:

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

Following are few observations about the next greater number.
1) If all digits sorted in descending order, then output is always “Not Possible”. For example, 4321.
2) If all digits are sorted in ascending order, then we need to swap last two digits. For example, 1234.
3) For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)

Following is the algorithm for finding the next greater number.
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.