Counting Coding Problems: 118 Questions with Solutions
118 counting coding problems — 47 easy · 63 medium · 8 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 118
- By difficulty: 47 easy · 63 medium · 8 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Problems answered by tallying: how many of each value, how many pairs satisfy a rule, how many ways to reach a total. A frequency array or map is usually the whole solution; the skill is choosing what to count and noticing when the count can be updated incrementally instead of recomputed.
How counting works, step by step
s = "loop", t = "pool"- "loop" and "pool" both have 4 letters, so they are anagrams exactly when each letter appears equally often in both. Keep one counter per letter: s adds one, t takes one away, and every counter must end at 0.
- s[0] = 'l', so count[l] goes up to 1: one 'l' that t will have to match.
- s[1] = 'o', so count[o] goes up to 1.
- s[2] = 'o' again, so count[o] rises to 2: t will need 2 of them to match.
- s[3] = 'p', so count[p] goes up to 1.
- Now t takes letters back: t[0] = 'p', so count[p] drops to 0. A counter going below 0 would mean t has a letter s lacks, and the answer would be false at once.
- t[1] = 'o', so count[o] drops to 1: s still has 1 more 'o' than t so far.
- t[2] = 'o', so count[o] drops to 0: s and t have used the same number of 'o'.
- t[3] = 'l', so count[l] drops to 0: s and t have used the same number of 'l'.
- Every counter is back to 0, so "pool" uses exactly the letters of "loop": they are anagrams. Two passes over n letters and at most 26 counters: O(n) time, O(1) extra space.
Counting study plan
14 of the 118 Counting problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 104 in the full list below are practice at your own pace. Then move on to Math.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Valid Anagram Easy
- Task Scheduler Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Majority Element II Medium
- Count Servers that Communicate Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Count Anagrams Hard
Counting: the essentials
When to reach for it
"How many pairs", "most frequent", "can these letters build that word", "make every count equal", "the first value that appears once". If the answer depends only on how often each value occurs, not where, discard the positions and count. If it asks for pairs of equal values, arithmetic on the counts replaces the pair loop. The same tally keyed by anything other than small integers is a Hash Table.
The pattern
Build the tally in one pass, then reason about the counts. A value seen c times forms c × (c − 1) ÷ 2 equal pairs; counting as you go — adding the current count before incrementing it — gives the same total in a single pass. "Can A be built from B" is a check that every count in A is at most the matching count in B.
def num_identical_pairs(nums):
seen, pairs = {}, 0
for x in nums:
pairs += seen.get(x, 0) # x pairs with every earlier copy
seen[x] = seen.get(x, 0) + 1
return pairs
Cost
O(n) time. Space is O(k) for k distinct values, which is O(1) for a fixed alphabet such as the 26 lowercase letters.
Common mistakes
- Counting ordered pairs when the question wants unordered ones, or the reverse — a factor of two either way.
- Overflow: 10⁵ equal values form about 5 × 10⁹ pairs, beyond a 32-bit
int. - Recounting from scratch for every query when the tally can be updated one element at a time.
- Checking only the letters of one word when both words' counts matter.
Start with
- Number of Good Pairs: pairs from counts.
- Ransom Note: one tally checked against another.
- Task Scheduler: the most frequent count decides the answer.
All counting problems
Easy (47)
- Design Parking System Design, Simulation
- Sort a Linked List of 0s, 1s and 2s Linked List, Sorting
- Check if Any Element Has Prime Frequency Array, Hash Table, Math
- Find Most Frequent Vowel and Consonant Hash Table, String
- Maximum Difference Between Even and Odd Frequency I Hash Table, String
- Find Valid Pair of Adjacent Digits in String Hash Table, String
- Most Frequent Number Following Key In an Array Array, Hash Table
- Check Whether Two Strings are Almost Equivalent Hash Table, String
- Kth Distinct String in an Array Array, Hash Table, String
- Longer Contiguous Segments of Ones than Zeros String
- Check if One String Swap Can Make Strings Equal Hash Table, String
- Increasing Decreasing String Hash Table, String
- Uncommon Words from Two Sentences Hash Table, String
- Count Elements With Strictly Smaller and Greater Elements Array, Sorting
- Number Of Rectangles That Can Form The Largest Square Array
- Most Frequent Even Element Array, Hash Table
- Rearrange Characters to Make Target String Hash Table, String
- Number of Beautiful Pairs Array, Hash Table, Math
- Split the Array Array, Hash Table
- Best Poker Hand Array, Hash Table, Greedy
- Substrings of Size Three with Distinct Characters String, Hash Table, Sliding Window
- Count Number of Pairs With Absolute Difference K Array, Hash Table
- Intersection of Multiple Arrays Array, Hash Table
- Find the Maximum Divisibility Score Array, Math
- Check if Number Has Equal Digit Count and Digit Value Hash Table, String
- Counting Elements Hash Table, Array
- Check if All Characters Have Equal Number of Occurrences Hash Table, String
- Find Words That Can Be Formed by Characters Hash Table, String
- Maximum Number of Pairs in Array Array, Hash Table
- Count Elements With Maximum Frequency Array, Hash Table
- Sum of Unique Elements Array, Hash Table
- Count Tested Devices After Test Operations Array, Simulation
- Maximum Number of Balls in a Box Math, Hash Table
- Redistribute Characters to Make All Strings Equal Array, String
- Maximum Population Year Array, Prefix Sum
- Find Lucky Integer in an Array Array, Hash Table
- Count the Number of Consistent Strings Array, Hash Table, String
- Sort Integers by The Number of 1 Bits Array, Bit Manipulation, Sorting
- Number of Equivalent Domino Pairs Array, Hash Table
- Maximum Count of Positive Integer and Negative Integer Array, Binary Search
- Split a String in Balanced Strings String, Greedy
- Determine if String Halves Are Alike String
- Maximum Number of Balloons Hash Table, String
- Ransom Note Hash Table, String
- First Unique Character in a String Hash Table, String, Queue
- Number of Good Pairs Array, Hash Table, Math
- Valid Anagram Hash Table, String, Sorting
Medium (63)
- Frequency Tracker Hash Table, Design
- Find Consecutive Integers from a Data Stream Hash Table, Queue, Design
- Detect Squares Array, Hash Table, Design
- RLE Iterator Array, Design
- Count Special Triplets Array, Hash Table
- Identify the Largest Outlier in an Array Array, Hash Table, Enumeration
- Count Almost Equal Pairs I Array, Hash Table, Sorting
- Minimum Length of Anagram Concatenation Hash Table, String
- Minimum Number of Operations to Make Word K-Periodic Hash Table, String
- Sender With Largest Word Count Array, Hash Table, String
- Minimum Operations to Make the Array Alternating Array, Hash Table, Greedy
- Check If Array Pairs Are Divisible by k Array, Hash Table
- Construct K Palindrome Strings Hash Table, String, Greedy
- Find Longest Special Substring That Occurs Thrice I Hash Table, String, Binary Search
- Sum of Beauty of All Substrings Hash Table, String
- Total Characters in String After Transformations I Hash Table, Math, String
- Maximum Total Damage With Spell Casting Array, Hash Table, Two Pointers
- Minimum Substring Partition of Equal Character Frequency Hash Table, String, Dynamic Programming
- Minimum Operations to Write the Letter Y on a Grid Array, Hash Table, Matrix
- Largest Combination With Bitwise AND Greater Than Zero Array, Hash Table, Bit Manipulation
- Make Number of Distinct Characters Equal Hash Table, String
- Largest Palindromic Number Hash Table, String, Greedy
- Number of Pairs of Strings With Concatenation Equal to Target Array, Hash Table, String
- Minimum Number of Swaps to Make the Binary String Alternating String, Greedy
- Change Minimum Characters to Satisfy One of Three Conditions Hash Table, String, Prefix Sum
- Letter Tile Possibilities Hash Table, String, Backtracking
- Subdomain Visit Count Array, Hash Table, String
- Bulls and Cows Hash Table, String
- Minimum Rounds to Complete All Tasks Array, Hash Table, Greedy
- Find All Lonely Numbers in the Array Array, Hash Table
- Tuple with Same Product Array, Hash Table
- Pairs of Songs With Total Durations Divisible by 60 Array, Hash Table
- Minimum Increment to Make Array Unique Array, Greedy, Sorting
- Friends Of Appropriate Ages Array, Sorting
- Construct String With Repeat Limit Hash Table, String, Greedy
- Minimum Number of Steps to Make Two Strings Anagram II Hash Table, String
- Minimum Length of String After Operations Hash Table, String
- Count Substrings Starting and Ending with Given Character Math, String
- Sum of Digit Differences of All Pairs Array, Hash Table, Math
- Number of Nodes in the Sub-Tree With the Same Label Hash Table, Tree, Graph
- Stone Game IX Array, Math, Greedy
- Destroy Sequential Targets Array, Hash Table
- Smallest Missing Non-negative Integer After Operations Array, Hash Table, Math
- Count the Number of Good Subarrays Array, Hash Table, Sliding Window
- 3Sum With Multiplicity Array, Hash Table, Two Pointers
- Reordered Power of 2 Math, Enumeration
- Minimum Number of Operations to Make Array Empty Hash Table, Greedy
- Number of Zero-Filled Subarrays Array, Math
- 4Sum II Hash Table, Array
- Find Players With Zero or One Losses Hash Table, Array, Sorting
- Count Number of Bad Pairs Hash Table, Array
- Determine if Two Strings Are Close Hash Table, String, Sorting
- Brick Wall Hash Table, Array
- Number of Pairs of Interchangeable Rectangles Array, Hash Table, Math
- Count Nice Pairs in an Array Array, Hash Table, Math
- Word Subsets String, Hash Table
- Number of Ways to Split a String String, Math
- Minimum Number of Frogs Croaking String, Greedy
- Top K Frequent Words Array, Hash Table, String
- Minimum Number of Steps to Make Two Strings Anagram Hash Table, String
- Count Servers that Communicate Array, Depth-First Search, Breadth-First Search
- Majority Element II Array, Hash Table, Sorting
- Task Scheduler Array, Greedy, Heap
Hard (8)
- Maximum Number of Ways to Partition an Array Array, Hash Table, Enumeration
- Maximum Equal Frequency Array, Hash Table
- Count Palindromic Subsequences String, Dynamic Programming
- Sum of Prefix Scores of Strings Array, String, Trie
- Minimum Cost to Split an Array Array, Hash Table, Dynamic Programming
- Count Anagrams Hash Table, Math, String
- Subarrays with K Different Integers Array, Hash Table, Sliding Window
- Count Unique Characters of All Substrings of a Given String String, Hash Table
Companies that ask counting problems
- Amazon 107 problems on counting
- Google 64 problems on counting
- Adobe 17 problems on counting
- Microsoft 15 problems on counting
- Infosys 12 problems on counting
- TCS 11 problems on counting
- Uber 8 problems on counting
- Bloomberg 5 problems on counting
- Meta 4 problems on counting
- Cognizant 3 problems on counting
- Goldman Sachs 3 problems on counting
- Indeed 3 problems on counting
Next topic: Math