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

• 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):
"""
:type n: int
:rtype: int
"""
c = collections.defaultdict(int)
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
``````

• Shortened it a bit...

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

And a bit more:

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

• Shortened it a bit...

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

And a bit more:

``````def leastInterval(self, tasks, n):
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

• @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):
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
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.

• @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.

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