Frequency arrays and counting
- Stage
- 3
- Module
- M3.6
- Lessons
- 1
In this module
- Build a frequency array to count how often each value appears.
- Use an array index to represent a value so counting happens in one pass.
- Apply frequency counting to solve real problems with character and digit counts.
- Recognize when a frequency array is the right tool and when it is not.
Before this module
Lessons
Practice
Try these on the judge. Each link opens the problem on DMOJ.
- 2016 S1Ragaman (opens on DMOJ in a new tab) DMOJ
Count how many times each letter appears, using the counts to fill a gap.
Why DMOJ: A letter-frequency problem, the direct application of this lesson's array.
- 2017 S3Nailed It! (opens on DMOJ in a new tab) DMOJ
Count how often each length occurs, then use the counts to avoid a slow scan.
Why DMOJ: A frequency-array problem where the counts themselves make a fast solution possible.
- 2019 J2Time to Decompress (opens on DMOJ in a new tab) DMOJ
Expand a compressed string, then count how often each character appears in the result.
Why DMOJ: A one-pass character count over the string this lesson's pattern builds toward.