Ransom Note - Video Solutions

Problem Overview: You are given two strings: ransomNote and magazine. Determine whether the ransom note can be constructed using letters from the magazine. Each character in magazine can only be used once, so you must verify that the magazine contains at least the same frequency of every character required by the ransom note.

Approach 1: Frequency Counting with Hash Maps (Time: O(n + m), Space: O(1))

This method counts how many times each character appears in the magazine, then checks whether the ransom note can consume those counts. First iterate through magazine and store frequencies in a hash map or fixed-size array for lowercase letters. Then iterate through ransomNote, decrementing the count for each character. If any count becomes negative or missing, the note cannot be constructed. The key insight: verifying character availability is a constant-time hash lookup instead of repeatedly scanning the string.

Because the alphabet is limited (26 lowercase letters), the auxiliary space is effectively constant. This approach runs in linear time relative to the combined lengths of both strings. It’s the most direct solution using hash tables and frequency counting, and it works well for any string size.

Approach 2: Sorting and Two Pointers (Time: O(n log n + m log m), Space: O(1) or O(n))

This strategy sorts both strings first. After sorting, traverse them using two pointers. One pointer scans the sorted magazine string while the other tracks characters in ransomNote. When characters match, advance both pointers since the letter is successfully used. If the magazine character is smaller, advance only the magazine pointer. If the ransom note character is smaller, construction is impossible because the required letter does not exist ahead.

The sorted ordering groups identical characters together, which makes comparison straightforward without a hash map. However, sorting introduces an O(n log n) cost, making it slower than the counting approach for large inputs. This method mainly demonstrates pointer techniques on sorted string data.

Recommended for interviews: Frequency counting with a hash map or fixed array is the expected answer. It runs in linear time and directly models the constraint that each magazine letter can only be used once. Interviewers often accept either a hash map or a 26-length integer array. Explaining the sorting approach shows awareness of alternative strategies, but the O(n) counting solution demonstrates stronger algorithmic judgment.