Coding Interview Question: Find the greatest integer smaller than N with the same set of digits as N (C++ Solutions with O(n ^ 2) and O(n) time complexities)

Google, Meta, Amazon Interview Questions

Question

Given an integer N, find the greatest integer less than N and has the same digits. If there is no such integer, return -1.

For example:

Input = 630

Output = 603

Input = 603

Output = 360

Input = 360

Output = 306

Input = 306

Output = -1 (Be careful, 063 could not be an answer, leading zeros are weird, discuss with your interviewer)

C++ Solution – O(n ^ 2) [Quadratic Time Complexity]

int prev_greatest_v1(int num)
{
  string strnum = to_string(num);
  for(int i = strnum.size() - 1; i > 0; i--)
  {
    for(int j = i - 1; (strnum[i] == '0' && j >= 1) || (strnum[i] != '0' && j >= 0); j--)
    {
      if (strnum[j] > strnum[i])
      {
        swap(strnum[i], strnum[j]);
        sort(strnum.begin() + j + 1, strnum.end(), greater <> ());
        return stoi(strnum);
      }
    }
  }
  return -1;
}

C++ Solution – O(n) [Linear Time Complexity]

int prev_greatest_v2(int num)
{
  string strnum = to_string(num);

  vector < int > track(strnum.size(), -1);
  stack < int > s;
  for(unsigned i = 0; i < strnum.size(); i++)
  {
    while(!s.empty() && strnum[s.top()] <= strnum[i]) s.pop();
    if (!s.empty()) track[i] = s.top();
    s.push(i);
  }

  for(int i = track.size() - 1; i > 0; i--)
  {
    if (track[i] != -1 && (strnum[i] != '0' || track[i] != 0))
    {
      swap(strnum[i], strnum[track[i]]);
      sort(strnum.begin() + track[i] + 1, strnum.end(), greater <> ());
      return stoi(strnum);
    }
  }
  return -1;
}

Full Code

The code contains some extra blocks related to creating random numbers and checking the return values of two different solutions.

// https://serhatgiydiren.com
// Oct 20, 2022

#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

mt19937 rng(steady_clock::now().time_since_epoch().count());

// O(n^2) - quadratic time complexity
int prev_greatest_v1(int num)
{
  string strnum = to_string(num);
  for(int i = strnum.size() - 1; i > 0; i--)
  {
    for(int j = i - 1; (strnum[i] == '0' && j >= 1) || (strnum[i] != '0' && j >= 0); j--)
    {
      if (strnum[j] > strnum[i])
      {
        swap(strnum[i], strnum[j]);
        sort(strnum.begin() + j + 1, strnum.end(), greater <> ());
        return stoi(strnum);
      }
    }
  }
  return -1;
}

// O(n) - linear time complexity
int prev_greatest_v2(int num)
{
  string strnum = to_string(num);

  vector < int > track(strnum.size(), -1);
  stack < int > s;
  for(unsigned i = 0; i < strnum.size(); i++)
  {
    while(!s.empty() && strnum[s.top()] <= strnum[i]) s.pop();
    if (!s.empty()) track[i] = s.top();
    s.push(i);
  }

  for(int i = track.size() - 1; i > 0; i--)
  {
    if (track[i] != -1 && (strnum[i] != '0' || track[i] != 0))
    {
      swap(strnum[i], strnum[track[i]]);
      sort(strnum.begin() + track[i] + 1, strnum.end(), greater <> ());
      return stoi(strnum);
    }
  }
  return -1;
}

void process()
{
  int num = rng() % INT_MAX;
  while(num != -1)
  {
    int res_v1 = prev_greatest_v1(num);
    int res_v2 = prev_greatest_v2(num);
    assert(res_v1 == res_v2);
    cout << num << " -> " << res_v1 << endl;
    num = res_v1;
  }
}

void fast_io()
{
  ios::sync_with_stdio(false);
  srand(time(NULL));
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(2);
  cerr << fixed << setprecision(2);
}

int main()
{
  fast_io();
  process();
  return EXIT_SUCCESS;
}

The original post is here.