LeetCode 30-Day Challenge: Is This Cheating?

C++: Practice

Today's problem, problem #4, for the the LeetCode 30-day programming challenge was the complete opposite of yesterday. They present the partitipant with:

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.


Input: [0,1,0,3,12]
Output: [1,3,12,0,0]


  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

Um... that's just std::stable_partition.

At first I hesitated for fear of being cheeky and not trying hard enough, but then I thought to myself, "Wouldn't you rather see std::stable_partition in production code rather than a roll-your-own implementation by some whiz kid?" So I submitted it, and it was accepted, and it was fast. (The STL can be fast, who knew?)

I am, however, looking for an example, or preferably a document, explaining how it's implemeneted in the STL so that I can understand what's going on under the hood. Google isn't turning up anything helpful. I tried looking through the GCC and Clang source code but their stable_partition functions look tightly coupled with other functions and there are some confusing looking optimization tricks going on in there.