a 10-line C++ implementation of the classic algorithm

  • 0

    With upper_bound() within a for-loop, it's still O(n). Do you know why?

        void nextPermutation(vector<int>& nums) {
            for (auto i=nums.rbegin(); i!=nums.rend(); ++i) {
                auto j = upper_bound(nums.rbegin(), i, *i);
                if (j != i) {
                    swap(*i, *j);
                    reverse(nums.rbegin(), i);
            reverse(nums.rbegin(), nums.rend());

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.