Sort Characters By Frequency

▶

Steps

setup

Count Character Frequencies

Count the frequency of each character in the input string 'tree' using a hash map (Counter).

💡 Counting frequencies is the foundation for grouping characters by how often they appear.

Line:

freq = Counter(s)

💡 You now know how many times each character appears, which is essential for bucket placement.

setup

Find Maximum Frequency

Determine the maximum frequency among all characters to size the buckets array.

💡 Knowing the max frequency lets us create buckets indexed by frequency.

Line:

max_freq = max(freq.values(), default=0)

💡 Maximum frequency is 2, so buckets array will have indices 0 to 2.

setup

Initialize Buckets Array

Create an array of empty buckets, one for each frequency from 0 to max_freq.

💡 Buckets will hold characters grouped by their frequency count.

Line:

buckets = [[] for _ in range(max_freq + 1)]

💡 Buckets array is ready to receive characters grouped by frequency.

fill_row

Place 't' in Bucket 1

Place character 't' into the bucket corresponding to its frequency 1.

💡 Characters are grouped by frequency to enable easy retrieval later.

Line:

buckets[count].append(char)  # Place char in bucket of its frequency

💡 't' belongs in bucket index 1.

fill_row

Place 'r' in Bucket 1

Place character 'r' into the bucket corresponding to its frequency 1.

💡 Multiple characters can share the same frequency bucket.

Line:

buckets[count].append(char)  # Place char in bucket of its frequency

💡 'r' joins 't' in bucket 1.

fill_row

Place 'e' in Bucket 2

Place character 'e' into the bucket corresponding to its frequency 2.

💡 Characters with higher frequency go into higher index buckets.

Line:

buckets[count].append(char)  # Place char in bucket of its frequency

💡 'e' is the only character in bucket 2.

setup

Initialize Result List

Create an empty list to accumulate the final sorted characters.

💡 This list will hold characters repeated by their frequency in descending order.

Line:

result = []

💡 Result list is ready to collect output.

traverse

Process Bucket 2 (Frequency 2)

Iterate bucket 2 and append 'e' repeated 2 times to the result.

💡 Start from highest frequency to ensure correct order.

Line:

result.append(char * freq_count)  # Append char repeated freq_count times

💡 Characters with highest frequency appear first in the output.

traverse

Process Bucket 1 (Frequency 1) - Append 't'

Append 't' repeated 1 time to the result from bucket 1.

💡 Process all characters in bucket 1 one by one.

Line:

result.append(char * freq_count)  # Append char repeated freq_count times

💡 Characters with same frequency are appended in bucket order.

traverse

Process Bucket 1 (Frequency 1) - Append 'r'

Append 'r' repeated 1 time to the result from bucket 1.

💡 Continue processing remaining characters in bucket 1.

Line:

result.append(char * freq_count)  # Append char repeated freq_count times

💡 All characters with frequency 1 are now appended.

reconstruct

Construct Final String

Join all appended characters in the result list to form the final output string.

💡 Joining the list produces the final frequency sorted string.

Line:

return ''.join(result)

💡 Final string 'eert' is ready to be returned.

from collections import Counter

def frequencySort(s: str) -> str:
    freq = Counter(s)  # STEP 1
    max_freq = max(freq.values(), default=0)  # STEP 2
    buckets = [[] for _ in range(max_freq + 1)]  # STEP 3
    for char, count in freq.items():  # STEP 4-6
        buckets[count].append(char)  # Place char in bucket of its frequency
    result = []  # STEP 7
    for freq_count in range(max_freq, 0, -1):  # STEP 8-10
        for char in buckets[freq_count]:
            result.append(char * freq_count)  # Append char repeated freq_count times
    return ''.join(result)  # STEP 11

if __name__ == '__main__':
    test = "tree"
    print(frequencySort(test))  # Expected: eert or eetr

📊

Sort Characters By Frequency - Watch the Algorithm Execute, Step by Step

Watching each step reveals how frequency-based bucket sorting efficiently groups characters and builds the final sorted string without explicit sorting.

insertmin-heap

1

0

1

1

2

2

peekmin-heap

2

0

insertmin-heap

[]

0

[]

1

[]

2

insertmin-heap

[]

0

['t']

1

[]

2

insertmin-heap

[]

0

['t', 'r']

1

[]

2

insertmin-heap

[]

0

['t', 'r']

1

['e']

2

insertmin-heap

empty heap

extract_maxmin-heap

e

0

e

1

Added: "ee"

extract_maxmin-heap

t

0

Added: "t"

extract_maxmin-heap

r

0

Added: "r"

peekmin-heap

empty heap

Added: "eert"

Key Takeaways

✓ Frequency counting is the key first step to group characters by how often they appear.

Without seeing the counts explicitly, it's hard to grasp how characters are bucketed.

✓ Using buckets indexed by frequency allows grouping characters without sorting them explicitly.

This insight shows how bucket sort leverages frequency as a direct index.

✓ Iterating buckets from highest to lowest frequency ensures the output string is sorted by frequency.

Watching the iteration order clarifies why the final string starts with the most frequent characters.

Practice

1. You are given an unsorted array of integers and asked to find the k-th smallest absolute difference between any two elements. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force nested loop to generate all pairs, then sort the distances and pick the k-th smallest.

B. Sort the array, then use a min-heap to merge pairs starting from adjacent elements to efficiently find the k-th smallest pair distance.

C. Use dynamic programming to build a table of pair distances and select the k-th smallest from the table.

D. Apply a greedy algorithm that repeatedly selects the smallest available pair distance without sorting.

Solution

1. Step 1: Understand problem constraints and approaches

   Brute force (A) is correct but inefficient with O(n^2 log n) time. Dynamic programming (C) is not applicable as pair distances don't form overlapping subproblems. Greedy (D) fails because pair distances are not independent and require sorting.

2. Step 2: Identify optimal approach

   Sorting the array and using a min-heap to merge pairs starting from adjacent elements (B) leverages sorted order to generate pairs in ascending order efficiently, achieving O(n log n + k log n) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap-based merging of sorted pairs is optimal and efficient [OK]

Hint: Heap merge after sorting is optimal for k-th smallest pair distance [OK]

Common Mistakes:

• Assuming DP applies to pair distances
• Thinking greedy works without sorting
• Believing brute force is optimal

2. You need to design a data structure that supports two operations: push(val) which adds an integer to the structure, and pop() which removes and returns the most frequent element. If multiple elements have the same highest frequency, the most recently added among them is removed first. Which approach guarantees optimal time complexity for both operations?

easy

A. Maintain a frequency map and a max-heap keyed by frequency and recency (timestamp) to pop the correct element efficiently.

B. Use dynamic programming to precompute frequencies and then pop elements in order.

C. Use a priority queue keyed only by frequency, ignoring insertion order.

D. Use a single stack and scan it on each pop to find the most frequent element.

Solution

1. Step 1: Understand the problem constraints

   The data structure must return the element with the highest frequency, and if there's a tie, the most recently pushed element among them.

2. Step 2: Evaluate approaches

   Approach A is brute force and inefficient. Approach C ignores recency, so it fails tie-breaking. Approach B uses dynamic programming which is unrelated and inefficient for this problem. Approach D maintains a frequency map and a max-heap keyed by frequency and timestamp, ensuring O(log n) push and pop operations with correct tie-breaking.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max-heap with frequency and timestamp ensures correct order and efficiency [OK]

Hint: Max-heap with freq and timestamp breaks ties correctly [OK]

Common Mistakes:

• Ignoring recency in tie-breaking
• Using a single stack and scanning on pop
• Confusing DP with frequency tracking

3. Consider the following buggy Quickselect implementation. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 4: The comparison operator in the if condition inside partition

B. Line 7: The swap of nums[i] and nums[right]

C. Line 11: The base case check if left == right

D. Line 15: The recursive call when pivot_index < k

Solution

1. Step 1: Identify partition logic

   Partition should move elements greater than pivot to the left for kth largest.

2. Step 2: Locate bug

   The condition uses '<' instead of '>', reversing the order and breaking correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect comparison flips partition logic [OK]

Hint: Partition comparison must match desired order (greater for kth largest) [OK]

Common Mistakes:

• Using wrong comparison direction in partition
• Confusing base case with recursion
• Swapping wrong elements

4. Consider the following buggy code snippet for the minimum cost to hire K workers problem. Which line contains the subtle bug that causes incorrect results on some inputs?

import bisect

def mincostToHireWorkers(quality, wage, K):
    workers = sorted([(w/q, q) for q, w in zip(quality, wage)])
    qualities = []
    sum_quality = 0
    min_cost = float('inf')
    for ratio, q in workers:
        bisect.insort(qualities, q)
        sum_quality += q
        if len(qualities) > K:
            removed = qualities.pop(0)  # BUG: removes smallest quality instead of largest
            sum_quality -= removed
        if len(qualities) == K:
            cost = ratio * sum_quality
            if cost < min_cost:
                min_cost = cost
    return min_cost

medium

A. Line where qualities.pop(0) removes the smallest quality

B. Line where qualities are inserted using bisect.insort

C. Line where workers are sorted by ratio

D. Line where cost is calculated as ratio * sum_quality

Solution

1. Step 1: Identify the data structure usage

   qualities is a sorted list; bisect.insort inserts maintaining ascending order.

2. Step 2: Check removal logic when size exceeds K

   qualities.pop(0) removes the smallest quality, but we want to remove the largest quality to minimize sum_quality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Removing smallest quality increases sum_quality, leading to incorrect cost [OK]

Hint: Remove largest quality, not smallest, to minimize sum [OK]

Common Mistakes:

• Removing smallest quality instead of largest
• Not updating min_cost when size == K
• Sorting workers incorrectly

5. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n, and why?

medium

A. O(n²) because nested loops iterate over frequencies and elements.

B. O(n log n) because sorting is involved in frequency ordering.

C. O(k log n) because a heap of size k is maintained during iteration.

D. O(n) because frequency counting and bucket placement are linear, and iterating buckets is at most n.

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires one pass over n elements -> O(n).

2. Step 2: Analyze bucket creation and iteration

   Creating buckets and placing elements is O(n) since total elements equal n. Iterating buckets from max frequency down is also O(n) in total.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All steps combined remain linear in n [OK]

Hint: Bucket sort avoids sorting unique keys explicitly [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming heap operations dominate