Ransom Note - Solution & Explanation
Problem Statement
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
Example 1:
Input: ransomNote = "a", magazine = "b" Output: false
Example 2:
Input: ransomNote = "aa", magazine = "ab" Output: false
Example 3:
Input: ransomNote = "aa", magazine = "aab" Output: true
Constraints:
1 <= ransomNote.length, magazine.length <= 105ransomNoteandmagazineconsist of lowercase English letters.
Approach Overview
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.
Approach 1: Approach 1: Frequency Counting with Hash Maps
This approach involves using hash maps to count the frequency of each letter in both ransomNote and magazine. The idea is to determine if magazine has enough of each letter to build ransomNote.
- Create a frequency count for each letter in
magazine. - Iterate over each letter in
ransomNoteand check if the magazine frequency is sufficient. - If any letter in
ransomNotehas a higher frequency than inmagazine, returnfalse. - If all letters are accounted for, return
true.
The solution uses an array count of size 26 to store the frequency of each character from 'a' to 'z'. It first increments the counts based on the characters in magazine and then decrements the respective counts as it encounters each character in ransomNote. If any count goes negative, it indicates that ransomNote cannot be formed, hence returning false.
Complexity
Time Complexity: O(m + n), where m and n are the lengths of magazine and ransomNote, respectively.
Space Complexity: O(1), as the space is allocated for a fixed-size frequency array.
Approach 2: Approach 2: Sorting and Two Pointers
Instead of counting character frequencies, we can sort both ransomNote and magazine and use a two-pointer technique to check if magazine contains all letters needed for ransomNote in a sorted order.
- Sort the characters in both
ransomNoteandmagazine. - Initialize two pointers, one for each string.
- Iterate through the sorted strings using the pointers. If the characters match, move both pointers forward.
- If all characters in
ransomNoteare matched, returntrue; otherwise, returnfalse.
This C solution sorts both strings using qsort and iterates using two indices, attempting to match each character from ransomNote with a character from magazine.
Complexity
Time Complexity: O(n log n + m log m), dominated by sorting
Space Complexity: O(1)
Approach 3: Hash Table or Array
We can use a hash table or an array cnt of length 26 to record the number of times each character appears in the string magazine. Then traverse the string ransomNote, for each character c in it, we decrease the number of c by 1 in cnt. If the number of c is less than 0 after the decrease, it means that the number of c in magazine is not enough, so it cannot be composed of ransomNote, just return false.
Otherwise, after the traversal, it means that each character in ransomNote can be found in magazine. Therefore, return true.
The time complexity is O(m + n), and the space complexity is O(C). Where m and n are the lengths of the strings ransomNote and magazine respectively; and C is the size of the character set, which is 26 in this question.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Counting with Hash Maps | Time Complexity: O(m + n), where m and n are the lengths of |
| Approach 2: Sorting and Two Pointers | Time Complexity: O(n log n + m log m), dominated by sorting |
| Hash Table or Array | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Counting with Hash Map | O(n + m) | O(1) | General case. Fastest solution when checking character availability. |
| Sorting and Two Pointers | O(n log n + m log m) | O(1) or O(n) | Useful when data is already sorted or when practicing two-pointer techniques. |
Video Solution
Ransom note | Leetcode #383 • Techdose • 26,460 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Ransom Note easy or hard?
Ransom Note Python/Java solution
How to solve Ransom Note in O(n)?
What is the best approach for Ransom Note?
Is Ransom Note asked at Google/Amazon/Meta?
What data structure is used in Ransom Note?
What is the time complexity of Ransom Note?
Ready to solve this problem?
Practice Ransom Note with our built-in code editor and test cases.
Practice on FleetCode