Next Greater Element III - Practice Coding Problems

Next Greater Element III - Problem

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n.

If no such positive integer exists, return -1.

Note: The returned integer should fit in 32-bit integer. If there is a valid answer but it does not fit in 32-bit integer, return -1.

Input & Output

Example 1 — Basic Next Permutation

$ Input: n = 123

› Output: 132

💡 Note: The digits are [1,2,3]. The next greater permutation is [1,3,2], which forms 132.

Example 2 — No Greater Permutation

$ Input: n = 321

› Output: -1

💡 Note: The digits are [3,2,1] in descending order. No rearrangement can create a larger number.

Example 3 — Larger Number

$ Input: n = 12443322

› Output: 13222344

💡 Note: Find rightmost ascending pair (2<4), swap with next larger digit, then arrange remaining digits in ascending order.

Constraints

1 ≤ n ≤ 2³¹ - 1
n is a positive integer

Visualization

Tap to expand

Understanding the Visualization

Input

Given number n with specific digit arrangement

Process

Find next lexicographically greater permutation of digits

Output

Return the next greater number or -1 if impossible

Key Takeaway

🎯 Key Insight: Use next permutation algorithm to efficiently find the lexicographically next arrangement of digits

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to use the next permutation algorithm: find the rightmost digit that can be increased, swap it with the smallest larger digit to its right, then reverse the suffix to get the minimal arrangement. Best approach is Next Permutation Algorithm. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Permutations	O(n!)	O(n!)	Generate all possible permutations of digits and find the next larger number
Next Permutation Algorithm	O(n)	O(n)	Use the next permutation algorithm to directly find the next greater arrangement

Brute Force - Generate All Permutations — Algorithm Steps

Convert number to array of digits
Generate all permutations of digits
Convert permutations back to numbers
Find smallest number greater than original

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Digits

Convert 123 to [1,2,3]

Generate Permutations

Create all arrangements: 123, 132, 213, 231, 312, 321

Find Next Greater

Filter valid numbers > 123, return smallest: 132

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

void swap(char* a, char* b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

void generatePermutations(char* s, int start, int len, long long* minNext, int original) {
    if (start == len) {
        if (s[0] != '0') {
            long long num = atoll(s);
            if (num > original && num <= INT_MAX && num < *minNext) {
                *minNext = num;
            }
        }
        return;
    }
    
    for (int i = start; i < len; i++) {
        swap(&s[start], &s[i]);
        generatePermutations(s, start + 1, len, minNext, original);
        swap(&s[start], &s[i]);
    }
}

int solution(int n) {
    char s[20];
    sprintf(s, "%d", n);
    int len = strlen(s);
    
    long long minNext = LLONG_MAX;
    generatePermutations(s, 0, len, &minNext, n);
    
    return minNext == LLONG_MAX ? -1 : (int)minNext;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generates n! permutations where n is number of digits

⚠ Quadratic Growth

Space Complexity

O(n!)

Stores all n! permutations in memory

⚠ Quadratic Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler