To find j, we can use a binary search between i and end.
However this may not make it faster in real world, because for a random permutation, i won't be far away from end.
If we know the array is almost sorted, then binary search will be better.

In the brute force approach shouldn't the space be O(n!) and not O(n)?
Given n elements produce n! permutations and we need space to store n! permutations.

For
while (j >= 0 && nums[j] <= nums[i]), there is no need to test j >= 0, as there must be a number is bigger than nums[i].
while (nums[j] <= nums[i]) is enough.

Isn't the time complexity O(n! * n) for the brute force case? We have to compare all of the permutations to the original one/current closest (each comparision requres O(n) time)

Isn't this incorrect? Should be nums[j] >= nums[i] since we are looking for a number that's greater than nums[i] where we found a break in the descending from left to right pattern. Can someone else double check this?

while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
after this line ,before swap, i think an extra check for j>=0 is required. For Input [1,1] , j may become -1 according to this logic. So only swap when j >= 0 .