O(log n) space Java


  • 2

    Based on my Python solution. Here I use a helper class giving me the Kolakoski sequence (that's its name) one element at a time with its next method. It has the first three elements hard-coded, and after that, it uses another instance of the sequence to iterate further. That other instance does the same, so it might eventually use yet another instance. And so on, O(log n) nested Kolakoski objects iterating in parallel at different speeds as needed. Takes O(log n) space and O(n) time.

    public class Solution {
    
        public int magicalString(int n) {
            Kolakoski kolakoski = new Kolakoski();
            int ones = 0;
            while (n-- > 0)
                if (kolakoski.next() == 1)
                    ones++;
            return ones;
        }
    
        private class Kolakoski {
            private int[] queue = {1, 2, 2};
            private int first = 0, last = 2;
            private Kolakoski source;
            int next() {
                if (first > last) {
                    if (source == null) {
                        source = new Kolakoski();
                        source.next();
                        source.next();
                    }
                    int output = queue[last % 3] ^ 3;
                    for (int k = source.next(); k > 0; k--)
                        queue[++last % 3] = output;
                }
                return queue[first++ % 3];
            }
        }
    }
    

  • 0

    I have one question, why is it slower though? Mine is 11ms,12ms, this solution is 30-39ms. Almost 20ms slower. Is it because the expensive allocation of a new instance?


  • 0

    @zhugejunwei No, the number of instances is small, that's not it. But I'm doing more work for each sequence element.


  • 0

    @zhugejunwei Here's a version that got accepted in 16ms, 16ms and 17ms in three attempts. It does less work per element:

    public class Solution {
    
        public int magicalString(int n) {
            if (n == 0) return 0;
            int ones = 1;
            n -= 2;
            Lakoski lakoski = new Lakoski();
            while (n-- > 0)
                if (lakoski.next() == 1)
                    ones++;
            return ones;
        }
    
        private class Lakoski {
            private int number = 2;
            private boolean again = false;
            private Lakoski source;
            int next() {
                if (again)
                    again = false;
                else if (source == null)
                    source = new Lakoski();
                else {
                    number ^= 3;
                    again = source.next() == 2;
                }
                return number;
            }
        }
    }
    

    I strip off the first two elements of the sequence and call it Lakoski sequence. Then I only hardcode the starting 2 and don't have to ignore the first two elements of the underlying sequence instances. Mix of my own observation of that being annoying and this article which I found in the meantime.


Log in to reply
 

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