Domain 2MediumCORE

Word Frequency

The task requires reading a text file (words.txt), counting the occurrences of each word, and printing them sorted by frequency in descending order.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 1

192. Word Frequency

Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 25.6%


Problem Breakdown

The task requires reading a text file (words.txt), counting the occurrences of each word, and printing them sorted by frequency in descending order. Inputs: A single string or file path containing words separated by whitespace (spaces/newlines). The content contains only lowercase letters and spaces. Outputs: Lines formatted as word count, sorted strictly by count from highest to lowest. Constraints & Edge Cases:

  1. Whitespace Handling: Words are separated by one or more whitespaces; the solution must ignore multiple consecutive spaces (not just single space).
  2. Empty Input: If the file is empty, output should be empty without crashing.
  3. Ties: The problem guarantees unique frequencies for each word, so secondary sort keys aren’t needed.
  4. Punctuation: Assumed not to exist based on constraints (only lowercase chars and spaces).

Intuition

A naive approach would read the file character-by-character or line-by-line into a list of strings, then iterate through that list to build counts using a dictionary/hash map. While this works in Python, it’s inefficient if we manually manage string parsing for every word. The key insight is leveraging built-in tokenization (split()) which automatically handles multiple spaces and newlines as delimiters. For counting, collections.Counter provides an optimized hash-map implementation that runs faster than a raw dictionary loop. If this were Bash (as the original problem suggests), we would use pipes: tr ' ' '\n' | sort | uniq -c. In Python, we replicate this logic using standard library tools to avoid external dependencies or manual parsing loops.

Approach

  1. Read Input: Open and read all content from words.txt (or stdin).
  2. Tokenize: Use the string method .split() without arguments; it treats any sequence of whitespace as a single delimiter, handling multiple spaces automatically.
  3. Count: Pass the list of words to collections.Counter, which builds an O(1) lookup table for frequencies in one pass over the data.
  4. Sort & Output: Extract items from the Counter and sort them by their count value (key=lambda x: x[1]) in descending order. Iterate through the sorted list, printing each word-count pair formatted as required.

Complexity Analysis

  • Time Complexity: O(N+Klog⁡K)O(N + K \log K), where NN is the total number of words (for reading and counting) and KK is the number of unique words (for sorting). Since we must read every character/word at least once to count them, this dominates. Sorting takes logarithmic time relative to unique keys.
  • Space Complexity: O(K)O(K), where KK is the number of unique words stored in the Counter hash map and the sorted list.

Solution

import collections
from sys import stdin # Or open('words.txt') depending on environment usage

def word_frequency(filename):
    """
    Calculates frequency of each word in a text file 
    and prints them sorted by descending frequency.
    """
    
    try:
        with open(filename, 'r') as f:
            content = f.read()
        
        # split() handles multiple spaces/newlines automatically
        words = content.split() 
        
        if not words:
            return

        counter = collections.Counter(words)
        
        # Sort by count (value), descending. 
        # Key is x[1] because Counter items are tuples (word, count).
        sorted_words = sorted(counter.items(), key=lambda item: item[1], reverse=True)
        
        for word, freq in sorted_words:
            print(f"{word} {freq}")

    except FileNotFoundError:
        # Graceful handling if file doesn't exist
        pass

# Example usage (assuming words.txt exists):
if __name__ == "__main__":
    word_frequency('words.txt')

Edge Cases Handled

  • Empty File: The split() returns an empty list; the Counter is empty, resulting in no output lines.
  • Multiple Spaces/Blank Lines: Python’s .split() without arguments treats consecutive whitespace as a single separator and ignores trailing whitespace at line ends or file end automatically.
  • Missing File: Wrapped in try-except to prevent runtime crash if words.txt is not found (though typically LeetCode environments guarantee input existence).