DSA for Interviews, From Zero

Part 1 · Lesson 10 · 20 min read

Objects, Map and Set

Look values up by name instead of by position. The counting pattern behind a large share of interview questions.

On this page

  1. Look things up by name, not by position
  2. Objects: records with named fields
  3. Map: the dictionary you'll use in DSA
  4. The frequency map pattern
  5. Traced: counting the letters of “banana”
  6. Set: “have I seen this before?”
  7. Why this is fast — a first look
  8. Array, object, Map or Set?
  9. Practice questions (11)
  10. Make it stick
  11. Part 1 complete — what's next

Look things up by name, not by position

An array answers the question “what is at position 3?”. But many questions are different. They ask “how many times have I seen the letter a?” or “what is Asha's age?”. If you search a whole array every time, that is slow.

A better way is to store each value under a key. A key is a name for the value. Then you look the value up directly by its key, like finding a word in a dictionary. A key together with its value is a key–value pair.

JavaScript gives you three tools for this: objects, Map and Set. Many interview solutions use them. Part 5 is built entirely on them.

Objects: records with named fields

An object is a value that groups related data under names. Each name is called a field (or property). Use an object to describe one thing, such as a student or an order. Write it with curly brackets { }, with name: value pairs inside.

JavaScript
const student = {  name: "Asha",  age: 21,  marks: [72, 85, 90],};console.log(student.name);        // Asha        dot notationconsole.log(student["age"]);      // 21          bracket notation (same thing)student.age = 22;                 // change a fieldstudent.city = "Pune";            // add a new fieldconsole.log(student.city);        // Puneconsole.log(student.phone);       // undefined   no such fieldfor (const key in student) {   // for...in gives each field NAME (key)  console.log(key);               // name, age, marks, city (one per line)}

Map: the dictionary you'll use in DSA

A Map is a built-in collection that stores key–value pairs. It is a dictionary: you give it a key and it gives you the value.

You can use a plain object as a dictionary too. But Map was made for this job, and it has three advantages. Any value can be a key, and a number stays a number (in an object, keys become text). It remembers the order in which keys were added. It has a built-in size. For counting and lookups in DSA, use a Map.

JavaScript
const stock = new Map();stock.set("apple", 10);           // add / overwrite a keystock.set("mango", 4);stock.set("apple", 12);           // same key: replaces 10 with 12console.log(stock.get("apple"));  // 12console.log(stock.get("kiwi"));   // undefinedconsole.log(stock.has("mango"));  // trueconsole.log(stock.size);          // 2stock.delete("mango");console.log(stock.size);          // 1for (const [fruit, qty] of stock) {  console.log(fruit, qty);        // apple 12}
OperationMapMeaning
Storem.set(key, value)Add, or replace if the key exists
Readm.get(key)The value, or undefined
Checkm.has(key)true / false
Removem.delete(key)Delete one entry
Countm.sizeNumber of keys

The frequency map pattern

Here is the most useful line in this lesson. To count how often each thing appears, loop once and, for each item, add 1 to its count:

The frequency map — memorise this line
freq.set(x, (freq.get(x) ?? 0) + 1);

freq.get(x) gives the count so far. The first time, there is no count, so it gives undefined. The operator ?? means “if the left side is undefined or null, use the right side”. So ?? 0 gives 0 when there is no count yet. Then add 1 and store the result back.

Many problems start with this one loop. Examples are finding duplicates, anagrams, the most frequent element and the first unique character. A frequency map is simply a Map from each item to how many times it appears.

Traced: counting the letters of “banana”

step 1 / 15
Set up
s = "banana"

Six characters to count.

▶const s = "banana";2const freq = new Map();3for (const ch of s) {4  freq.set(ch, (freq.get(ch) ?? 0) + 1);5}6console.log(freq);
Variables
s"banana"
Console
(nothing printed yet)
One pass over the string. The map grows a new key the first time a letter appears, and just increases the count after that. · interactive

Set: “have I seen this before?”

A Set is a built-in collection that keeps each value only once. If you add a value that is already there, nothing happens. Think of a guest list: a name is either on the list or not. The most useful method is has(). It answers “is this value in the Set?” with true or false, and it is very fast.

JavaScript
const seen = new Set();seen.add(3);seen.add(7);seen.add(3);                 // already there, so nothing happensconsole.log(seen.has(7));    // trueconsole.log(seen.has(5));    // falseconsole.log(seen.size);      // 2const unique = new Set([1, 2, 2, 3, 3, 3]);console.log(unique.size);    // 3console.log([...unique]);    // [ 1, 2, 3 ]   back to an array (spread syntax)

Why this is fast — a first look

Suppose you want to know if 7 is in an array of a million numbers. A linear search may look at all million. A Set or Map works differently. It can jump straight to the place where 7 would be stored. On average this takes about the same short time for ten items or for ten million.

So a Map or Set can often replace a “loop inside a loop” with a single loop. Lesson 12 puts numbers on this (O(n) compared with O(1)). Lesson 15 shows how it works inside.

Dry run · “does the collection contain x?”
Stored inHow it checksWork for 1,000,000 items
Arraylook at items one by oneup to 1,000,000 checks
Set / Mapjump straight to x's slotabout 1 check (on average)

Array, object, Map or Set?

You need…Use
An ordered list, access by positionArray
One record with named fields (a student, an order)Object
Counts, or a lookup from key to valueMap
Uniqueness, or fast “have I seen it?”Set

Practice questions

Q1Character frequencyEasy

Count how many times each character appears.

Example 1
Input: "banana"
Output:
b: 1
a: 3
n: 2
Explanation: b appears once, a three times and n twice. The characters are listed in the order they first appear.
Stuck? Open one hint at a time
Hint 1
Use a Map that stores each character and its count.
Hint 2
For each character, write: freq.set(ch, (freq.get(ch) ?? 0) + 1).
Show all 3 solutions with explanations
Approach 1Map
The idea

Go through the string once. Add 1 to the character's count. The first time, start from 0.

JavaScript
function charFrequency(s) {  const freq = new Map();  for (const ch of s) {    freq.set(ch, (freq.get(ch) ?? 0) + 1);  }  return freq;}for (const [ch, count] of charFrequency("banana")) {  console.log(ch + ": " + count);}/* Output:b: 1a: 3n: 2*/
How it works

This is the frequency-map pattern traced in this lesson. A Map remembers the order in which the keys were first added.

Approach 2Plain object
The idea

This is the same idea with an object. Each character is a property name.

JavaScript
function charFrequency(s) {  const freq = {};  for (const ch of s) {    freq[ch] = (freq[ch] || 0) + 1;  }  return freq;}console.log(charFrequency("banana")); // { b: 1, a: 3, n: 2 }
How it works

This is very common in JavaScript code. freq[ch] || 0 gives 0 when the property does not exist yet. (|| uses the right side for any “empty” value such as 0 or undefined. That is fine here, because a count of 0 and “no count” both mean 0.)

Approach 3Array of 26 counters
The idea

For lowercase letters only, use the character-code trick from Lesson 9. It turns each letter into a position from 0 to 25.

JavaScript
function charFrequency(s) {  const counts = new Array(26).fill(0);  for (const ch of s) {    counts[ch.charCodeAt(0) - 97]++;          // 97 is the code of "a"  }  return counts;}const counts = charFrequency("banana");console.log(counts[0], counts[1], counts[13]); // 3 1 2   (a, b, n)
How it works

An array is slightly faster than a Map and uses a fixed amount of memory. It works only when you know in advance which characters are possible.

Which approach should you use?

Use a Map (Approach 1) by default. It works for any characters. Use the 26-counter array when the problem says “lowercase English letters only”.

Q2Contains duplicateEasy

Return true if any value appears at least twice. (LeetCode 217.)

Example 1
Input: [1, 2, 3, 1]
Output: true
Explanation: 1 appears twice.
Example 2
Input: [1, 2, 3, 4]
Output: false
Explanation: Every value is different.
Stuck? Open one hint at a time
Hint 1
Brute force means trying every possibility. Here that means comparing every pair. Can you avoid that?
Hint 2
Walk through the array. Remember every value you have seen in a Set. If a value is already in the Set, you found a duplicate.
Show all 3 solutions with explanations
Approach 1Compare every pair
The idea

Two nested loops (a loop inside a loop) check each pair (i, j) where i < j.

JavaScript
function containsDuplicate(nums) {  for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] === nums[j]) return true;    }  }  return false;}console.log(containsDuplicate([1, 2, 3, 1])); // trueconsole.log(containsDuplicate([1, 2, 3, 4])); // false
How it works

This is correct, but for n items it makes about n²/2 comparisons (Lesson 6). For 100,000 items that is about 5 billion, which is far too slow.

Approach 2Sort, then check neighbours
The idea

After sorting, equal values sit next to each other. So compare each item with its neighbour.

JavaScript
function containsDuplicate(nums) {  const sorted = [...nums].sort((a, b) => a - b);  for (let i = 1; i < sorted.length; i++) {    if (sorted[i] === sorted[i - 1]) return true;  }  return false;}console.log(containsDuplicate([1, 2, 3, 1])); // true
How it works

This is much faster than comparing every pair. Sorting still costs more than one pass (Lesson 12). We sort a copy because sort changes the original array. If you may change the input, you can sort it directly and save the memory for the copy.

Approach 3Set of values seen so far
The idea

Check each value against a Set of the earlier values. Then add it to the Set.

JavaScript
function containsDuplicate(nums) {  const seen = new Set();  for (const x of nums) {    if (seen.has(x)) return true;    seen.add(x);  }  return false;}console.log(containsDuplicate([1, 2, 3, 1])); // trueconsole.log(containsDuplicate([1, 2, 3, 4])); // false// Even shorter: if the Set is smaller than the array, something was repeatedconsole.log(new Set([1, 2, 3, 1]).size !== 4); // true
How it works

Each value is checked once, and has is very fast. This is the “have I seen it before?” idea that Part 5 is built on.

Which approach should you use?

Approach 3 is the expected answer for LeetCode 217. It needs one pass. Mention Approach 1 as the brute force. Mention Approach 2 if memory is limited.

Q3First non-repeating characterMedium

Return the first character that appears exactly once, or null.

Example 1
Input: "leetcode"
Output: "l"
Explanation: l appears once and comes first. (e appears three times.)
Example 2
Input: "loveleetcode"
Output: "v"
Explanation: l and o repeat. v is the first character that appears only once.
Example 3
Input: "aabb"
Output: null
Explanation: Every character repeats.
Stuck? Open one hint at a time
Hint 1
You cannot know whether a character repeats until you have seen the whole string.
Hint 2
Pass 1: count every character. Pass 2: walk the string again. Return the first character whose count is 1.
Show all 2 solutions with explanations
Approach 1Count, then scan again
The idea

Use two passes. First build a frequency map. Then walk the string again and find the first character with count 1.

JavaScript
function firstUnique(s) {  const freq = new Map();  for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1);  for (const ch of s) {    if (freq.get(ch) === 1) return ch;  }  return null;}console.log(firstUnique("leetcode"));     // lconsole.log(firstUnique("loveleetcode")); // vconsole.log(firstUnique("aabb"));         // null
How it works

The second pass walks the string and not the map. So “first” means first in the original order. LeetCode 387 asks for the index. For that, use an index loop and return i instead of the character.

Approach 2indexOf equals lastIndexOf
The idea

A character is unique if its first position and its last position are the same.

JavaScript
function firstUnique(s) {  for (const ch of s) {    if (s.indexOf(ch) === s.lastIndexOf(ch)) return ch;  }  return null;}console.log(firstUnique("loveleetcode")); // v
How it works

This is short. But indexOf and lastIndexOf each scan the string, so the total work grows like n². It is fine for short strings only.

Which approach should you use?

Use Approach 1. It makes two simple passes, and each pass checks every character once.

Q4Most frequent elementEasy

Return the value that appears most often.

Example 1
Input: [1, 3, 2, 3, 3, 2]
Output: 3
Explanation: 3 appears three times, 2 appears twice and 1 appears once.
Stuck? Open one hint at a time
Hint 1
Count first with a frequency map.
Hint 2
Then find the entry with the largest count. This is the “best so far” pattern.
Show all 2 solutions with explanations
Approach 1Count, then pick the best
The idea

Build the frequency map. Then loop over it and keep the value with the highest count.

JavaScript
function mostFrequent(nums) {  const freq = new Map();  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);  let best = null, bestCount = 0;  for (const [x, count] of freq) {    if (count > bestCount) {      best = x;      bestCount = count;    }  }  return best;}console.log(mostFrequent([1, 3, 2, 3, 3, 2])); // 3
How it works

This joins two patterns you already know: a frequency map and best-so-far.

Approach 2Track the best while counting
The idea

Update the best answer every time a count goes up. Then you need only one loop.

JavaScript
function mostFrequent(nums) {  const freq = new Map();  let best = null, bestCount = 0;  for (const x of nums) {    const c = (freq.get(x) ?? 0) + 1;    freq.set(x, c);    if (c > bestCount) {      best = x;      bestCount = c;    }  }  return best;}console.log(mostFrequent([1, 3, 2, 3, 3, 2])); // 3
How it works

The best answer can change only when a count goes up. So it is enough to check at that moment.

Which approach should you use?

Both are correct and do about the same work. Approach 1 is easier to read. Approach 2 saves the second loop.

Q5Valid anagramEasy

Do the two strings contain exactly the same letters, the same number of times? (LeetCode 242.)

Example 1
Input: "listen", "silent"
Output: true
Explanation: Both words use the letters e, i, l, n, s, t once each.
Example 2
Input: "rat", "car"
Output: false
Explanation: rat has a t, but car does not have a t.
Stuck? Open one hint at a time
Hint 1
Two words are anagrams when they use the same letters the same number of times.
Hint 2
Count the letters of the first word up. Count the letters of the second word down. If a count would go below zero, it is not an anagram.
Show all 3 solutions with explanations
Approach 1Sort both and compare
The idea

If you sort the letters of two anagrams, you get the same text.

JavaScript
function isAnagram(a, b) {  const sortWord = (w) => w.split("").sort().join("");  return sortWord(a) === sortWord(b);}console.log(isAnagram("listen", "silent")); // trueconsole.log(isAnagram("rat", "car"));       // false
How it works

“listen” and “silent” both become “eilnst”. This is very easy to write. But sorting costs more than counting.

Approach 2Count up and down with a Map
The idea

Add 1 for each letter of a. Subtract 1 for each letter of b.

JavaScript
function isAnagram(a, b) {  if (a.length !== b.length) return false;  const count = new Map();  for (const ch of a) count.set(ch, (count.get(ch) ?? 0) + 1);  for (const ch of b) {    const c = count.get(ch) ?? 0;    if (c === 0) return false;     // b has more of this letter than a    count.set(ch, c - 1);  }  return true;}console.log(isAnagram("listen", "silent")); // trueconsole.log(isAnagram("rat", "car"));       // false
How it works

The lengths are equal and no count ever goes below zero. So every count must end at exactly 0.

Approach 326 counters
The idea

For lowercase letters, use an array of 26 counters instead of a Map.

JavaScript
function isAnagram(a, b) {  if (a.length !== b.length) return false;  const counts = new Array(26).fill(0);  for (let i = 0; i < a.length; i++) {    counts[a.charCodeAt(i) - 97]++;    counts[b.charCodeAt(i) - 97]--;  }  return counts.every((c) => c === 0);}console.log(isAnagram("listen", "silent")); // true
How it works

Both words are processed in the same loop. At the end, every counter must be 0.

Which approach should you use?

Approach 1 is a good first answer. Approach 2 or 3 is the efficient answer for LeetCode 242. Use Approach 3 when the input is lowercase letters only.

Q6Intersection of two arraysEasy

Return the values that appear in both arrays, each only once, in any order. (LeetCode 349.)

Example 1
Input: [1, 2, 2, 1], [2, 2]
Output: [2]
Explanation: 2 is the only value in both arrays. It is listed once.
Example 2
Input: [4, 9, 5], [9, 4, 9, 8, 4]
Output: [9, 4]
Explanation: 4 and 9 are in both arrays. Any order is accepted.
Stuck? Open one hint at a time
Hint 1
Put one array into a Set. Then you can check quickly whether a value is in it.
Hint 2
Walk the other array and collect the values that are in the Set. Use a second Set so that each answer appears only once.
Show all 3 solutions with explanations
Approach 1Set lookup
The idea

Make a Set from the first array. Make a second Set for the answers. Then make one pass over the second array.

JavaScript
function intersection(a, b) {  const inA = new Set(a);  const result = new Set();  for (const x of b) {    if (inA.has(x)) result.add(x);  }  return [...result];}console.log(intersection([1, 2, 2, 1], [2, 2]));       // [ 2 ]console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [ 9, 4 ]
How it works

Each value is checked once. The result Set removes repeated answers for you.

Approach 2filter with includes
The idea

Keep the values of one array that the other array also has. Then remove duplicates.

JavaScript
const intersection = (a, b) => [...new Set(a.filter((x) => b.includes(x)))];console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [ 4, 9 ]
How it works

This is one line. But includes scans b for every item of a, so the work grows like n × m (the two array sizes multiplied).

Approach 3Sort both, then two pointers
The idea

Sort both arrays. Then use one pointer in each array. Compare the two values and move the pointer that points to the smaller value.

JavaScript
function intersection(a, b) {  a = [...a].sort((x, y) => x - y);  b = [...b].sort((x, y) => x - y);  const result = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) {    if (a[i] < b[j]) i++;    else if (a[i] > b[j]) j++;    else {      if (result[result.length - 1] !== a[i]) result.push(a[i]);      i++;      j++;    }  }  return result;}console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [ 4, 9 ]
How it works

This helps when the arrays are already sorted or memory is limited. Lesson 21 covers two pointers in depth.

Which approach should you use?

Approach 1 is the standard answer for LeetCode 349. Approach 3 is the follow-up when the inputs are already sorted.

Q7Count distinct valuesEasy

How many different values does the array contain?

Example 1
Input: [1, 2, 2, 3, 3, 3]
Output: 3
Explanation: The distinct (different) values are 1, 2 and 3.
Stuck? Open one hint at a time
Hint 1
Which data structure keeps each value only once?
Show all 2 solutions with explanations
Approach 1Set size
The idea

Put everything into a Set. The size of the Set is the number of distinct values.

JavaScript
const countDistinct = (nums) => new Set(nums).size;console.log(countDistinct([1, 2, 2, 3, 3, 3])); // 3
How it works

The Set ignores values it already has.

Approach 2Sort and count changes
The idea

After sorting, a new distinct value starts wherever an item is different from the one before it.

JavaScript
function countDistinct(nums) {  const s = [...nums].sort((a, b) => a - b);  let count = s.length > 0 ? 1 : 0;  for (let i = 1; i < s.length; i++) {    if (s[i] !== s[i - 1]) count++;  }  return count;}console.log(countDistinct([3, 1, 2, 3, 2, 3])); // 3
How it works

No Set is needed. This is the “remove duplicates from a sorted array” idea from Lesson 8. Here we count instead of copy.

Which approach should you use?

Use the Set (Approach 1).

Q8Class report from recordsEasy

Given an array of { name, marks } objects, print the average marks and the name of the topper.

Example 1
Input: Asha 72, Ravi 91, Meera 71
Output:
Average: 78
Topper: Ravi
Explanation: (72 + 91 + 71) / 3 = 234 / 3 = 78. Ravi has the highest marks.
Stuck? Open one hint at a time
Hint 1
Each student is an object. Read the fields with s.marks and s.name.
Hint 2
Use an accumulator (a variable that collects a total) for the sum. Use best-so-far for the topper.
Show all 2 solutions with explanations
Approach 1One loop
The idea

In one loop, add up the marks and keep the student with the highest marks.

JavaScript
const students = [  { name: "Asha", marks: 72 },  { name: "Ravi", marks: 91 },  { name: "Meera", marks: 71 },];let total = 0;let topper = students[0];for (const s of students) {  total += s.marks;  if (s.marks > topper.marks) topper = s;}console.log("Average: " + total / students.length); // Average: 78console.log("Topper: " + topper.name);              // Topper: Ravi
How it works

Real data often arrives as an array of objects (from an API, a database or a test case). The patterns are exactly the same as for arrays of numbers.

Approach 2reduce and sort
The idea

Use reduce to get the total. Sort a copy by marks to find the topper.

JavaScript
const students = [  { name: "Asha", marks: 72 },  { name: "Ravi", marks: 91 },  { name: "Meera", marks: 71 },];const total = students.reduce((sum, s) => sum + s.marks, 0);const ranked = [...students].sort((a, b) => b.marks - a.marks);console.log("Average: " + total / students.length); // Average: 78console.log("Topper: " + ranked[0].name);           // Topper: Ravi
How it works

(a, b) => b.marks - a.marks sorts by marks, largest first. Sorting gives the full ranking. This helps if you also need second and third place.

Which approach should you use?

Approach 1 does the least work. Approach 2 is useful when you need the whole ranking.

Q9Two SumMedium

Return the indices of the two numbers that add up to target. Exactly one answer exists, and you may not use the same element twice. (LeetCode 1.)

Example 1
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9.
Example 2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: nums[1] + nums[2] = 2 + 4 = 6. (3 + 3 is not allowed, because you cannot use the same element twice.)
Stuck? Open one hint at a time
Hint 1
Brute force: try every pair (i, j). How many pairs is that?
Hint 2
For each number x, the partner you need is target - x. Have you already seen it?
Hint 3
Keep a Map that stores the value and the index of every number you have seen so far. Check for the partner before you add the current number.
Show all 3 solutions with explanations
Approach 1Try every pair
The idea

Use two nested loops. Return the first pair that adds up to the target.

JavaScript
function twoSum(nums, target) {  for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] + nums[j] === target) return [i, j];    }  }  return [];}console.log(twoSum([2, 7, 11, 15], 9)); // [ 0, 1 ]console.log(twoSum([3, 2, 4], 6));      // [ 1, 2 ]
How it works

This is always a good first answer to say out loud. It makes about n²/2 checks, so it is too slow for large inputs.

Approach 2Map of values seen so far
The idea

For each number, look for its partner in a Map. If the partner is not there, store the number and its index.

JavaScript
function twoSum(nums, target) {  const indexOf = new Map();             // stores: value, then its index  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i];    if (indexOf.has(need)) return [indexOf.get(need), i];    indexOf.set(nums[i], i);  }  return [];}console.log(twoSum([2, 7, 11, 15], 9)); // [ 0, 1 ]console.log(twoSum([3, 2, 4], 6));      // [ 1, 2 ]
How it works
Dry run · nums = [3, 2, 4], target = 6
inums[i]needin map?map after
033no{3 → 0}
124no{3 → 0, 2 → 1}
242yes, at 1return [1, 2]
Approach 3Sort with indexes, then two pointers
The idea

Sort the values, but remember their original positions. Then start one pointer at each end and move them towards each other.

JavaScript
function twoSum(nums, target) {  const items = nums.map((value, index) => ({ value, index }));  items.sort((a, b) => a.value - b.value);  let left = 0, right = items.length - 1;  while (left < right) {    const sum = items[left].value + items[right].value;    if (sum === target) return [items[left].index, items[right].index].sort((a, b) => a - b);    if (sum < target) left++;      // need a bigger sum    else right--;                  // need a smaller sum  }  return [];}console.log(twoSum([3, 2, 4], 6)); // [ 1, 2 ]
How it works

If the sum is too small, only moving the left pointer can make it bigger. If the sum is too big, only moving the right pointer can make it smaller. This is the main idea of LeetCode 167 (Lesson 21).

Which approach should you use?

LeetCode 1 is one of the best-known interview questions. First say Approach 1. Then give Approach 2, which makes one pass with a Map. Lesson 26 compares all three in detail.

Q10Group words by first letterMedium

Group the words by their first letter.

Example 1
Input: ["apple", "bat", "avocado", "ball", "cat"]
Output:
a: apple, avocado
b: bat, ball
c: cat
Explanation: Words that start with the same letter are put in the same group, in their original order.
Stuck? Open one hint at a time
Hint 1
Use a Map. The key is the letter and the value is a list of words.
Hint 2
The first time you see a letter, create an empty list for it. Then push the word into that list.
Show all 2 solutions with explanations
Approach 1Map of arrays
The idea

The key is the first letter. The value is an array of the words that start with that letter.

JavaScript
function groupByFirstLetter(words) {  const groups = new Map();  for (const w of words) {    const key = w[0];    if (!groups.has(key)) groups.set(key, []);    groups.get(key).push(w);  }  return groups;}for (const [letter, list] of groupByFirstLetter(["apple", "bat", "avocado", "ball", "cat"])) {  console.log(letter + ": " + list.join(", "));}/* Output:a: apple, avocadob: bat, ballc: cat*/
How it works

“Create the list the first time you see a key, then push into it” is the grouping pattern. If you change the key to the word's sorted letters, this becomes Group Anagrams (LeetCode 49, Lesson 27).

Approach 2Object with reduce
The idea

Build an object whose property names are the letters.

JavaScript
const groups = ["apple", "bat", "avocado", "ball", "cat"].reduce((acc, w) => {  (acc[w[0]] ??= []).push(w);       // create the list if missing, then push  return acc;}, {});console.log(groups); // { a: [ 'apple', 'avocado' ], b: [ 'bat', 'ball' ], c: [ 'cat' ] }
How it works

x ??= [] sets x to an empty array only if x is undefined or null. This is short, but it is harder for beginners to read.

Which approach should you use?

Use Approach 1. It is clear and it works with keys of any type.

Q11Ransom noteEasy

Can the ransom note be built from the letters of the magazine, using each letter at most once? (LeetCode 383.)

Example 1
Input: ransomNote = "aa", magazine = "aab"
Output: true
Explanation: The magazine has two a letters. That is enough for the note.
Example 2
Input: ransomNote = "aa", magazine = "ab"
Output: false
Explanation: The note needs two a letters, but the magazine has only one.
Stuck? Open one hint at a time
Hint 1
Each magazine letter can be used only once. Count the letters that the magazine has.
Hint 2
Then go through the note and use up one count for each letter. If a count is already 0, return false.
Show all 2 solutions with explanations
Approach 1Count the magazine, use it up
The idea

Make a frequency map of the magazine. Then subtract 1 for each letter of the note.

JavaScript
function canConstruct(ransomNote, magazine) {  const available = new Map();  for (const ch of magazine) available.set(ch, (available.get(ch) ?? 0) + 1);  for (const ch of ransomNote) {    const c = available.get(ch) ?? 0;    if (c === 0) return false;    available.set(ch, c - 1);  }  return true;}console.log(canConstruct("aa", "aab")); // trueconsole.log(canConstruct("aa", "ab"));  // false
How it works

This is the same count-up and count-down idea as the anagram question. The difference is that the magazine may have letters left over.

Approach 226 counters
The idea

The input has only lowercase letters, so an array of 26 counters works.

JavaScript
function canConstruct(ransomNote, magazine) {  const counts = new Array(26).fill(0);  for (const ch of magazine) counts[ch.charCodeAt(0) - 97]++;  for (const ch of ransomNote) {    const i = ch.charCodeAt(0) - 97;    if (counts[i] === 0) return false;    counts[i]--;  }  return true;}console.log(canConstruct("aa", "aab")); // true
How it works

This is the same logic, with a fixed amount of memory.

Which approach should you use?

Both are accepted for LeetCode 383. Use the array when the problem says the input is lowercase letters.

Make it stick

Make it stick — close this page, then
  1. Write the frequency-map line from memory and explain each part of it.
  2. Solve “contains duplicate” with a Set, then say why it beats two nested loops.
  3. Name one job each for an array, an object, a Map and a Set.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

Part 1 complete — what's next

You can now write variables, conditions, both kinds of loop, nested loops and functions. You can also work with arrays, strings, Maps and Sets. These are the basic tools that every DSA problem uses. Before you move on, go back and solve two questions from each lesson again without looking. If one feels hard, read that lesson once more.

Part 2 — Thinking Like a Problem-Solver starts with how to read an interview question well. Then it teaches Big-O, which is a way to count how much work your loops really do.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Related series