Java 18 ms true O(1) space / cheated O(n) time using binary search


  • 11

    I spent a lot of time looking for an in-place linear algorithm for finding the median. Thanks to @StefanPochmann for posting a link to Stack Overflow, I found this one. It's really esoteric, and what's worse, it's not really a complete algorithm because at some point it just says

    then, using any other linear-time in-place selection algorithm, search
    the sample for two elements x,y, of ranks...

    So in the end, it's not exactly an algorithm for linear in-place selection, but rather an algorithm for finding the best sample for other algorithms to optimize the total number of operations involved. The paper provides references to other algorithms, but I've been unable to find any of them in the open. But surely, one could buy some books or access to some scientific site, and in the end it is possible to solve this in linear time and constant space. The code would be a real mess, though, and I'm not even sure if it will fit within the code length limit.

    But there is a better way. Once I saw that I was amazed how absurdly simple it is. Made me feel like Dr. Watson after another explanation by Holmes.

    Indeed, why bother with all those algorithms if we know that possible values of the median lie between INT_MIN and INT_MAX. We can use binary search on the entire range! And since checking whether some number is the median or not takes O(n), then the whole thing is just O(n log 2^32). But log 2^32 is a constant, so it's technically still O(n).

    public void wiggleSort(int[] nums) {
        if (nums.length <= 1) {
            return;
        }
        int p = bsSelect(nums, (nums.length - 1) / 2 + 1);
        // Reverse Dutch National Flag with Wiggle Indexing (StefanPochmann's Virtual Indexing).
        // Thanks to apolloydy for reversing this thing.
        final int n = nums.length;
        int m = 0, r = nums.length - 1;
        int lw = 1, mw = 1, rw = (1 + 2 * (nums.length - 1)) % (n | 1);
        while (m <= r) {
            if (nums[mw] > p) {
                int tmp = nums[mw];
                nums[mw] = nums[lw];
                nums[lw] = tmp;
                mw = (mw + 2) % (n | 1);
                ++m;
                lw = (lw + 2) % (n | 1);
            } else if (nums[mw] < p) {
                int tmp = nums[mw];
                nums[mw] = nums[rw];
                nums[rw] = tmp;
                rw = (rw - 2 + (n | 1)) % (n | 1);
                --r;
            } else {
                mw = (mw + 2) % (n | 1);
                ++m;
            }
        }
    }
    
    private int bsSelect(int[] nums, int k) {
        if (k < 1 || k > nums.length) {
            throw new IllegalArgumentException("length=" + nums.length + " k=" + k);
        }
        int left = Integer.MIN_VALUE, right = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = (left < 0 && right > 0) ? (left + right) / 2 : left + (right - left) / 2;
            int cl = 0, cg = 0, d = 0;
            for (int n : nums) {
                if (n < mid) {
                    if (++cl > k - 1) {
                        d = +1; // mid larger than kth
                        break;
                    }
                } else if (n > mid) {
                    if (++cg > (nums.length - k)) {
                        d = -1; // mid smaller than kth
                        break;
                    }
                }
            }
            if (d == 0) {
                return mid;
            } else if (d < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        throw new AssertionError();
    }
    

    It almost feels like cheating. But according to that post on Quora, that's exactly what the interviewers expect. Thinking out of the box and such.

    This thing runs on my PC for 500 million elements in 31 seconds if the array is sorted and in 38 seconds if it's wiggle-sorted to begin with. This is slower than the median of medians solution (22 and 12 seconds), but this time it's true O(1) space.

    Note that I moved the argument check to the beginning because the old variant was really bugged. And I fixed the binary search because I forgot to do the mid + 1 / mid - 1 part. That turned 15 ms into 18 ms for some reason, and if I put while (true) there then it raises the runtime to 20 ms. Figures. But at least it's not bugged now (I hope). Note that integer overflows aren't possible because if mid is either INT_MIN or INT_MAX then the respective condition for decreasing/increasing it would be false.

    As noted in the comment below, mid = (left + right) / 2 may overflow, so it was replaced by that ugly, but overflow-aware line.


  • 2

    Well... just like you can "sort in O(n)" with radix sort. That is, if you ignore the word size as a constant. But if you do that, then you can also consider any problem where the input is a single int to be solvable in O(1) time, because then there's only a finite number of possible inputs and you just take a worst input and have your constant that bounds all inputs. I can never really decide whether I like it.

    Really truly in general it's O(wn), just like radix sort (see the box on the top-right). But I'll upvote it anyway, as it's a good and interesting solution and the "O(n)" is somewhat justified.

    There's also at least one other LeetCode problem with a neat "O(n)" solution that's really "O(wn)". Do you want to know which problem I mean? I can tell, but you'd then have a spoiler for it already...

    I btw also came across that quora answer a few days ago :-). It's good, especially the second half. But note that he clearly doesn't call it "true O(n)" but says "extra naughty assumption".


  • 0

    Indeed, that's why I called it cheating. I thought about radix sort too, but then it wouldn't be O(1) space complexity now, would it?


  • 0

    Hmm... Wikipedia talks about in-place implementations and does say "O(w + N)" space, where I suspect the w is meant in bits, so O(1) words. But I'm not sure.


  • 0

    I see you changed the title to say "cheated"... not sure that's best, might just unnecessarily scare people off. I would've just removed the word "true", as I found that a bit misleading. Your call, of course :-)

    I don't think there's much complaining about those "O(n)" solutions to that other problem that I mentioned, instead they easily get upvoted...


  • 0

    On the other hand, I only thought about radix sort briefly without refreshing my memory on it. Looking at it now, the only thing that it needs is a stable O(1) space linear sort for each digit, but I can't think of one off the top of my head. Usually counting sort is used for that sort of thing, no pun intended, but it's not O(1)...


  • 0

    I left the word "true" there as well because it's true O(1) space complexity, no doubt about that. And that's what I wanted to highlight in the first place, but it kind of got mixed up with that "O(n)" thing which I only meant as secondary.


  • 0

    Here's a Ruby version. Finding the median is really nice, just one line, but I wasn't able to do the rest anywhere near as nicely.

    def wiggle_sort(nums)
      n = nums.size
      mid = (nums.min..nums.max).bsearch { |m| nums.count { |x| m >= x } > n / 2 }
      mod = n | 1
      i, j, k = 1 % mod, 1 % mod, (2*n-1) % mod
      n.times do
        if nums[j] > mid
          nums[i], nums[j] = nums[j], nums[i]
          i = (i + 2) % mod
          j = (j + 2) % mod
        elsif nums[j] < mid
          nums[j], nums[k] = nums[k], nums[j]
          k = (k - 2) % mod
        else
          j = (j + 2) % mod
        end
      end
      nil
    end
    

    I used your nice idea to work with "real but wiggled" indexes, if I may call them that :-)

    Two noteworthy differences to yours:

    • I used the actual range of the given numbers, i.e., nums.min..nums.max. Finding min and max takes two extra scans, but they're fast and they can reduce the number of count-scans, and those are probably slower. This solution gets accepted in ~220 ms. With range -2**31...2**31 it gets accepted in ~350 ms.

    • For partitioning, I simply did the loop n times (and I remain in love with how Ruby lets me write that :-).


  • 0

    Hey, wasn't wiggle indexing your idea?


  • 0

    Yes, but I didn't think of doing it your way :-)

    In C++ I can use that nice macro to just write A(i), both for reading and writing. But in the other languages, I only thought of using nums[real(i)] everywhere or having a swap helper, both of which didn't seem nice to me. I just tried it, though, and now I actually like it as well, as it does make the actual algorithm cleaner:

    def wiggle_sort(nums)
      n = nums.size
      mid = (nums.min..nums.max).bsearch { |m| nums.count { |x| m >= x } > n / 2 }
      
      real = -> virtual { (1 + 2*virtual) % (n | 1) }
      swap = -> v, w {
        v, w = real[v], real[w]
        nums[v], nums[w] = nums[w], nums[v]
      }
      
      i, j, k = 0, 0, n-1
      n.times do
        num = nums[real[j]]
        if num > mid
          swap[i, j]
          i += 1
          j += 1
        elsif num < mid
          swap[j, k]
          k -= 1
        else
          j += 1
        end
      end
      nil
    end

  • 0

    More compact version:

    def wiggle_sort(nums)
      n = nums.size
      mid = (nums.min..nums.max).bsearch { |m| nums.count { |x| m >= x } > n / 2 }
    
      real = -> virtual { (1 + 2*virtual) % (n | 1) }
      swap = -> v, w {
        v, w = real[v], real[w]
        nums[v], nums[w] = nums[w], nums[v]
      }
    
      i, j, k = 0, 0, n-1
      n.times do
        case nums[real[j]] <=> mid
        when 0 then j += 1
        when 1 then swap[i, j]; i += 1; j += 1
        else        swap[j, k]; k -= 1
        end
      end
      
      nil
    end

  • 0

    I like it better in fact. First I implemented it like this too, but I had a function instead of an array, and Java wasn't very good at optimizing those numerous calls and the whole thing was twice as slower than my final version. I tried arrays now, it's much faster, but still a bit slower than the arithmetic version.


  • 0

    "I had a function instead of an array"

    What do you mean with array there?


  • 0

    Oh, sorry. I'm not very familiar with Ruby. I meant that I've created an array int[] index and filled it with indexes before proceeding, and then the code was much like yours. Works really faster in Java then a wiggle-indexing function.


  • 0

    Ah, ok. I thought maybe you meant my real[...] because of the [].

    Yeah, I can imagine pre-computing an index table being faster... just too bad that its linear space defeats the whole point :-)


  • 0

    Yes, that's exactly what I thought at first because of the []. Now that you mention the linear space, I understand why I didn't think of that. And anyway, the arithmetic solution is the fastest in Java.


  • 0
    K

    Your bsSelect() implementation is broken.

    int x = bsSelect(new int[] { 0, 1, 20, 500, Integer.MAX_VALUE }, 5);
    

    That line runs forever ^

    The problem is in your calculation of mid:

    int mid = (left + right) / 2;
    

    This can overflow depending on what left and right are.

    You should use this instead:

    int mid = (left < 0 && right > 0) ? (left + right) / 2 : left + (right - left) / 2;

  • 0

    Good catch! I was so worried about the possibility that mid + 1 or mid - 1 may overflow that I failed to notice the elephant, so to speak.


  • 0
    This post is deleted!

  • 0

    Actually, since lw and rw are the borders of less-than and larger-than median, they never need to wrap around. You can just += 2 and -= 2 them, and initialize rw as the largest even index, (nums.length - 1) & ~1.

    (In my virtual indexing I treat all three indexes with the same logic because that's the point and beauty of it, that the actual algorithm doesn't even know that it's happening. So I won't change it there.)


Log in to reply
 

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