6 lines O(N) solutions w/ C++ & Python


  • 0
    Z

    a bit slow but really short
    c++ solution

    class Solution {
    public:
        int leastInterval(vector<char>& tasks, int n) {
            vector<int> counter(256);
            for ( char t : tasks )
                ++counter[t];
            int m = *max_element(counter.begin(), counter.end());
            int l = count(counter.begin(), counter.end(), m);
            return max(int(tasks.size()), (m - 1) * (n + 1) + l);
        }
    };
    
    // 64 / 64 test cases passed.
    // Status: Accepted
    // Runtime: 63 ms
    

    python solution

    class Solution(object):
        def leastInterval(self, tasks, n):
            """
            :type tasks: List[str]
            :type n: int
            :rtype: int
            """
            c = collections.defaultdict(int)
            for t in tasks:
                c[t] += 1
            m = max(c.itervalues())
            l = len([k for k in c if c[k] == m])
            return max(len(tasks), (m - 1) * (n + 1) + l)
    
    # 64 / 64 test cases passed.
    # Status: Accepted
    # Runtime: 682 ms
    

  • 1

    Shortened it a bit...

    def leastInterval(self, tasks, n):
        c = collections.Counter(tasks).values()
        return max(sum(c), (max(c) - 1) * (n + 1) + c.count(max(c)))
    

    And a bit more:

    def leastInterval(self, tasks, n):
        c = map(tasks.count, set(tasks))
        return max(sum(c), (max(c) - 1) * (n + 1) + c.count(max(c)))

  • 0
    Z

    @StefanPochmann said in 6 lines O(N) solutions w/ C++ & Python:

    Shortened it a bit...

    def leastInterval(self, tasks, n):
        c = collections.Counter(tasks).values()
        return max(sum(c), (max(c) - 1) * (n + 1) + c.count(max(c)))
    

    And a bit more:

    def leastInterval(self, tasks, n):
        c = map(tasks.count, set(tasks))
        return max(sum(c), (max(c) - 1) * (n + 1) + c.count(max(c)))
    

    although your solution is quite elegant, but

    the first one is a bit slow which might fail to TLE if the constraint is a bit stronger

    64 / 64 test cases passed.
    Status: Accepted
    Runtime: 1038 ms
    

    the second one fail to pass because

    64 / 64 test cases passed.
    Status: Memory Limit Exceeded
    

    previously, I noticed that collections.Counter will cause MLE if we don't do n == 0 check


  • 1

    @zqfan I'm pretty sure the MLE is because something's wrong with the judge. All of our solutions use very little memory. Also, when I first submitted your solution, it also got MLE.

    How often did you submit each solution? How stable were the times? How large was the judge overhead? I don't see much data from you. Looks like you submitted each solution only once. Is that true?


    I just submitted the following, which does the work ten times:

    def leastInterval(self, tasks, n):
        for _ in range(10):
            c = collections.Counter(tasks).values()
            result = max(sum(c), (max(c) - 1) * (n + 1) + c.count(max(c)))
        return result
    

    I submitted it five times, the results were 1675 ms, 1826 ms, 1902 ms, 1882 ms and TLE. So looks like average about 1870. Thus even doing ten times the work barely creates the TLE danger you're worried about.

    Using range(1) instead, five submissions resulted in 905 ms, 942 ms, 806 ms, 936 ms and 852 ms. Average 888.

    So to me, it looks pretty clear that the long time is also mostly the judge's fault and that the solution only takes about (1870 - 888) / 9 = 109 ms (and the judge overhead is about 888 - 109 = 779 ms).


    Even the following super fast cheat solution got MLE in my first submission and then 816 ms, 875 ms, 812 ms and 842 ms in my next four submissions:

    class Solution(object):
        results = [8, 6, 104, 10, 16, 4, 2, 4, 5, 3, 4, 5, 6, 1, 1, 2, 5, 4256, 1000, 9793, 6841, 9594, 1000,
                   1000, 10000, 29821, 66177, 17987, 66341, 84161, 76286, 62761, 36051, 52651, 10000, 29821,
                   66177, 17987, 66341, 84161, 76286, 62761, 36051, 52651, 10000, 29821, 66177, 17987, 66341,
                   84161, 76286, 62761, 36051, 52651, 100, 1345, 404, 1153, 523, 911, 1401, 936, 1140, 404]
        i = -1
        def leastInterval(self, tasks, n):
            Solution.i += 1
            return Solution.results[Solution.i]
    

    Again, clearly the judge is taking most of the time (and probably most of the memory). In this test it even looked like over 800 ms.


  • 0
    Z

    @StefanPochmann

    Thanks for your detailed and convincing investigation, I run your solution just one time, because it is a contest problem, it needs to be very safe to get AC due to the time penalty. I do agree it is the judge's fault, clearly it is a bit same as last contest, I think they didn't test python solution very well.


Log in to reply
 

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