StringProblem 15 of 43Important

Find next greater number with same set of digits [Very Very IMP]

Brute Force
Time: O(n! × n)
Space: O(n)
Optimal
Time: O(n)
Space: O(1)

Problem Statement

Given a number, find the next greater number that can be formed using the same set of digits. If no such number exists (the number is the largest possible), return -1.

Example:

  • Input: 1234

  • Output: 1243

  • Input: 4321

  • Output: -1 (already the largest)

  • Input: 534976

  • Output: 536479

  • Input: 218765

  • Output: 251678

Approach 1: Brute Force (Generate All Permutations)

Intuition

Generate all permutations of the digits, sort them, find the current number, and return the next one.

Algorithm

  1. Convert number to string and generate all permutations
  2. Sort the permutations
  3. Find the current number and return the next one
java
import java.util.*;

public class Solution {
    public String nextGreaterNumber(String num) {
        List<String> permutations = new ArrayList<>();
        char[] chars = num.toCharArray();
        Arrays.sort(chars);
        
        // Generate all permutations
        do {
            permutations.add(new String(chars));
        } while (nextPermutation(chars));
        
        Collections.sort(permutations);
        
        for (int i = 0; i < permutations.size() - 1; i++) {
            if (permutations.get(i).equals(num)) {
                return permutations.get(i + 1);
            }
        }
        
        return "-1";
    }
    
    private boolean nextPermutation(char[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i < 0) return false;
        
        int j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;
        
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }
    
    private void reverse(char[] arr, int start, int end) {
        while (start < end) {
            char temp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = temp;
        }
    }
}

Complexity Analysis

  • Time Complexity: O(n! × n) - Generating and sorting n! permutations
  • Space Complexity: O(n!) - Storing all permutations

Approach 2: Optimal (Next Permutation Algorithm)

Intuition

Find the next lexicographically greater permutation directly using the next permutation algorithm:

  1. Find the rightmost digit that is smaller than its next digit (pivot)
  2. Find the smallest digit to the right of pivot that is greater than pivot
  3. Swap them
  4. Reverse the suffix after the pivot position

Algorithm

  1. Traverse from right to find first digit smaller than its next digit (index i)
  2. If no such digit exists, return -1
  3. Find the smallest digit greater than digits[i] in the suffix
  4. Swap them
  5. Reverse the suffix to get the smallest arrangement
java
public class Solution {
    public int nextGreaterNumber(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        int len = digits.length;
        
        // Step 1: Find the pivot
        int i = len - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }
        
        // If no such digit found
        if (i < 0) {
            return -1;
        }
        
        // Step 2: Find smallest digit greater than digits[i]
        int j = len - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }
        
        // Step 3: Swap
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
        
        // Step 4: Reverse the suffix
        reverse(digits, i + 1, len - 1);
        
        // Convert back to number and check overflow
        try {
            long result = Long.parseLong(new String(digits));
            if (result > Integer.MAX_VALUE) {
                return -1;
            }
            return (int) result;
        } catch (NumberFormatException e) {
            return -1;
        }
    }
    
    private void reverse(char[] arr, int start, int end) {
        while (start < end) {
            char temp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = temp;
        }
    }
}

Complexity Analysis

  • Time Complexity: O(n) - At most two passes through the digits
  • Space Complexity: O(n) - For storing digits (O(1) if modifying in place)

Visual Example

For number 534976:

Step 1: Find pivot (rightmost digit smaller than next) 5 3 4 9 7 6 ^ i=2 (4 < 9) Step 2: Find smallest digit > 4 in suffix [9,7,6] 5 3 4 9 7 6 ^ j=5 (6 > 4) Step 3: Swap digits[2] and digits[5] 5 3 6 9 7 4 Step 4: Reverse suffix after index 2 5 3 6 4 7 9 Result: 536479

Edge Cases

Alternative: Finding Previous Smaller Number

Key Takeaways

  1. Next Permutation is the core algorithm - essential to know
  2. The key insight is finding the rightmost ascent (pivot point)
  3. After swapping, the suffix must be reversed (not sorted)
  4. Time complexity is O(n) - much better than generating all permutations
  5. Handle integer overflow carefully for large numbers
  6. Handle edge cases: single digit, all same digits, descending order
  7. This problem is a classic interview question (LeetCode 31, 556)
  8. The same technique applies to finding the previous smaller number
Previous
EDIT Distance [Very Imp]
Next
Balanced Parenthesis problem [Imp]