It "LOOKS LIKE" your DFS only visited each email account once, by using a "visited" list. But you didn't remove the visited "neighbor" from the emails_accounts_map, so the block of code:
class Solution(object): def maximumSwap(self, num): num = str(num) n = len(num) index_of_max_from_right =  * n swapped_digits = list(num) # scan from right to left, find the index of the biggest digit to num[i]'s right (including num[i]) for i in xrange(n - 1, -1, -1): # second condition is ">=" because you want to swap the smaller digit with the right most bigger digit if i < n - 1 and num[index_of_max_from_right[i + 1]] >= num[i]: index_of_max_from_right[i] = index_of_max_from_right[i + 1] else: index_of_max_from_right[i] = i the_index_to_swap = None j = 0 while j < n: if num[index_of_max_from_right[j]] > num[j]: the_index_to_swap = index_of_max_from_right[j] break j += 1 if the_index_to_swap != None: swapped_digits[the_index_to_swap] = num[j] swapped_digits[j] = num[the_index_to_swap] return int(''.join(swapped_digits))
I guess a more clear explanation for "* (n + 1)" is each chunk has at lease n + 1 chars when the frame is formed at first, not necessarily "for the for loop" as you said.
Assume the most frequent letter(s) is with count k, then there are two cases:
When the whole frame is "loose" -- when there is still unused idle time in each chunk, result = (c - 1) * (n + 1) + 25 - i where "25 - i" simply counts how many letters are with count k and n + 1 is the length of each chunk. Since we have k (in this case k == c) chunks, the total length of the first k - 1 chunks == (k - 1) * (n + 1). For the last chunk, we don't need the "whole chunk" (i.e., if the chunk is "ABXXX", we only will need the "AB". Because there are no more "less frequent letters" left so we can remove the last three spaces)
When the frame is "dense" (fully filled), the length of each chunk > n + 1. In this case it could be: a) initially the number of letters with count k is > n + 1 so the frame is already "fully filled without space left", or 2) the length of each chunk is > n + 1 after insertion. We still calculate the total length by adding up all the chunks, and it will == the length of the task at last.
Here is my Python version:
def leastInterval(self, tasks, n): c =  * 26 for task in tasks: c[ord(task) - ord('A')] += 1 c.sort() i = 25 while i >= 0 and c[i] == c: i -= 1 return max(len(tasks), (c - 1) * (n + 1) + 25 - i)
Sorry I didn't make it clear...
Everybody knows how to calculate n/2 + n/4 + n/8 + ... + 4 + 2 + 1 since it is a simple geometric sequence. I was saying it has O(logN) items whereas the number of items decides the number of loops (in your linked-list case, the concatenation of nodes).
However, if you can prove that each number needs exactly three extra chars, then we can ignore, jump out of the above discussion because what matters then will be the total number of operations, which is the sum of (n/2 + n/4 + n/8 + ... + 4 + 2 + 1).
@lixx2100 correct me if I am wrong
At first, n/2 + n/4 + ... + 4 + 2 + 1 is O(logN) time, not O(N).
Second, I don't know how you jump to the conclusion that one number only needs one "(", one ")" and one ",". If you could give logical deduction I would really appreciate.
Third, the string concatenation surely takes O(N) because we need to recreate a new string. In terms of using doubly-linked list, you need to justify the above point ("3 extra" nodes for each number), otherwise you cannot guarantee how many "(" or ")" you need to put on each side of the number.
So far I've only seen lots of O(nlogn) solutions...
I think in terms of O(n), you need to figure out how many parentheses you need to add on the left/right of each number.
Using backtracking will always need O(logn) times of looping through the whole list.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.