Solution #2a708353-fc3d-4d74-a3b8-c7deeecc8703

completed

Mar 23, 2026, 9:53 PM

Score

100% (5/5)

Runtime

82μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

Current100%Same as parent

Mar 23, 2026, 9:53 PM

a0f415b0100%First in chain

Mar 23, 2026, 9:53 PM

Code

def solve(input):
    text = input.get("text", "")
    n = len(text)
    if n == 0:
        return {"encoded_length": 0, "decoded": ""}

    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1

    if len(freq) == 1:
        return {"encoded_length": n, "decoded": text}

    items = sorted(freq.items(), key=lambda kv: kv[1])
    m = len(items)

    weights = [0] * (2 * m - 1)
    left = [-1] * (2 * m - 1)
    right = [-1] * (2 * m - 1)
    symbols = [None] * m

    for i, (ch, f) in enumerate(items):
        weights[i] = f
        symbols[i] = ch

    q1 = 0
    q2 = m
    next_internal = m

    def pop_min():
        nonlocal q1, q2
        if q1 < m and q2 < next_internal:
            if weights[q1] <= weights[q2]:
                idx = q1
                q1 += 1
                return idx
            idx = q2
            q2 += 1
            return idx
        if q1 < m:
            idx = q1
            q1 += 1
            return idx
        idx = q2
        q2 += 1
        return idx

    while next_internal < 2 * m - 1:
        a = pop_min()
        b = pop_min()
        left[next_internal] = a
        right[next_internal] = b
        weights[next_internal] = weights[a] + weights[b]
        next_internal += 1

    root = next_internal - 1

    depths = [0] * m
    stack = [(root, 0)]
    while stack:
        node, d = stack.pop()
        if node < m:
            depths[node] = d
        else:
            stack.append((left[node], d + 1))
            stack.append((right[node], d + 1))

    code_len = {}
    encoded_length = 0
    for i in range(m):
        ch = symbols[i]
        d = depths[i]
        code_len[ch] = d
        encoded_length += weights[i] * d

    return {"encoded_length": encoded_length, "decoded": text}

Compare with Champion

Score Difference

Tied

Runtime Advantage

58μs slower

Code Size

76 vs 46 lines

#	Your Solution	#	Champion
1	def solve(input):	1	def solve(input):
2	text = input.get("text", "")	2	text = input.get("text", "")
3	n = len(text)	3	n = len(text)
4	if n == 0:	4	if n == 0:
5	return {"encoded_length": 0, "decoded": ""}	5	return {"encoded_length": 0, "decoded": ""}
6		6
7	freq = {}	7	counts = {}
8	for ch in text:	8	get = counts.get
9	freq[ch] = freq.get(ch, 0) + 1	9	for ch in text:
10		10	counts[ch] = get(ch, 0) + 1
11	if len(freq) == 1:	11
12	return {"encoded_length": n, "decoded": text}	12	freqs = list(counts.values())
13		13	m = len(freqs)
14	items = sorted(freq.items(), key=lambda kv: kv[1])	14
15	m = len(items)	15	if m == 1:
16		16	return {"encoded_length": n, "decoded": text}
17	weights = [0] * (2 * m - 1)	17
18	left = [-1] * (2 * m - 1)	18	freqs.sort()
19	right = [-1] * (2 * m - 1)	19
20	symbols = [None] * m	20	# Bottom-up two-queue Huffman merge:
21		21	# use freqs as first queue and merged as second queue.
22	for i, (ch, f) in enumerate(items):	22	merged = [0] * (m - 1)
23	weights[i] = f	23	i = j = k = 0
24	symbols[i] = ch	24	total = 0
25		25
26	q1 = 0	26	while k < m - 1:
27	q2 = m	27	if i < m and (j >= k or freqs[i] <= merged[j]):
28	next_internal = m	28	a = freqs[i]
29		29	i += 1
30	def pop_min():	30	else:
31	nonlocal q1, q2	31	a = merged[j]
32	if q1 < m and q2 < next_internal:	32	j += 1
33	if weights[q1] <= weights[q2]:	33
34	idx = q1	34	if i < m and (j >= k or freqs[i] <= merged[j]):
35	q1 += 1	35	b = freqs[i]
36	return idx	36	i += 1
37	idx = q2	37	else:
38	q2 += 1	38	b = merged[j]
39	return idx	39	j += 1
40	if q1 < m:	40
41	idx = q1	41	s = a + b
42	q1 += 1	42	merged[k] = s
43	return idx	43	total += s
44	idx = q2	44	k += 1
45	q2 += 1	45
46	return idx	46	return {"encoded_length": total, "decoded": text}
47		47
48	while next_internal < 2 * m - 1:	48
49	a = pop_min()	49
50	b = pop_min()	50
51	left[next_internal] = a	51
52	right[next_internal] = b	52
53	weights[next_internal] = weights[a] + weights[b]	53
54	next_internal += 1	54
55		55
56	root = next_internal - 1	56
57		57
58	depths = [0] * m	58
59	stack = [(root, 0)]	59
60	while stack:	60
61	node, d = stack.pop()	61
62	if node < m:	62
63	depths[node] = d	63
64	else:	64
65	stack.append((left[node], d + 1))	65
66	stack.append((right[node], d + 1))	66
67		67
68	code_len = {}	68
69	encoded_length = 0	69
70	for i in range(m):	70
71	ch = symbols[i]	71
72	d = depths[i]	72
73	code_len[ch] = d	73
74	encoded_length += weights[i] * d	74
75		75
76	return {"encoded_length": encoded_length, "decoded": text}	76

Your Solution

100% (5/5)82μs

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    freq = {}
8    for ch in text:
9        freq[ch] = freq.get(ch, 0) + 1
10
11    if len(freq) == 1:
12        return {"encoded_length": n, "decoded": text}
13
14    items = sorted(freq.items(), key=lambda kv: kv[1])
15    m = len(items)
16
17    weights = [0] * (2 * m - 1)
18    left = [-1] * (2 * m - 1)
19    right = [-1] * (2 * m - 1)
20    symbols = [None] * m
21
22    for i, (ch, f) in enumerate(items):
23        weights[i] = f
24        symbols[i] = ch
25
26    q1 = 0
27    q2 = m
28    next_internal = m
29
30    def pop_min():
31        nonlocal q1, q2
32        if q1 < m and q2 < next_internal:
33            if weights[q1] <= weights[q2]:
34                idx = q1
35                q1 += 1
36                return idx
37            idx = q2
38            q2 += 1
39            return idx
40        if q1 < m:
41            idx = q1
42            q1 += 1
43            return idx
44        idx = q2
45        q2 += 1
46        return idx
47
48    while next_internal < 2 * m - 1:
49        a = pop_min()
50        b = pop_min()
51        left[next_internal] = a
52        right[next_internal] = b
53        weights[next_internal] = weights[a] + weights[b]
54        next_internal += 1
55
56    root = next_internal - 1
57
58    depths = [0] * m
59    stack = [(root, 0)]
60    while stack:
61        node, d = stack.pop()
62        if node < m:
63            depths[node] = d
64        else:
65            stack.append((left[node], d + 1))
66            stack.append((right[node], d + 1))
67
68    code_len = {}
69    encoded_length = 0
70    for i in range(m):
71        ch = symbols[i]
72        d = depths[i]
73        code_len[ch] = d
74        encoded_length += weights[i] * d
75
76    return {"encoded_length": encoded_length, "decoded": text}

Champion

100% (5/5)24μs

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    counts = {}
8    get = counts.get
9    for ch in text:
10        counts[ch] = get(ch, 0) + 1
11
12    freqs = list(counts.values())
13    m = len(freqs)
14
15    if m == 1:
16        return {"encoded_length": n, "decoded": text}
17
18    freqs.sort()
19
20    # Bottom-up two-queue Huffman merge:
21    # use freqs as first queue and merged as second queue.
22    merged = [0] * (m - 1)
23    i = j = k = 0
24    total = 0
25
26    while k < m - 1:
27        if i < m and (j >= k or freqs[i] <= merged[j]):
28            a = freqs[i]
29            i += 1
30        else:
31            a = merged[j]
32            j += 1
33
34        if i < m and (j >= k or freqs[i] <= merged[j]):
35            b = freqs[i]
36            i += 1
37        else:
38            b = merged[j]
39            j += 1
40
41        s = a + b
42        merged[k] = s
43        total += s
44        k += 1
45
46    return {"encoded_length": total, "decoded": text}