0
$\begingroup$

The programming language is C++, and the elements of the input vector are of type int and able to take all valid int values. So it’s not possible to store extra information in the input vector. Now, is it possible to sort the vector in linear time and constant extra space? Simple solutions are preferred.

And to avoid ridiculous constant factors, the constant factor in linear time is at most 100.

$\endgroup$
2
  • $\begingroup$ I’m voting to close this question because it is a programming competition question, so the questioner is just trying to cheat. $\endgroup$
    – gnasher729
    Feb 16 at 20:17
  • 1
    $\begingroup$ When you ask a question based on a resource you have seen elsewhere, please link to the original resource and include the title or other citation for it. You mentioned that this is based on leetcode.com/problems/single-number-iii/description -- please include that motivation in the question. This avoids wasting answerers' time and helps others in the future who might have a similar question about the same exercise. $\endgroup$
    – D.W.
    Feb 16 at 22:45

2 Answers 2

2
$\begingroup$

If you require a comparison-based sorting algorithm akin to quicksort and merge sort, the answer is "No." Simply put, it can be proven that sorting an array of $n$ elements using a comparison-based method in that respect would require, at least, a complexity of $O(n\times log(n))$. Alternatively, Kelly Bundy's solution works fine and does run in linear time, as requested. However, I would not wager too much in terms of efficiency.

$\endgroup$
1
  • $\begingroup$ Of course it’s not comparison-based. $\endgroup$
    – Zirui Wang
    Feb 16 at 15:15
0
$\begingroup$

(Note: This was posted before their edit.)

Yes. Move all elements with value $-2^{31}$ to the front, order of the remaining elements doesn't matter. Easy in linear time. Then move all remaining elements with value $-2^{31}+1$ to the front (but after the $-2^{31}$ elements). Then do the same with $-2^{31}+2$, ..., $2^{31}-1$. Total time for $n$ elements is $O(2^{32}n) = O(n)$.

$\endgroup$
13
  • 1
    $\begingroup$ @ZiruiWang It's both. $\endgroup$ Feb 16 at 15:10
  • 2
    $\begingroup$ @ZiruiWang I saw. Not friendly trying to invalidate someone's work. (Not that you succeed in that, as I can simply count the billions of steps, so my conclusion becomes like O(4n)=O(n), i.e., my constant factor is only 4 then, which is less than 100.) $\endgroup$ Feb 16 at 15:17
  • 1
    $\begingroup$ @ZiruiWang "this is a LeetCode programming question (260 Single Number III: leetcode.com/problems/single-number-iii)" - Not really. That LeetCode question is far simpler, sorting is wasteful for that. $\endgroup$ Feb 16 at 16:19
  • 1
    $\begingroup$ I just voted to close. Rudeness is not a reason to close, but cheating on leetcode questions is. $\endgroup$
    – gnasher729
    Feb 16 at 20:18
  • 2
    $\begingroup$ @KennethKho Yes, you missed the requirement "uses only constant extra space". No, I wouldn't call it trivial. $\endgroup$ Feb 17 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.