Is Ransom Note easy or hard?

Ransom Note is classified as an Easy problem with an acceptance rate around 65%. The challenge focuses on recognizing that character frequency counting eliminates the need for repeated searches, enabling a simple linear-time solution.

Ransom Note Python/Java solution

In Python, developers typically use a dictionary or a list of 26 integers to store character frequencies. In Java, a HashMap or an int[26] array is common. Both implementations follow the same logic: count magazine characters, then decrement counts while scanning the ransom note.

How to solve Ransom Note in O(n)?

Iterate through the magazine and count character frequencies using a hash map or a 26-element integer array. Then iterate through the ransom note and decrease the corresponding counts. If any character count drops below zero, the ransom note cannot be constructed. Each operation is constant time, giving an overall O(n + m) solution.

What is the best approach for Ransom Note?

The best approach uses frequency counting with a hash map or a fixed array of size 26. Count how many times each character appears in the magazine, then decrement counts while scanning the ransom note. If any required character is unavailable, return false. This method runs in O(n + m) time and O(1) space.

Is Ransom Note asked at Google/Amazon/Meta?

Ransom Note is a common easy-level interview problem and has appeared in coding interviews and online assessments at companies like Amazon and Meta. It tests understanding of hash maps, frequency counting, and basic string manipulation—skills frequently evaluated in early interview rounds.

What data structure is used in Ransom Note?

The typical data structure is a hash table or a fixed-size frequency array. These structures store the count of each character in the magazine and allow constant-time updates and lookups while processing the ransom note.

What is the time complexity of Ransom Note?

The optimal solution runs in O(n + m) time, where n is the length of the magazine and m is the length of the ransom note. Each string is scanned once while performing constant-time hash lookups or array updates. Space complexity is O(1) because only 26 character counts are stored.

Description Solution Video 8:21

383. Ransom Note

Easy66.3% acceptance14 companies

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 <= 10⁵
ransomNote and magazine consist of lowercase English letters.

Asked at 14 companies

Anduril Tripadvisor Karat Criteo Disney Bloomberg Apple Spotify Microsoft SAP

Google Amazon

+2 more

Topics

8:21

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

383. Ransom Note

Asked at 14 companies

Topics

Similar problems